Техническое: Решение с расчетом расстояния Левенштейна для исправления опечаток

Про эту задачку и что у неё есть решения я писал раньше и всё таки решил описать один из способов как её можно решить без использования n-gram.

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

Рассмотрим что у нас есть:

1. Слово, предположительно с опечаткой, по которому нам необходимо найти все вероятные кандидаты слов похожих на него.

2. Массив слов словаря по которым мы проверяем данное слово. Условно не менее 100 000 слов, в реальности до 1 миллиона.

3. Формула расчёта расстояния Левенштейна для определения отличий между словами.

4. Необходимо найти не просто первое совпадение, но всех потенциальных кандидатов.

Если решать эту задачу в лоб, то несложно понять что прямым перебором нам придётся совершить 100 000 сравнений. Это может быть немного для работы в оффлайне, но много для работы с потоками слов и работой онлайн.

Вопрос: как можно сократить число сравнений?

Первое же что приходит на ум — это учёт длины слова.

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

Например, если мы ищем кандидатов для слова из 12 букв и ожидаемое расстояние Левенштейна равно 2, то нам необходимо выбрать все слова от 10 до 14 букв. На моей выборке из 100 000 слов из словаря Зализняка это будет означать 44 000 слов кандидатов, итого число сравнений сократилось вполовину.

Для слов из 15 букв и расстояния равного 2 — всего будет 14276 слов кандидатов и так далее, чем больше букв в слове тем меньше кандидатов в словаре и меньше делать сравнений.

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

Пусть есть слова a, b, c и расчёт расстояния Левенштейна для них это f(a,b), f(b,c) и f(a,c). Где a — это слово которое мы проверяем, а b и c — это элементы словаря.

Для начала сделаем предположение.

f(a, c) <= f(b, c) + f(a, b)

f(a, c) => abs ( f(b, c) — f(a, b) )

Наверняка — это можно доказать или даже уже доказано, пусть это будет предположением на моей совести.

в результате

abs ( f(b, c) — f(a, b) ) <= f(a, c) <= f(b, c) + f(a, b)

То есть расстояние Левенштейна между a и c будет не более суммы расстояний Левенштейна между b и с, и b и a.

И расстояние Левенштейна между a и c будет не менее абсолютного значения разницы между расстояниями Левенштейна между b и c, и b и a

А теперь вспомним что нас то интересуют все те результаты где f(a, c) равно некой константе, например, 2-м.

Что это означает на практике? Рассмотрим:

инок и вино слова в словаре и слово пиво как слово для проверки при расстоянии Левенштейна равном 2.

f(инок, вино) = 2

f(вино, пиво) = 2

0 <= f(пиво, инок) <= 4

что соответствует действительности, поскольку f(пиво, инок) = 2, но нам это никак не помогает, поскольку в пределах от 0-4 есть множество значений.

рассмотрим другой случай:

виноделие и виночерпие в словаре и пилорама как слово для проверки

f(виноделие, виночерпие) = 3

f(виноделие, соленоид) = 7

4 <= f(виночерпие, соленоид) <= 10

при реальных значениях f(виночерпие, соленоид) = 7.

Но нам нет необходимости делать это сравнение поскольку мы заведомо знаем что f(виночерпие, соленоид) > 4, и, соответственно, больше искомого нами расстояния Левенштейна равного 2-м.

Что мы получаем в итоге.

1. Подготовка данных

b — может быть заменено на множество B небольшой выборкой слов с которыми сравнивается a.

c — заменяется множеством C — из всех слов кроме входящих в B

для каждого слова b в множестве B рассчитывается проводится расчёт расстояния Левенштейна для каждого слова c в множестве C и перечень значений f(b, c) сохраняется как часть общего индекса Index(B, C)

2. Процедура сравнения

Слово a последовательно сравнивается со словами из выборки B где для каждого сравнения строится массив значений f(a, b).

Этот массив используется в качестве фильтра для индекса Index(B,C) в результате чего определяется число значений.

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

Соответственно, в чём особенность эффективности работы такого подхода — в правильном подборе выборки B.

Но это уже совсем другая история, которую можно решать алгоритмами n-gram, частотным анализом или анализом расстояний Левенштейна.

About This Author

  • tasman

    Интересный подход. Вот еще вариант решения проблемы.

    Букв в алфавите для русского языка 33 (для английского 26), бит в двухбайтном «слове» 32. Для каждой буквы в алфавите выделяем свой бит. Если в слове соответствующая буква присутствует — ставим 1, если нет — 0. (Решение нехватки бит для русского алфавита простое — достаточно объеденить пару малоиспользуемых букв, например ъ и ь)

    Для каждого слова из словаря расчитываем такое значение и сохраняем — это наш индекс. Теперь при поступлении слова достаточно такой же расчет сделать и для него. Далее можно либо нагенерить «похожих» значений с отличием в n бит и выбрать все соответствующие слова из индекса, либо пробежаться по всему индексу и с помощью xor и подсчета оставшихся единичных бит получить оценку похожести. Естественно эту выборку нужно проверять непосредственно алгоритмом расчет расстояния Левенштейна.

    Конечно в выборке таким способом будет довольно много лишних слов по сравнению с тем же n-gram’ным методом, но скорость будет больше. И отсуствует проблема правильного подбора выборки B из описаного метода.

  • http://ivan.begtin.name ivbeg

    Подборка выборки B — это не такая уж серьёзная проблема:) Во всяком случае это однократный расчёт по статической базе.

    В том что Вы предлагаете важно оценить реальную скорость и точность — провести тесты. В общем случае да, должно быть быстрее чем в случае n-gram, но мне пока непонятно как в данном случае Вы учитываете удаление и вставки символов.

  • tasman

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

    Насчет учитывания удаления и вставки — как раз удаление и вставка только и учитывается (есть данный символ в слове или нет, и соответственно есть он или нет в сравниваемом слове). Не учитывается возможность нескольких символов в слове повторяться, не учитывается взаимное расположение — и как следствие перестановочные ошибки не учитываются вовсе. То есть данный метод позволяет сократить количество слов из словаря для дальнейшей проверки с помощью расстояния Левенштейна, но в то же время он дает гораздо больше ложных срабатываний по сравнению с теми же n-gram’ными методами.

    Метод использовался на словарях порядка 200 000 слов, и позволил считать приходящие потоком слова в реальном времени. Хотя сравнительные замеры с другими методами я не проводил.

    ЗЫ может на ты? :)

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