Как определить вхождение слова в текст, допуская незначительные грам. ошибки в нем?

Question

[Никита Каменев]

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

Пример:
Есть текст:

Какая стоимасть у этого товара?

Алгоритм должен распознать это слово, при условии что в ключевых словах есть слово стоимость.

Сейчас всё это дело реализовано так:
1. Разбиваю текст на слова
2. Для каждого слова считаю расстояние Левенштейна от списка ключевых слов
3. Если расстояние не больше двух - это слово присутствует.

Comments

[sim3x]

Почему текущий вариант тебя не устраивает?

Тебе нужно подумать о метриках качества - полнота и точность
Тк дальше тебе нужно думать про машобучение и/или експертную систему

Answer 1

[xmoonlight]

1. Пересечение множеств и сегментация цепочек данных.
(Левенштейн - полностью нерабочий вариант в данном случае)
2. Правила для автогенерации возможных ошибок/очепяток, дубликаты согласных, раскладки клавиатуры: а:о, и:е, е:ё, ц:й:у:ф:ы:в, п:а:р:к:е:н:м:и:т, и т.д.
3. Словарь синонимов по ключевикам
4. Словоформы

PS: пишите чат-бота-консультанта для интернет-магазина?)

Comments

[Никита Каменев]

Человек, который пишет сообщение, так же может нажать не на ту букву или вообще упустить одну из, что не редкость. Что-то вроде "какова стоимось товара?" - словарь ошибок не панацея.

[xmoonlight]

Никита Каменев: тут пересечение множеств и процент совпадения должны спасти ситуацию (п.1)

Answer 2

[Виктор Обен]

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

Answer 3

[lega]

Есть такой алгоритм (не помню названия):
Слово (или все предложение) формируют группы по 3 символа (или 4),
"стоимость" -> {__с, _ст_ сто, тои, оим, имо, мос, ост, сть, ть_, ь__}
В итоге когда будем искать пересечения (set & set) с ошибочным словом "стоимасть" -> {__с, _ст, ... }, мы получим 8 из 11 совпадений, а вообще если прогнать по всем ключевым словам и отсортировать результаты по релевантности то мы получим "стоимость" на первом месте как самое близкое слово.

Так же тут можно использовать обратный индекс и по слову находить тексты (включая те слова с ошибками).