Comments 33
UFO just landed and posted this here
как говорится — нет слов. Мне этот топик понравился уже во время скрола.
Спасибо, что привели полный список используемой вами литературы. Браво.
Спасибо за статью, в аспирантуре занимаюсь анализом текста.
Неистово плюсую, редко встретишь подобную годную статью.
не знаю, кто как, а я уже на тэгах к топику залип-)
Почему вы считаете, что именно эти алгоритмы используются в гугле?
Питер Норвиг — человек, которому можно верить — говорит, что это некоторая разновидность Байесовского классификатора.
Питер Норвиг — человек, которому можно верить — говорит, что это некоторая разновидность Байесовского классификатора.
Статья хорошая!
Но основной проблемой нечеткого поиска всегда было то что индекс нельзя построить по нему, точнее можно но он будет бухнуть на глазах и его эффективность будет равна не то что бы нулю, а даже будет еще хуже, вот если кто то еще опубликует статью как быть с производительностью при огромных словарях я буду очень рад.
Спасибо за статью.
Но основной проблемой нечеткого поиска всегда было то что индекс нельзя построить по нему, точнее можно но он будет бухнуть на глазах и его эффективность будет равна не то что бы нулю, а даже будет еще хуже, вот если кто то еще опубликует статью как быть с производительностью при огромных словарях я буду очень рад.
Спасибо за статью.
Вы в раздел тестирования заглядывали? Конечно, скорость работы по сравнению с точным поиском может отличаться на порядок. Но, опять же, и размер индекса, и время собственно поиска остаются в разумных пределах даже для больших словарей.
Абалдеть! Вот так все описано! Супер!
Есть маленькое дополнение, которое работает на 200000 словаре за доли секунд.
Вводите последовательность норм! Лучше взаимно исключающих.
Применяя несколько алгоритмов последовательно.
Ex:
ищу: «амплитуда» длина 9
количество допустимых ошибок 2 (задайте его параметром и поиграйтесь может на ваших словарях оно будет другим)
сначала отсекаю все слова с длиной не равной 9 +-2 (7,8,9,10,11)
затем отсекаю по норме(тоже самое с шагом 2) (за норму можно и Евклидову взять)
затем «Хеширование по сигнатуре» (2 ошибки)
финальный результат сортирую и отсекаю по «Метод N-грамм» лучше применить последовательно допустим от 2 до 4 (для большей релевантности)
результат радует не только глаз )
P.s. Из практики при количестве ошибок больше 2 результаты не очень, много мусора.
Вводите последовательность норм! Лучше взаимно исключающих.
Применяя несколько алгоритмов последовательно.
Ex:
ищу: «амплитуда» длина 9
количество допустимых ошибок 2 (задайте его параметром и поиграйтесь может на ваших словарях оно будет другим)
сначала отсекаю все слова с длиной не равной 9 +-2 (7,8,9,10,11)
затем отсекаю по норме(тоже самое с шагом 2) (за норму можно и Евклидову взять)
затем «Хеширование по сигнатуре» (2 ошибки)
финальный результат сортирую и отсекаю по «Метод N-грамм» лучше применить последовательно допустим от 2 до 4 (для большей релевантности)
результат радует не только глаз )
P.s. Из практики при количестве ошибок больше 2 результаты не очень, много мусора.
Хотелось бы конечно получить более детальное описание этого алгоритма, чтобы было понятно, к чему такие сложности.
Кроме того, как можно видеть из тестирования, метод N-грамм позволяет на словаре из 3200000 слов (что в 16 раз больше, чем приведенный вами пример) проводить поиск за 1 / 20 секунды. Очевидно, что на 200К слов время работы будет соизмеримо меньше (учитывая свойства этого метода).
Кроме того, как можно видеть из тестирования, метод N-грамм позволяет на словаре из 3200000 слов (что в 16 раз больше, чем приведенный вами пример) проводить поиск за 1 / 20 секунды. Очевидно, что на 200К слов время работы будет соизмеримо меньше (учитывая свойства этого метода).
Последовательность применения алгоритмов сделана для уменьшения выборки на каждом последующем шаге. Чтобы те алгоритмы которые требуют расчетов работали с меньшим множеством. А соответственно скорость увеличивается.
Я абсолютно ничего не понял. Ведь для того, чтобы использовать какой-то метод в процессе самого поиска, надо предварительно соответствующим этому методу образом подготовить индекс.
Хочу увидеть рабочее решение (или хотя бы внятный алгоритм).
Хочу увидеть рабочее решение (или хотя бы внятный алгоритм).
У вас есть словарь, у каждого слова есть предварительно вычисленные значения (длины, нормы, битовой маски,… )
вычисляем допустимые значения длины, нормы,… и отсеиваем все не соответствующие. (простое быстрое сравнение больше меньше)
в моем случает отсеивает порядок а то и 2.
затем смотрим битовую маску и вычисляем расстояние Хемминга, нам удовлетворяют только те для которых расстояние меньше заданного.
множество уменьшилось еще значительнее.
теперь уже используем метод N-грамм, на сильно сокращенном множестве.
Рабочее решение реализовано в админке, для поиска соответствий объектов от разных поставщиков(крайней кустарно). В подсказках(поиска — необходимы веса и т д ) на проекте и отдельной либе не реализовано, (времени увы нехватило). Но если найдутся N-ое количество страждущих, то возьму себя в руки, допишу и выложу.
вычисляем допустимые значения длины, нормы,… и отсеиваем все не соответствующие. (простое быстрое сравнение больше меньше)
в моем случает отсеивает порядок а то и 2.
затем смотрим битовую маску и вычисляем расстояние Хемминга, нам удовлетворяют только те для которых расстояние меньше заданного.
множество уменьшилось еще значительнее.
теперь уже используем метод N-грамм, на сильно сокращенном множестве.
Рабочее решение реализовано в админке, для поиска соответствий объектов от разных поставщиков(крайней кустарно). В подсказках(поиска — необходимы веса и т д ) на проекте и отдельной либе не реализовано, (времени увы нехватило). Но если найдутся N-ое количество страждущих, то возьму себя в руки, допишу и выложу.
1. Что такое норма и как я могу её посчитать от одного слова?
2. Даже если я для слов разной длины раздельно проиндексирую методом хеширования по сигнатуре, то как я во время поиска к результирующему множеству (которое будет состоять из слов длины +-k с хешами, отличными не более чем на k от хеша запроса) применю метод n-грамм?
2. Даже если я для слов разной длины раздельно проиндексирую методом хеширования по сигнатуре, то как я во время поиска к результирующему множеству (которое будет состоять из слов длины +-k с хешами, отличными не более чем на k от хеша запроса) применю метод n-грамм?
1.
Норма — функция вводимая на некотором множестве или пространстве. Можно ввести норму равную сумме int ( буква слова), можно добавить коэффициенты от позиции буквы в слове, а также поиграться с частотой появления буквы (в зависимости от специфики исходных данных)
Не забываем о том что все слово-формы можно приводить к одному виду (маленькие буквы, вырезая ё й… )
2.
я кажется не понял вопроса, но отвечу как понял. У вас есть на выходе множество слов к нему и применяете «метод n-грамм» так как его размер уже не столь велик — он отработает значительно быстрее.
Норма — функция вводимая на некотором множестве или пространстве. Можно ввести норму равную сумме int ( буква слова), можно добавить коэффициенты от позиции буквы в слове, а также поиграться с частотой появления буквы (в зависимости от специфики исходных данных)
Не забываем о том что все слово-формы можно приводить к одному виду (маленькие буквы, вырезая ё й… )
2.
я кажется не понял вопроса, но отвечу как понял. У вас есть на выходе множество слов к нему и применяете «метод n-грамм» так как его размер уже не столь велик — он отработает значительно быстрее.
Это всё какие-то абсолютно бессмысленные процедуры. Я всё же хочу ознакомится с каким-нибудь подобием кода или чего-нибудь такого, чтобы начать наконец понимать идею.
Смысл каждого шага в том что он дешевле чем следующий.
Сравнить слова по длине значительно дешевле чем с помощью метода n-грамм (Поиск начинает работать быстрее).
По поводу кода я уже писал что не считаю целесообразным выкладывать его щас!
Из ваших ответов следует что код вам нужен для решения срочной насущной задачи, не вопрос найдите еще десяток человек которым он нужен, и я выпилю из паровоза самолет, в самые кратчайшие сроки. Чтобы на нем могли ездить не только вы но и все остальные не вникая в реализацию и не спотыкаясь на камнях.
Сравнить слова по длине значительно дешевле чем с помощью метода n-грамм (Поиск начинает работать быстрее).
По поводу кода я уже писал что не считаю целесообразным выкладывать его щас!
Из ваших ответов следует что код вам нужен для решения срочной насущной задачи, не вопрос найдите еще десяток человек которым он нужен, и я выпилю из паровоза самолет, в самые кратчайшие сроки. Чтобы на нем могли ездить не только вы но и все остальные не вникая в реализацию и не спотыкаясь на камнях.
А вообще мне пост очень понравился, лучшее что я ДЛЯ СЕБЯ нашел за последнее время на хабре.
Огромный вам респект ( картинки формулы графики — красота ).
Огромный вам респект ( картинки формулы графики — красота ).
На счет малой эффективности деревьев, откуда такой вывод?
А как же фонетические алгоритмы? Они правда, больше приспособлены, для различных справочников для игнорирования ошибок в имени, фамилии и.т.п
К сожалению, ссылка номер 7 уже достойна удаления :( Клики на том сайте ведут на ООО Информпартнёр, то есть на сервис, снимающий со счёта 1000р в месяц за клик на огромный «ОК» в центре экрана.
Что скажете по поводу такой вот реализации?
Как мне показалось при тесте, достаточно неплохой инструмент для различного типа поиска.
Как мне показалось при тесте, достаточно неплохой инструмент для различного типа поиска.
Sign up to leave a comment.
Нечёткий поиск в тексте и словаре