Нечеткий поиск подстроки в строке

#java #поиск #нечеткий_поиск

Здравствуйте. Необходимо реализовать на Java поиск подстроки в строке.
Т.е. строка 
"Разница между родившимися и умершими" должна быть найдена в строке "Разность между
числом родившихся и числом умерших за определенное время (например, за один год) называют
естественным приростом населения."

А строка "Ивановыми" должна быть найдена в строке "Иванов - древнейший житель города"

Необходим лишь ответ - есть ли что-то похожее в строке. Посоветуйте что-нибудь, желательно
уже реализованное на Java.
    

Ответы

Ответ 1

Грубо говоря это делается в 3 шага:


Разбиваем строку на лексемы/слова
Полученные лексемы прогоняем через Apache Lucene c русской морфологией - в итоге
получаем список лексем очищенный от падежных/родовых и прочих морфологичечких признаков
характерных для великого могучего, то есть вместо:



  Разность между числом родившихся и числом умерших за определенное время 


получим


  Разница между число родить и число умереть за определенный время



Далее для этих лексем вычисляем хэш функцию умеющую выдавать близкие значения хэша
для похожих слов - например SimHash или что-то вроде упомянутого Левенштейна


Остальное надеюсь объяснять не надо.

Алгоритм нечеткого поиска с фильтрацией

#алгоритм #нечеткий_поиск

Ищу решение для максимально быстрого нечеткого поиска по заранее известному множеству
сущностей (например, по географическим объектам). Классические алгоритмы (префиксный
бор, суффиксный автомат, автомат Левенштейна) сами по себе подходят, но ни один из
них (вполне ожидаемо) не предполагает дополнительной фильтрации (в случае с примером
по географическим объектам запрос "Площадь Ленина" может иметь необходимость быть отфильтрованным
по типу "станция метро" и региону "Санкт-Петербург"). Строить автомат для каждого поиска,
конечно, плохой вариант; поиск по единому общему автомату может дать чересчур большой
результат (запрос "Ленина" в этом случае выведет миллиард топонимов с Лениным по всей
России). Сам язык позволяет минимизировать эффект от раздутого результата (java / streaming
api), но хотелось бы решить чисто решить задачу изначально.

Есть ли какие-то известные решения для подобной задачи?
    

Ответы

Ответ 1

Почему этот вопрос - плохой

Я писал этот вопрос на знатно несвежую голову, и по-хорошему его вообще не должно
было возникнуть. То, что алгоритмы выполняют одну-единственную задачу - это их предназначение,
если по выходу из алгоритма получается большой объем данных - это не проблема алгоритма,
а алгоритм, который одновременно ищет и фильтрует - это нонсенс, это два разных алгоритма
(один из которых тривиален), соединенные в одной имплементации. Поиск по содержимому
не имеет ничего общего с дополнительными атрибутами, и если вы строите в своем приложении
автомат имени N, то он знать не должен, есть ли у того, что он ищет дополнительные
атрибуты - он просто должен возвращать дженерик, и всё.

Как правильно сделать

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

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

Какой алгоритм нечеткого поиска лучше для 10 тысяч строк из 50 символов?

#javascript #алгоритм #нечеткий_поиск

Есть массив из 10000 строк. Средняя длина строки 50 символов.

Символы в строках: a-я0-9'"%+!& .,;\-()/

Поиск осуществляется на клиенте при помощи JavaScript. Сейчас использую простой поиск
по точному совпадению при помощи метода indexOf. Какой алгоритм будет оптимальнее?
    

Ответы

Ответ 1

Из комментария пользователя @PinkTux:

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

Можно почитать статью «Нечёткий поиск в тексте и словаре».


Ответ 2

Тут проблема в том, что для каждой ошибки нужен свой алгоритм. Опечатка - наиболее
сложный вариант.
С раскладкой могу посоветовать сразу при наборе каждую букву переводить в другую
раскладку и сразу осуществлять 2 поиска - на той раскладке что вводят и на изменённой.
Если один из вариантов пуст а другой уже нашёл что-то после 3 букв например то можно
показывать на экране.


Ответ 3

Попробуйте Bitap. Реализации на JS у меня нет, но с C# он списывается почти один
в один :)
Вот реализация: Fuzzy Bitap Algorithm

Нечеткий поиск подстроки в строке

Здравствуйте. Необходимо реализовать на Java поиск подстроки в строке. Т.е. строка "Разница между родившимися и умершими" должна быть найдена в строке "Разность между числом родившихся и числом умерших за определенное время (например, за один год) называют естественным приростом населения."
А строка "Ивановыми" должна быть найдена в строке "Иванов - древнейший житель города"
Необходим лишь ответ - есть ли что-то похожее в строке. Посоветуйте что-нибудь, желательно уже реализованное на Java.

Ответ

Грубо говоря это делается в 3 шага:
Разбиваем строку на лексемы/слова Полученные лексемы прогоняем через Apache Lucene c русской морфологией - в итоге получаем список лексем очищенный от падежных/родовых и прочих морфологичечких признаков характерных для великого могучего, то есть вместо:
Разность между числом родившихся и числом умерших за определенное время
получим
Разница между число родить и число умереть за определенный время
Далее для этих лексем вычисляем хэш функцию умеющую выдавать близкие значения хэша для похожих слов - например SimHash или что-то вроде упомянутого Левенштейна
Остальное надеюсь объяснять не надо.

Алгоритм нечеткого поиска с фильтрацией

Ищу решение для максимально быстрого нечеткого поиска по заранее известному множеству сущностей (например, по географическим объектам). Классические алгоритмы (префиксный бор, суффиксный автомат, автомат Левенштейна) сами по себе подходят, но ни один из них (вполне ожидаемо) не предполагает дополнительной фильтрации (в случае с примером по географическим объектам запрос "Площадь Ленина" может иметь необходимость быть отфильтрованным по типу "станция метро" и региону "Санкт-Петербург"). Строить автомат для каждого поиска, конечно, плохой вариант; поиск по единому общему автомату может дать чересчур большой результат (запрос "Ленина" в этом случае выведет миллиард топонимов с Лениным по всей России). Сам язык позволяет минимизировать эффект от раздутого результата (java / streaming api), но хотелось бы решить чисто решить задачу изначально.
Есть ли какие-то известные решения для подобной задачи?

Ответ

Почему этот вопрос - плохой
Я писал этот вопрос на знатно несвежую голову, и по-хорошему его вообще не должно было возникнуть. То, что алгоритмы выполняют одну-единственную задачу - это их предназначение, если по выходу из алгоритма получается большой объем данных - это не проблема алгоритма, а алгоритм, который одновременно ищет и фильтрует - это нонсенс, это два разных алгоритма (один из которых тривиален), соединенные в одной имплементации. Поиск по содержимому не имеет ничего общего с дополнительными атрибутами, и если вы строите в своем приложении автомат имени N, то он знать не должен, есть ли у того, что он ищет дополнительные атрибуты - он просто должен возвращать дженерик, и всё.
Как правильно сделать
Именно так, как я написал под флагом "мне не нравится". Наивный способ предполагает либо возврат большой коллекции, которая затем фильтруется, либо встраивание фильтра прямо в движок поисковика (это можно сделать приемлимо с помощью интерфейсов, но вообще идея отвратительная), либо возврат результата в виде итератора (и это, пожалуй, самая лучшая из пришедших мне в голову наивных идей). Идея со Stream на самом деле является околоидеальной - благодаря возможностям языка можно превратить просто итератор в поток, который будет фильтроваться на лету, и тем самым избавиться как от сложных конструкций с итератором, так и встроить фильтр практически у самого выхода из поискового алгоритма, не устраивая драматичное вторжение в поисковый движок.
Подытоживая - лучше всего, если поисковой движок возвращает итератор или поток данных (если язык имеет такие возможности) - это позволит как отфильтровать результаты на ранней стадии (до того, как они коллекцией займут область памяти), так и галантно организовать архитектуру без излишней боли.