Pull to refresh
  • by relevance
  • by date
  • by rating

Нечёткий поиск в тексте и словаре

Algorithms *

Введение


Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.

В этой обзорной статье я рассмотрю следующие понятия, методы и алгоритмы:
  • Расстояние Левенштейна
  • Расстояние Дамерау-Левенштейна
  • Алгоритм Bitap с модификациями от Wu и Manber
  • Алгоритм расширения выборки
  • Метод N-грамм
  • Хеширование по сигнатуре
  • BK-деревья
А также проведу сравнительное тестирование качества и производительности алгоритмов.
Читать дальше →
Total votes 171: ↑170 and ↓1 +169
Views 220K
Comments 33

Поиск повторений в двумерном массиве, или вычислительная сложность на примере

Programming *Algorithms *Visual Basic for Applications *
Sandbox
Доброго времени суток, уважаемое хабрасообщество.

Когда я учился в институте на втором или третьем курсе (то есть, в общем, не так и давно), был у меня, помимо прочих, предмет под названием «алгоритмы и структуры данных». Рассказывали там, однако, не только про сами алгоритмы и структуры, но и о таком понятии, как «вычислительная сложность». Признаюсь, тогда это меня не очень заинтересовало.

«Наверняка заморачиваться с исследованием алгоритма на пространственную и временную сложность нужно только при разработке либо очень высокопроизводительных/высоконагруженных систем, либо при работе с действительно большими объемами данных», — примерно такие мысли посещали меня (да и, наверное, не только меня) тогда.

Однако недавно мне пришлось сильно изменить свое мнение из-за простой, казалось бы, задачи.
Читать дальше →
Total votes 49: ↑36 and ↓13 +23
Views 4.4K
Comments 31

Поиск повторений в двумерном массиве, или правильно выбранный инструмент

Programming *Algorithms *Visual Basic for Applications *
Sandbox
Доброго времени суток.

В той или иной степени интересуюсь алгоритмами. Наткнулся на свежую статью
«Поиск повторений в двумерном массиве, или вычислительная сложность на примере» http://habrahabr.ru/post/141258/. Автор стати,Singerofthefall, довольно интересно рассказывает про решение задачи и оптимизации алгоритма. Очень интересно. Однако, по моему мнению, прежде всего необходимо было определить не алгоритм, а инструмент которым будет решаться задача. И вот инструмент был выбран неправильный, отсюда вся сложность и оптимизации.
Для решения задачи автора более всего подходили инструменты БД, соответственно и надо было их использовать.
Читать дальше →
Total votes 12: ↑7 and ↓5 +2
Views 980
Comments 2

Нечеткий поиск в словаре с универсальным автоматом Левенштейна. Часть 1

Search engines *Algorithms *Natural Language Processing *
Sandbox


Нечеткий поиск строк является весьма дорогостоящей в смысле вычислительных ресурсов задачей, особенно если вам необходима высокая точность получаемых результатов. В статье описан алгоритм нечеткого поиска в словаре, который обеспечивает высокую скорость поиска при сохранении 100% точности и сравнительно низком потреблении памяти. Именно автомат Левенштейна позволил разработчикам Lucene повысить скорость нечеткого поиска на два порядка
Читать дальше →
Total votes 53: ↑51 and ↓2 +49
Views 56K
Comments 7

Нечеткий поиск в словаре с универсальным автоматом Левенштейна. Часть 2

Search engines *Algorithms *Natural Language Processing *


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

Читать дальше →
Total votes 32: ↑32 and ↓0 +32
Views 20K
Comments 3