Главная » Статьи » Excel » Макросы и программы VBA

Нечёткий поиск

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

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

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

Для тех, кто спешит, сразу сообщаю, что, если тема актуальна, то я предлагаю вам воспользоваться своей пользовательской функцией рабочего листа, которая называется 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 статический и меняется редко.

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

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

Категория: Макросы и программы VBA | Добавил: dsb75 (27.12.2014) | Автор: Батьянов Денис E W
Просмотров: 5048 | Комментарии: 7 | Теги: нечёткий поиск, Fuzzy search | Рейтинг: 5.0/3
Всего комментариев: 7
7 yourredjoker   (22.07.2016 11:44)
Если копировать в свой файл, то выдает, что переменная TextCompare не объявлена(

6 Lyfan   (03.02.2016 10:45)
Повисает файл, когда база для поиска большая, у меня 1000 строк и все виснет, что можно сделать?

4 podbelski   (28.12.2015 12:18)
Можно как-то модифицировать функцию, чтобы работала с переставленными словами?
Сейчас для Сергей Иванов, находит Иван Иванов вместо Иванов Сергей.

0
5 dsb75   (29.12.2015 07:02)
Думаю нельзя, там порядок слов вообще не учитывается никак.

0
3 SvetaS   (16.09.2015 20:51)
Добрый Вечер! подскажите, пожалуйста, что нужно сделать - чтобы заработало -- http://perfect-excel.ru/forum/9-31-1

0
1 AndS   (27.04.2015 15:47)
Есть прикладная задача под этот алгоритм. Посмотрите если пришлю описание на почту?

0
2 dsb75   (27.04.2015 15:48)
Конечно

Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Яндекс.Метрика