Исправление опечаток. Совокупность подходов

Я ранее немало писал про исправление опечаток в нескольких заметках, например, можно прочитать здесь по ссылкам про исследования которыми я занимался.

Сейчас же я размышляю над тем как результаты использовать в других задачах или же зафиксировать их в виде продукта или сервиса и изложу ряд взаимосвязанных подходов к исправлению к которым я пришёл. Постараюсь излагать, по возможности, без терминологии и формул в форме свободного текста размышлений.

1. «Подбор ключей»

Это, собственно, предельно простой подход  основанный на том что расстояние Левенштейна между словами a  и b обладает зависимостью от значений расстояния Левенштейна между словами b и c. Подробное описание присутствует в заметке Решение с расчетом расстояния Левенштейна для исправления опечаток 

Такой подход позволяет сократить число сравнений от 2 до 10 раз. Если, к примеру, есть словарь в 100 000 слов и ищем опечатку в слове в 10 знаков, то максимальное число сравнений для расстояния Левенштейна равное 1 будет равно числу слов с  длиной в 9, 10, 11 знаков — в нашем случае суммарно 39161 слов. За счёт фильтра их число сокращается от 3000 до 10000 сравнений. Что всё ещё очень много и сильно зависит от того какое слово рассматривается и насколько оно близко к используемым ключам. 

Основной недостаток этого подхода — слабая предсказуемость и значительные объёмы индексов.

2. Зависимость от производных метрик

Расширим рассмотренный свыше подход.

Предположим что у нас есть функция позволяющая извлечь из слова некую статичную метрику, которая при сравнении с метрикой другого слова даёт численное значение обладающего зависимостью от расстояния Левенштейна между этими словами.

Иными словами нам необходимо создать фильтр по некому простому производному из рассматриваемого слова для быстрого фильтра по базе слов в словаре. При этом есть 

Пройдя чуть далее — можно прийти к выводу что производных может быть много больше и они могут составлять один или несколько взаимосвязанных индексов. Например, в своих исследованиях я применял именно такой подход — итеративно перебирая различные метрики и способы их получения. 

Это позволяет обеспечить лучшую фильтрацию и сократить число сравнений от 10 до 20 раз. То есть, фактически, для примера выше, этот фильтр оставляет лишь от 1500 до 3000 слов в выборке с которыми уже необходимо сравнивать искомое слово. 

3. Ветвление алгоритма  и использование слов выборки из словаря как ключевых слов.

При сравнении слова с опечаткой со словами из выборки слов у нас всегда имеется дополнительная метрика — результат расчета расстояния Левенштейна между этими словами. 

За счет построения индекса который бы охватывал все слова из выборки и ключевые значения при расчете расстояния Левенштейна — число сравнение можно сократить, как минимум, в 2-3 раза.

Ограничения этого подхода в использовании статической выборки и в том что всегда будут слова не попадающие в фильтр и проходящие всю цепочку сравнений. 

Подход потребует длительного расчета расстояния Левенштейна между всеми словами выборки, но это будет не более чем однократной операцией.

Лично я именно этот подход так и не реализовывал до конца, в первую очередь из за необходимости проведения длительных расчётов, особенно для больших словарей.  Конечно Hadoop и прочие инструменты позволяют эту задачу ускорить, но и в этом случае — предварительная подготовка данных ресурсоёмка.

4. Разбор структуры слова и алгоритма

Подробнее о таком подходе я писал здесь.

Собственно тот способ который я использую сейчас — все варианты преобразований слова укладывающиеся в расстояние Левенштейна равное 1 группируются суммарно в около 15 правил для каждого из которых рассчитывается своя статическая метрика однократно по словам в словаре и для каждого слова на проверку. Далее по этим метрикам производится выборка вариантов с совпадающими метриками). 

Плюс подхода в том что фильтрация позволяет сократить размер выборки в тысячи раз. Например, поиск по слову «автомобилъ» (последняя буква заменена на твердый знак) по словарю в 108 000 слов даёт выборку в 29 слов, поиск по слову «алексанндр» (лишняя буква «н» в середине) даёт выборку в 19 слов. 

Для сравнения выборка для слова «алексанндр» по словарю в 5 004 923 слов состоит из 1755 слов, а для слова «автомобилъ» на том же словаре выборка состоит из 1031 слова. 

Цена столь сильного сокращения выборки в сложности построения запросов — сейчас лично использую для этой задачи SQL сервер и это куда медленнее чем если создать свою структуру под хранение словаря с индексами и постоянно держать её в памяти. 

Можно обратить внимание что размер выборки практически растёт в соответствии с ростом словаря, но, за счёт того что фильтр изначально отсеивает до 99.9% слов, то основные временные затраты приходятся на получение выборки, а не на расчёт расстояния Левенштейна к словам в ней. Кроме того, за счёт усложнения фильтра возможно и последующее сокращение выборок в 2-3 раза вопрос лишь в подборе баланса временных затрат на фильтрацию и на последующие сравнения.

About This Author

Яндекс.Метрика