![]() |
|
![]() ![]() ![]() |
|
blackbanny |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 83 Регистрация: 18.11.2009 Репутация: нет Всего: нет |
Доброго времени суток!
Имеется список слов и некий получаемый текст. Нужно перебирать список слов и искать эти слова в получаемом тексте. Проблема в том, что получаемый текст может приходить с ошибками, например, в словаре есть такое слово "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 " пробелы в получаемом тексте скорее всего нужно будет убрать(это делается просто стандартными функциями языка), а вот как действовать дальше? |
|||
|
||||
mrgloom |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 829 Регистрация: 8.6.2011 Репутация: нет Всего: нет |
кстати меня тоже интересует данный вопрос, я так понимаю тут разговор идёт об OCR.
вроде как есть какие то техники, которые позволяют сдетектировать фразу например из N букв, но во-первых мы можем иметь ошибки в определении самих букв, т.е. по правильному мы должны иметь лишь вероятность нахождения буквы на k-ой позиции, а потом перебирая все варианты должны получить "осмысленное" слово из словаря. вообщем должна быть какая то вероятностная модель по идее. |
|||
|
||||
blackbanny |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 83 Регистрация: 18.11.2009 Репутация: нет Всего: нет |
именно, а точнее о результате распознавания. с нем и нужно проводить манипуляции. ну из-за ошибок в распознавании я и задал вопрос... что-то проверять по позиции в моем случае не получится, потому что слова могут располагаться в разных частях текста... |
|||
|
||||
Pavia |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 418 Регистрация: 6.12.2008 Репутация: 11 Всего: 12 |
Думаю с такими ошибками лучше всего справится Левенштейн. Можно попробовать собрать статистику ошибок и улучшить алгоритм, но сомневаюсь что это даст прирост более 1/1000. Тут надо улучшать обработку перед OCR. А так совет один трудитесь. Чем больше придумаете тем лучше будет. |
|||
|
||||
mrgloom |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 829 Регистрация: 8.6.2011 Репутация: нет Всего: нет |
ну тогда видимо пробегать по фразе словом из словаря и смотреть насколько совпадает. |
|||
|
||||
blackbanny |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 83 Регистрация: 18.11.2009 Репутация: нет Всего: нет |
||||
|
||||
mrgloom |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 829 Регистрация: 8.6.2011 Репутация: нет Всего: нет |
по-моему это называется Approximate string matching
http://en.wikipedia.org/wiki/Approximate_string_matching расстояние Левенштейна это видимо один из методов. |
|||
|
||||
Albor |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 589 Регистрация: 28.2.2009 Репутация: нет Всего: 9 |
С помощью алгоритма Левенштейна можно вычислить не только расстояние, но и места ошибок. Когда-то тестировал данный алгоритм на предмет написания диктантов по русскому языку. Если интересно - выложу. Программка сравнивает два небольших текста с определением местоположения ошибок. Это сообщение отредактировал(а) Albor - 19.7.2013, 07:18 Присоединённый файл ( Кол-во скачиваний: 3 ) ![]() |
|||
|
||||
blackbanny |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 83 Регистрация: 18.11.2009 Репутация: нет Всего: нет |
конечно интересно, было бы интересно посмотреть
![]() |
|||
|
||||
Albor |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 589 Регистрация: 28.2.2009 Репутация: нет Всего: 9 |
||||
|
||||
blackbanny |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 83 Регистрация: 18.11.2009 Репутация: нет Всего: нет |
спасибо) посмотрел результат работы, вполне отлично)
Эталонная строка: BORDEAUX Проверяемая строка: ")RDEAUXCHATEAUl'Estang ¦'ISDECASTILLOSotcastilio*con2008" Результат проверки: ~~RDEAUX************************************************** т.е. получается 6 из 8 или 75% а не могли бы привести код метода для проверки? |
|||
|
||||
Albor |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 589 Регистрация: 28.2.2009 Репутация: нет Всего: 9 |
Вечерком выложу
|
|||
|
||||
Albor |
|
||||||||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 589 Регистрация: 28.2.2009 Репутация: нет Всего: 9 |
Сначала таблица для обеспечения работы алгоритма:
Реализация:
Собственно сам алгоритм:
И его использование:
|
||||||||
|
|||||||||
blackbanny |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 83 Регистрация: 18.11.2009 Репутация: нет Всего: нет |
большое спасибо за код)
есть небольшой вопрос... Суть в следующем: Эталонная строка: 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********************************************, что вполне корректно и ожидаемо ![]() С чем может быть связана данная проблема? Есть ли какой-нибудь путь для ее обхода? |
|||
|
||||
Albor |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 589 Регистрация: 28.2.2009 Репутация: нет Всего: 9 |
Вполне вероятно, что у меня в программке есть незамеченные проблемы, это всё делалось на скорую руку и не проходило должного тестирования. Для меня было важнее на тот момент определиться, возможно ли решить задачу проверки текста на ошибки, но, в дальнейшем, данный функционал не потребовался и так и остался в виде теста. Попробую посмотреть в отладчике что к чему, но быстро не обещаю, так как свободного времени не очень много.
|
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |