Проблема нечёткого поиска

Когда мы имеем дело с текстом, вводимым человеком, то в нём неизбежны ненамеренные ошибки. Вместо "пер. Гоголя" человек может набрать "пер. Ноголя" просто потому, что промахнётся по нужной клавише и нажмёт соседнюю. В виду этого, возникает задача поставить в соответствие введеному слову слово словарное, которое в наибольшей степени похоже на то, что ввёл пользователь. Классическая задача - верификация названий улиц, населенных пунктов и т.п. Обычный поиск тут бессилен, так как введенное слово в словаре отсутствует. Обычный поиск в состоянии только установить этот факт, но не в состоянии предложить пользователю на выбор наиболее близкие варианты. Нужна реализация нечёткого поиска.

Что я предлагаю

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

Формат вызова: =FS_GetClosestWord( What ; Where ; [NumItem] ; [MinLen] ; [Compare] ; [Dbg] ) , где:

• What - ссылка на ячейку, которая содержит искомую строку. Обратите внимание, что текстовая константа в формуле не будет воспринята, только ссылка на ячейку;

• Where - ссылка на диапазон, содержащий словарь, в котором необходимо подобрать наиболее близкое к What слово. Словарь может быть в виде столбца, строки или состоять из произвольного размера диапазона. Имейте только в виду, что, задав словарь из большого количества слов (скажем больше 10000), или, если словарь содержит много очень длинных слов, то вы рискуете надолго подвесить систему;

• [NumItem] - в процессе поиска строится коллекция наиболее подходящих слов, которые ранжируются по определенному алгоритму. NumItem определяет номер возвращаемого слова из этой коллеции. NumItem=1 возвращает наиболее близкое по мнению используемого алгоритма слово. Если указанный номер слишком велик и результирующая коллекция не содержит такого числа элементов, то возвращается ошибка #Н/Д;

• [MinLen] - минимальная длинна буквенных комбинаций, на которые разбиваются слова из словаря и, которые потом ищутся в слове из What. Не может быть меньше 3. Если укажете меньше 3 или не укажете вовсе, то будет использовано значение 3;

• [Compare] - тип сравнения строк: с учётом регистра или без учёта. 0 - с учётом регистра, 1 - без учёта регистра;

• [Dbg] - если указать тут число большее 1, то включится режим отладки и в зависимости от того, что вы тут укажаете, сможете получить:

  • 1 - стандартное поведение, возвращающее близкое слово из Where;

  • 2 - найденная подстрока;

  • 3 - слепок найденного словарного слова;

  • 4 - разница по модулю между слепком найденного и искомого слова, которая используется для ранжирования найденных слов по уровню схожести с оригинальным словом (чем меньше разница, тем считаются более похожими слова).

Большинство пользователей обойдутся первыми двумя параметрами.

Скачать файл с функцией

Скачать

Если будете переносить руками в свой Excel VBA проект, то не забудьте помимо модуля Fuzzy, также перенести класс Search.

Теория нечёткого поиска

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

Предположим, что у нас в словаре есть слово ПОМИДОР. Мой алгоритм разбивает это слово на подстроки длиной от 7 до 3 символов. 7 - длина слова в данном случае, а комбинации символов короче трёх символов использовать особого смысла нет.

• 7 символов - 1 вариант (ПОМИДОР)

• 6 символов - 2 варианта (ПОМИДО, ОМИДОР)

• 5 символов - 3 варианта (ПОМИД, ОМИДО, МИДОР)

• 4 символа - 4 варианта (ПОМИ, ОМИД, МИДО, ИДОР)

• 3 символа - 5 вариантов (ПОМ, ОМИ, МИД, ИДО, ДОР)

• Итого мы получили из слова ПОМИДОР 15 разных буквенных комбинаций.

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

Проблемы реализации нечёткого поиска

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

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

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

Читайте также:

• Извлекаем список уникальных значений из необработанных данных

• Формирование случайных списков на основе справочника

• Расширенное сравнение двух колонок (списков)