LINUX.ORG.RU

нечеткий поиск подстроки


0

1

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

Ответ на: комментарий от ilias

спасибо что закидали меня абривеатурами :) КМП ищет точную подстроку в строке, БМ вообще не нашел, но подозреваю что тоже.

Zubchick
() автор топика

Вы измеряете длину строк в словах. Значит ли это, что вы оперируете только целыми словами или просто длина так выражена приблизительно?

proud_anon ★★★★★
()

agrep - text search tool with support for approximate patterns

sdio ★★★★★
()
Ответ на: комментарий от proud_anon

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

Zubchick
() автор топика

построить индекс по всем вариантам слов (для разных форм одного слова использовать один id) задача сведется к поиску подмножества int-ов

C
()
Ответ на: комментарий от C

да, я так изначально и предполагал, используя pymorphy находить инфинитивы... Но вдруг есть способ попроще? :)

Zubchick
() автор топика
Ответ на: комментарий от Zubchick

>да, я так изначально и предполагал, используя pymorphy находить инфинитивы... Но вдруг есть способ попроще? :)

Если вы оперируете на уровне лексем и не ниже, «алгоритм попроще» для строк максимум в 20 лексем может оказаться писать сложнее, чем профиту будет с него.

Можно разве что какие-нибудь оптимизации провести. Вывести какие-нибудь правила типа «X и Y не могут быть формами одной лексемы, если у них не совпадают первые n символов» и ускорить поиск предварительной проверкой. Но это все мелочи.

Может быть, можно придумать набор простых правил для конкретного словаря/множества слов.

Впрочем, может быть, кто-то и знает более простой способ.

proud_anon ★★★★★
()

Хм.. ну, если я правильно понял, то необходима необходима некая эвристика (тем более, что мера сходства не указана).

Определим меру различия двух слов как минимальное количество операций, которые нужно применить к слову A, чтобы получить слово B. Операции: удалить символ, записать лишний симво, заменить символ на другой.

Для слов A и B считается динамикой значение f(len A, len B):

f(n, k) = min { f(n-1, k) + 1, f(n, k-1) + 1, f(n-1, k-2)*(An==Bk) + (f(n-1, k-2) + 1)*(An!=Bk) }

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

Waterlaz ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.