LINUX.ORG.RU

Алгоритмы распознавания нечеткого ввода текста?


0

1

Юзер вводит слово (напр. название опции). Есть некий набор допустимых значений для того что введено, при этом ввод может быть с ошибкой/сокращениями. Какие алгоритмы используются для распознавания этого дела? Я пока делаю так:

1) если введено одно из допустимых значений - это оно

2) иначе если одно (и только одно) из значений начинается на введенную последовательность это оно

3) иначе если одно и только одно из значений начинается на первый символ введенной последовательности, а остальные введенные символы можно получить выкинув из значения какие то символы, это оно (т.е. скажем для preview допустимы сокращения prw, prv, pie но не допустимо pwv)

иначе ошибка.

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

★★★★★

google «расстояние между словами»

unC0Rr ★★★★★ ()

практичнее будет заменить юзера на неошибающегося :)

Harald ★★★★★ ()

Подсчитать процент совпадающих букв с каждым из возможных вариантов («АА», «АА» - 100% совпадения, «АВ», «АА» - 50%). Затем проверить совпадения порядка следования букв (чем больше буквы идут друг за другом так как в образце - тем лучше. «АБВ», «АВ» - 100% совпадения, «АБВ», «АВБ» - 50%, «АБ», «БА» - 0%). После этого взять то слово из базы, которое обладает наибольшем процентом совпадения.

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

Тока селекцией... ошибся - и током убило. Боюсь правда что я тогда тоже недолго проживу;-)

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

а реализовывать всю эту сабжевую фигню - не затратно ли будет? Такое себе только конторы уровня гугла позволяют )

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

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

AIv ★★★★★ ()

Почему бы не использовать для этого библиотеку спеллчекинга с кастомным словарем?

provaton ★★★★★ ()

Интереснее было бы определять опечатки с учётом раскладки клавиатуры.

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

Почему бы не использовать для этого библиотеку спеллчекинга с кастомным словарем?

Спасибо, интересная мысль.

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

К сожалению не получается... может руки не оттуда растут.

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

AIv ★★★★★ ()

Помню, в прошлом году, на диалоговском APL-контесте одним из заданий было написание нечеткого поиска.

Да, для английского и некоторых других языков есть еще Soundex, для определения омофонов.

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

А причем здесь это вообще О_О???

AIv ★★★★★ ()

одна из канонических задач нейронных сетей

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

>> Системы оптического распознавания текста в Linux - обзор и сравнительное тестирование

И просто похожая тема: Распознавание рукописного текста

причем здесь это вообще О_О???

Действительно, ни при чём. Я думал что ты про распознавание текста.

ZenitharChampion ★★★★★ ()

поле с автокомплитом и словарь опций, не?!
или у тебя уже есть введенные (куда-то) с ошибками слова?

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

поле с автокомплитом и словарь опций, не?!

кстати, самое правильное решение - простое и надежное

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

Поля нету, есть командная строка. Если под автокомплитом понимать readline, то да, это сделано. Речь идет о вводе аргументов в терминале в неинтерактивном режиме, когда что бы реадлайну прокомплитить надо сначала распарсить то, что уже введено (кроме того сокращения могут быть вполне сознательные, что бы команда не занимала 15 строк).

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