Comments 33
Странно, что вы не рассмотрели подробно алгоритм Жаро-Винклера. Несколько лет назад я проводил сравнительное тестирование алгоритмов на задачу сопоставления коротких фраз (географические названия, имена собственные, названия событий и т.д.) Выбрал Жаро-Винклера.
Статья же вовсе не о метриках, да и расстояние Джаро-Винклера не является метрикой с математической точки зрения, потому оно затрудняет или делает невозможной реализацию некоторых алгоритмов. Собственно, и используется то оно не часто.
Так а в чём смысл вашей статьи? Объясните, какие цели вы преследовали.
Алгоритмы нечёткого поиска, а не сравнения. Метрики Левенштейна и Дамерау-Левенштейна приведены для того, чтобы показать суть нечёткого сопоставления и разъяснить, как же оно там внутри всё сравнивает. Сами алгоритмы поиска лишь использует эти метрики для своей работы.
как говорится — нет слов. Мне этот топик понравился уже во время скрола.
Спасибо, что привели полный список используемой вами литературы. Браво.
Рискну предположить, что по ссылке — ни что иное, как метод Расширения выборки (с ранжированием по частоте), который как раз наиболее часто и используется в spell-checker'ах, и обзор которого так же присутствует в статье.
Статья хорошая!

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

Спасибо за статью.
Вы в раздел тестирования заглядывали? Конечно, скорость работы по сравнению с точным поиском может отличаться на порядок. Но, опять же, и размер индекса, и время собственно поиска остаются в разумных пределах даже для больших словарей.
Думаю, нужно уточнить в разделе тестирования условия подборки тестового пула слов: какой объем пула, по какому принципу отбирались слова для тестирования (случайному?).
Объем пула подбирался таким образом, чтобы дальнейшее его увеличение не приводило к какому-либо изменению в результатах (это около 1000 слов).

В итоге, в пул попадало каждое Размер словаря / Объем пула слово не короче 3 символов из отсортированного словаря.
Есть маленькое дополнение, которое работает на 200000 словаре за доли секунд.
Вводите последовательность норм! Лучше взаимно исключающих.
Применяя несколько алгоритмов последовательно.
Ex:
ищу: «амплитуда» длина 9
количество допустимых ошибок 2 (задайте его параметром и поиграйтесь может на ваших словарях оно будет другим)

сначала отсекаю все слова с длиной не равной 9 +-2 (7,8,9,10,11)
затем отсекаю по норме(тоже самое с шагом 2) (за норму можно и Евклидову взять)
затем «Хеширование по сигнатуре» (2 ошибки)
финальный результат сортирую и отсекаю по «Метод N-грамм» лучше применить последовательно допустим от 2 до 4 (для большей релевантности)

результат радует не только глаз )

P.s. Из практики при количестве ошибок больше 2 результаты не очень, много мусора.
Хотелось бы конечно получить более детальное описание этого алгоритма, чтобы было понятно, к чему такие сложности.

Кроме того, как можно видеть из тестирования, метод N-грамм позволяет на словаре из 3200000 слов (что в 16 раз больше, чем приведенный вами пример) проводить поиск за 1 / 20 секунды. Очевидно, что на 200К слов время работы будет соизмеримо меньше (учитывая свойства этого метода).
Последовательность применения алгоритмов сделана для уменьшения выборки на каждом последующем шаге. Чтобы те алгоритмы которые требуют расчетов работали с меньшим множеством. А соответственно скорость увеличивается.
Я абсолютно ничего не понял. Ведь для того, чтобы использовать какой-то метод в процессе самого поиска, надо предварительно соответствующим этому методу образом подготовить индекс.

Хочу увидеть рабочее решение (или хотя бы внятный алгоритм).
У вас есть словарь, у каждого слова есть предварительно вычисленные значения (длины, нормы, битовой маски,… )
вычисляем допустимые значения длины, нормы,… и отсеиваем все не соответствующие. (простое быстрое сравнение больше меньше)
в моем случает отсеивает порядок а то и 2.
затем смотрим битовую маску и вычисляем расстояние Хемминга, нам удовлетворяют только те для которых расстояние меньше заданного.
множество уменьшилось еще значительнее.
теперь уже используем метод N-грамм, на сильно сокращенном множестве.

Рабочее решение реализовано в админке, для поиска соответствий объектов от разных поставщиков(крайней кустарно). В подсказках(поиска — необходимы веса и т д ) на проекте и отдельной либе не реализовано, (времени увы нехватило). Но если найдутся N-ое количество страждущих, то возьму себя в руки, допишу и выложу.
1. Что такое норма и как я могу её посчитать от одного слова?
2. Даже если я для слов разной длины раздельно проиндексирую методом хеширования по сигнатуре, то как я во время поиска к результирующему множеству (которое будет состоять из слов длины +-k с хешами, отличными не более чем на k от хеша запроса) применю метод n-грамм?
1.
Норма — функция вводимая на некотором множестве или пространстве. Можно ввести норму равную сумме int ( буква слова), можно добавить коэффициенты от позиции буквы в слове, а также поиграться с частотой появления буквы (в зависимости от специфики исходных данных)
Не забываем о том что все слово-формы можно приводить к одному виду (маленькие буквы, вырезая ё й… )

2.
я кажется не понял вопроса, но отвечу как понял. У вас есть на выходе множество слов к нему и применяете «метод n-грамм» так как его размер уже не столь велик — он отработает значительно быстрее.
Это всё какие-то абсолютно бессмысленные процедуры. Я всё же хочу ознакомится с каким-нибудь подобием кода или чего-нибудь такого, чтобы начать наконец понимать идею.
Смысл каждого шага в том что он дешевле чем следующий.
Сравнить слова по длине значительно дешевле чем с помощью метода n-грамм (Поиск начинает работать быстрее).

По поводу кода я уже писал что не считаю целесообразным выкладывать его щас!
Из ваших ответов следует что код вам нужен для решения срочной насущной задачи, не вопрос найдите еще десяток человек которым он нужен, и я выпилю из паровоза самолет, в самые кратчайшие сроки. Чтобы на нем могли ездить не только вы но и все остальные не вникая в реализацию и не спотыкаясь на камнях.
Если не говорить о том, что то, что вы описываете — полный абсурд, то я всего лишь хотел понять смысл всего происходящего, и так как я не могу получить нормального описания алгоритма, то мне нужен код.

И да — метод n-грамм не является методом сравнения слова.
Ух. Думаю каждый останется пока при своем.
Я с кучей схожих объектов от разных источников(импортеров — поставщиков) линкующихся в один материнский наш.
А вы с чем?
А вообще мне пост очень понравился, лучшее что я ДЛЯ СЕБЯ нашел за последнее время на хабре.
Огромный вам респект ( картинки формулы графики — красота ).
Для меня это очевидно из самого определения Trie-метода. Я буду приятно удивлен, если это не так, и, может быть, наконец, увижу хоть какие-нибудь результаты его сравнительного тестирования.
А как же фонетические алгоритмы? Они правда, больше приспособлены, для различных справочников для игнорирования ошибок в имени, фамилии и.т.п
К сожалению, ссылка номер 7 уже достойна удаления :( Клики на том сайте ведут на ООО Информпартнёр, то есть на сервис, снимающий со счёта 1000р в месяц за клик на огромный «ОК» в центре экрана.
Что скажете по поводу такой вот реализации?
Как мне показалось при тесте, достаточно неплохой инструмент для различного типа поиска.
Only those users with full accounts are able to leave comments. Log in, please.