Алгоритм нечеткого поиска с помощью Python

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

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

Данный сценарий реализует задачу нечеткого поиска с помощью библиотек языка программирования Python в Loginom.

Для работы узла Python может потребоваться предварительная настройка Loginom и установка Python. В демопримере используется библиотека fuzzywuzzy.

Инструкция по установке библиотеки.

Примечание: Демопример имеет ограничение демонстрации всех возможностей при запуске на демостенде (Запустить демо). Рекомендуем установить пример локально.

Запустить демо

Установить локально

Описание алгоритма

1. Импорт данных

В подмодели Импорт данных загружаются данные из текстового файла, содержащего поисковые запросы для сравнения.

а) Загрузка данных

Таблица «Данные для сравнения»:

Имя поля Метка поля
Text_1 Text_1 Текст 1
Text_2 Text_2 Текст 2

2. Нечеткий поиск

В подмодели Нечеткий поиск реализован алгоритм нечеткого поиска с помощью обработчика Python.

а) Методы нечеткого поиска

Библиотека Python fuzzywuzzy предоставляет различные методы осуществления нечеткого поиска. Использование определенного метода обусловлено конкретной задачей или типом данных.

Рассмотрим каждый метод более подробно:

1) fuzz.ratio — метод, при котором к данным применяется простое посимвольное сравнение. Рейтинг «100» присваивается, только если строки полностью равны; любое различие уменьшает рейтинг, будь то знаки препинания, регистр букв, порядок слов и так далее.

2) fuzz.token_sort_ratio — данный метод акцентирует внимание именно на самих словах, игнорируя регистр букв, порядок слов и даже знаки препинания по краям строки.

3) fuzz.token_set_ratio — метод, похожий на предыдущий, но дополнительно игнорирующий повторяющиеся слова и учитывающий только уникальные.

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

5) fuzz.WRatio — метод, который работает ближе к человеческой логике, комбинируя несколько методов в один алгоритм с определенными весами.

Для выбора метода в настройках порта переменных подмодели Нечеткий поиск необходимо указать соответствующее значение номера алгоритма для переменной fuzchanger.

б) Настройки узла Нечеткий поиск

В настройках входного порта узла Python самостоятельно задаются столбцы:

Имя поля Метка поля
Text_1 Text_1 Текст 1
Text_2 Text_2 Текст 2
fuzzy_search fuzzy_search Значение нечеткого поиска

Устанавливается галочка в пункте Разрешить формировать выходные столбцы из кода.

Для доступа к данным портов и другим встроенным объектам в контексте выполнения кода предусмотрены:

  • Входные наборы данных (InputTable)
  • Входные переменные (InputVariables)
  • Выходной набор данных (OutputTable)
  • Необходимые перечисления (DataType)

Вышеуказанные объекты импортируются из встроенного модуля «builtin_data». По умолчанию в текст исполняемого узлом кода добавляется строка импорта.

Импорт библиотеки:

from builtin_data import InputTable, InputVariables, OutputTable, DataType
from fuzzywuzzy import fuzz

Объявляем словарь с функциями нечеткого поиска:

fuzz_function_map = {     
    1: fuzz.ratio,
    2: fuzz.token_set_ratio,
    3: fuzz.token_sort_ratio,
    4: fuzz.partial_ratio,
    5: fuzz.WRatio
}

Присваиваем переменной функцию, полученную по ключу из словаря:

     fuz_value = fuzz_function_map.get(InputVariables.Items["fuzchanger"].Value, fuzz.ratio) 
     for i in range(InputTable.RowCount):
        text1 = InputTable.Get(i, 0)
        text2 = InputTable.Get(i, 1)
        OutputTable.Append()
        OutputTable.Set(0, text1)
        OutputTable.Set(1, text2)

Применяем алгоритм нечеткого поиска между столбцами:

OutputTable.Set(2, fuz_value(text1, text2))

Результат для метода fuzz.ratio:

Текст 1 Текст 2 Значение нечеткого поиска
Who is most talented on share? Who is most talented email world? 76
How do doughnut shops to actually make enough to survive, as well as pay for rent and employees? How do doughnut shops to actually make enough to survive, as well as pay for rent and employees? 36
How do game STP? How does StP? 76
What are good activities for a 2 old? What are good activities for a engineer year old? 84
Does turmeric powder stops or disturb mustache and beard growth in men if applied on face? What is the chances of getting a commitmentphobic man who says he'll never marry to want to try? He’s a little broken after his first marriage. 29

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

Скачать демопример

Минимальные требования к системе:

  • Операционная система: Windows 8.1 и выше.
  • CPU x64: 1 core.
  • Оперативная память: 1 GB.
  • Жесткий диск: 10 GB.