@antoart
Web developer

Как определить похожесть двух строк?

Приветствую.

Прошу вашей помощи в решении задачи. Подсказать направление куда "копать".

Имеется список строк. Длина строки 2-7 слов. В этих строках написаны названия различных приложений. Строки часто составлены или с ошибками, или с лишними словами, или короче, чем оригинальное название.
Например, " Система для документов Программуля" вместо " Программуля плюс документс".
То есть в этих строках сохраняется некая суть правильного названия.

Имеется база (список) правильных названий программ.

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

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

Прошу помочь советом. Не жду готовых решений (разве что чего-то похожего для примера). Подскажите куда "копать", как выстроить алгоритм?

Буду реализовывать на языке Java.

UPD: набрел на одну тему, где использовался алгоритм нечеткого сравнения для сравнения слов из предложения со словарем правильных слов.
Проводили индексацию предложения, выстраивали массив встречающихся слов и связей с другими словами. Дальше не объясню, не совсем понимаю.
Что такое индексация? Как она помогает в поиске целого предложения по отдельным словам.

Спасибо откликнувшимся ☺
  • Вопрос задан
  • 16287 просмотров
Решения вопроса 2
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
ruFelix
@ruFelix
Предсказание будущего по руке, таро, кофе.
Не, вы не то просите. Похожесть строк это когда две строки.
А вы будете брать одно строку из одного множества, и ранжировать(сортировать) по релевантности к ней второе множество.
Т.е. у вас строка и множество строк это не тоже самое, что две строки.

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

Индексация нужна, что всё тормозило один раз при индексации, а не при поиске каждого совпадения.
Ответ написан
Пригласить эксперта
Ответы на вопрос 5
@vilgeforce
Раздолбай и программист
Выбираете алгоритм нечеткого сравнения, пробуете. Подошел - хорошо, нет - ищете дальше.
Ответ написан
riot26
@riot26
<:З )~~
Забавно, но буквально только что на хабре была опубликована статья на близкую тему: https://habrahabr.ru/post/275937/
Ответ написан
dimonchik2013
@dimonchik2013
non progredi est regredi
ТС нужен что-то вроде системы поиска плагиата
https://habrahabr.ru/post/199190/

можно взять Сфинкс, добавить стеммер, добавить синонимы и дальше посмотреть, как будет срабатывать релевантность
sphinxsearch.com/blog/2010/08/17/how-sphinx-releva...
Ответ написан
@antoart Автор вопроса
Web developer
Пришел к тому, что хорошо бы освоить Apache Lucene.
Тот способ поиска, который был у меня самопальный, работал "не так чтобы очень".
Много "допиливаний" требовалось по различным неточностям.
Но. Есть пару "но". Создание самопального продукта позволило более детально изучить вопрос поиска, поисковых систем, разбиения на токены и индексацию.
Так что все было отлично.

Пробуйте свои идеи. Даже если не пойдет, приобретете опыт.
Ответ написан
Комментировать
@RuWeb
Вот уже готовый онлайн сервис TextTools.ru
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Bell Integrator Ульяновск
До 400 000 ₽
Bell Integrator Ижевск
До 400 000 ₽
Bell Integrator Хабаровск
До 400 000 ₽
29 мар. 2024, в 15:11
50000 руб./за проект
29 мар. 2024, в 15:06
50000 руб./за проект