Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.
В этой обзорной статье я рассмотрю следующие понятия, методы и алгоритмы:
Расстояние Левенштейна
Расстояние Дамерау-Левенштейна
Алгоритм Bitap с модификациями от Wu и Manber
Алгоритм расширения выборки
Метод N-грамм
Хеширование по сигнатуре
BK-деревья
А также проведу сравнительное тестирование качества и производительности алгоритмов.
Ежедневно каждый из нас принимает решения. Принятие решений — это один из важнейших видов деятельности человеческого мозга и большая проблема на пути создания искусственного интеллекта.
Решение – это процесс и результат выбора цели и способа действий. У решения можно выделить:
Стоимость (затраты) решения — негативные факторы, связанные с решением.
Выгода (выгодность, прибыль) решения — соответственно, позитивные факторы, связанные с решением.
Цена решения — соотношение стоимости и выгоды, при которых решение принимается.
Большинство решений принимаются человеком спонтанно, то есть без анализа ситуации. Причиной этого является сильное преобладание выгодности решения над стоимостью. В этом случае «анализ ситуации» несет в себе дополнительные затраты. Однако, при повышении стоимости или уменьшении выгодности решения внимание человека к ситуации увеличивается.