Доброго времени суток!
Имеется список слов и некий получаемый текст. Нужно перебирать список слов и искать эти слова в получаемом тексте. Проблема в том, что получаемый текст может приходить с ошибками, например, в словаре есть такое слово "DEL'ESTANG", а в тексте только "'ESLANG". С помощью какого алгоритма можно с наибольшей долей вероятности определить, что слово "DEL'ESTANG" изначально было в тексте? Подойдет ли алгоритм расстояние Левенштейна или есть более эффективные алгоритмы? Может есть готовые легковесные библиотеки?

Добавлено через 7 минут и 48 секунд
или вот еще такой пример:
в словаре есть слово "BORDEAUX"
получаемый текст следующий ") R D E A UX CHATEAU l'Estang ■'IS DE CASTILLOS ot castilio*con 2 00 8 "
пробелы в получаемом тексте скорее всего нужно будет убрать(это делается просто стандартными функциями языка), а вот как действовать дальше? 

кстати меня тоже интересует данный вопрос, я так понимаю тут разговор идёт об OCR.


вроде как есть какие то техники, которые позволяют сдетектировать фразу например из N букв, но во-первых мы можем иметь ошибки в определении самих букв, т.е. по правильному мы должны иметь лишь вероятность нахождения буквы на k-ой позиции, а потом перебирая все варианты должны получить "осмысленное" слово из словаря.

вообщем должна быть какая то вероятностная модель по идее. 

именно, а точнее о результате распознавания. с нем и нужно проводить манипуляции.

ну из-за ошибок в распознавании я и задал вопрос...

что-то проверять по позиции в моем случае не получится, потому что слова могут располагаться в разных частях текста...

Думаю с такими ошибками лучше всего справится Левенштейн. Можно попробовать собрать статистику ошибок и улучшить алгоритм, но сомневаюсь что это даст прирост более 1/1000.
Тут надо улучшать обработку перед OCR.
А так совет один трудитесь. Чем больше придумаете тем лучше будет.

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

с помощью какого алгоритма можно узнать насколько совпадает?

по-моему это называется Approximate string matching
http://en.wikipedia.org/wiki/Approximate_string_matching

расстояние Левенштейна  это видимо один из методов.

С помощью алгоритма Левенштейна можно вычислить не только расстояние, но и места ошибок. Когда-то тестировал данный алгоритм на предмет написания диктантов по русскому языку. Если интересно - выложу. Программка сравнивает два небольших текста с определением местоположения ошибок. 

Это сообщение отредактировал(а) Albor - 19.7.2013, 07:18

Присоединённый файл ( Кол-во скачиваний: 3 )
 tesst.rar 96,12 Kb

конечно интересно, было бы интересно посмотреть 

Присоединил к предыдущему сообщению, иначе почему-то не отправлялось.

спасибо) посмотрел результат работы, вполне отлично)
Эталонная строка: BORDEAUX
Проверяемая строка: ")RDEAUXCHATEAUl'Estang ¦'ISDECASTILLOSotcastilio*con2008"
Результат проверки: ~~RDEAUX**************************************************
т.е. получается 6 из 8 или 75%

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

Вечерком выложу

Сначала таблица для обеспечения работы алгоритма:

Реализация:


Собственно сам алгоритм:


И его использование:

большое спасибо за код)
есть небольшой вопрос...
Суть в следующем:
Эталонная строка: bordeaux

Проверяемая строка: <?)rdeaux??b1??i?hi??chateau?d£l'estang?11sdecastillo*?\t1'isdecastluo*c0,‘?2008?‘zszvssx****'?%?•0oironocrh*\ta??4^••ooiponot-?\t\t?•o-oi**\"1?vo,oc

Результат:***********b****************************************o~*******de*a***u*******************x************************************************************

Если проверяемую строку укоротить, например, до такой <?)rdeaux??b1??i?hi??chateau?d£l'estang?11sdecastillo, то результат будет таким ~~*rdeaux********************************************, что вполне корректно и ожидаемо 

С чем может быть связана данная проблема? Есть ли какой-нибудь путь для ее обхода?

Вполне вероятно, что у меня в программке есть незамеченные проблемы, это всё делалось на скорую руку и не проходило должного тестирования. Для меня было важнее на тот момент определиться, возможно ли решить задачу проверки текста на ошибки, но, в дальнейшем, данный функционал не потребовался и так и остался в виде теста. Попробую посмотреть в отладчике что к чему, но быстро не обещаю, так как свободного времени не очень много.

буду очень благодарен)

blackbanny, посмотрите эту статью, возможно в ней вы найдёте путь к решению (а может и решение) вашей задачи.

Всё верно, согласно алгоритму Левенштейна именно таким результат и должен быть. Дело в том, что чтобы найти места ошибок, нужно пройтись по построенной таблице обратно от итоговой ячейки содержащей расстояние, поэтому в итоговую строку попадают символы проверяемой строки в обратном порядке. Под вашу задачу это не совсем подходит - нужно дорабатывать анализ полученной таблицы, используя не только результирующую ячейку, но и промежуточные, пока не получится самый оптимальный вариант с минимумом операций редактирования. 

Это сообщение отредактировал(а) Albor - 29.7.2013, 08:08

Видимо всё значительно проще. Вот составил таблицу несколько упрощённого вашего теста

Здесь видно, что для решения задачи нужно найти минимальное значение (либо несколько значений удовлетворяющих допустимому количеству ошибок) в последней колонке матрицы и, если нужно, то вычислить ошибки, либо обозначить диапазон подстрок(и), удовлетворяющих поиску.  
Добавлено:
Поторопился я с выводом, не всё так просто, чтобы в этом убедиться, нужно в вертикальную строку добавить текст строки для поиска, т.е. создать периодичность текста, тогда становится очевидным, что минимальным значением в последней колонке не отделаешься. 

Это сообщение отредактировал(а) Albor - 30.7.2013, 07:55