Нечеткий поиск?

Question

[Zubchick]

Есть две строки, 1я короткая 1-3 слова, вторая длинная 10-20 слов, надо определить, находится ли первая строка во второй или на сколько процентов она там находится. Посоветуйте алгоритмы :)

Comments

[xmoonlight]

Есть готовое API для этого. Думаю, что идеально подойдёт для Ваших целей.

Answer 1

[Nicolette]

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

Comments

[Zubchick]

я пока тоже остановился на длине общего префикса, но если короткая фраза из нескольких слов, все немного портится.

Answer 2

[bear11]

попробуйте дистанцию Левенштейна считать:http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0
пример
bytes.com/topic/python/answers/580959-fuzzy-string-comparison

Comments

[Zubchick]

Я еще нашел некое расстояние Хемминга, читаю :)

Answer 3

[Никита]

if(longStr.Contains(shortStr))

Comments

[Zubchick]

Это чёткий, пацанский поиск :)
И он уже есть!

[Никита]

ай ай ай, ctrl+shift…
int proc = 100 — ((longStr.replace(shortStr,string.empty).length) / (longStr.length/100); //на столько процентов shortStr находится в longStr

Answer 4

[tampere]

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

Answer 5

[Олег Матрозов]

Можно сравнивать методом триграмм. Даст определенный результат, даже если слова с разными окончаниями и т.д.

Answer 6

[lightcaster]

Традиционно — расстояние левенштейна.

Но я бы рекомендовал использвоать common longest subsequence. При этом, можно ввести некий штраф за гэпы между словами.

Comments

[Zubchick]

расстояние Левенштейна не подходит, во всяком случае в чистом виде, т.к. фразы разной длины…

[lightcaster]

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

К примеру, можно поступить так

мама мыла раму
утром мама тряпкой мыла запыленную раму

Твой словарь:
мама: 0
мыла: 1
раму: 2
утром: 3
тряпкой: 4
запыленную: 5

И того, две последовательности:

012
304152

Расстояние левеншнейна: 3
Наибольшая общая подпоследовательность: 3 — 012

Можно и по буквам это все сравнивать. Но это займет больше времени.
Вообще, не считая шинглов и прочей магии, типовые алгоритмы:
Hamming Distance
Levenstein Distance (Edit Distance)
Damerau-Levenstein Distance
Longest common substring
Longest common subsequence
Needleman-Wunsch distance
Smith–Waterman distance

Но, насколько я знаю, все они квадратичные по сложности. Так что не для всех задач подойдут.

[Zubchick]

у меня так много информации обрабатывать, так что пойдут. Посмотрю, спасибо.

Answer 7

[xmoonlight]

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