Поиск подстроки с учетом допустимых искажений в OCR-распознанном тексте

Delphi , Базы данных , Поиск

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

Проблема

Представим, что у нас есть текст, полученный в результате OCR-распознавания, и нам необходимо найти в нем подстроку, допуская некоторое количество ошибок. Например:

• Текст: 9912, 1.What is your name?
• Подстрока: 1. What is your name?
• Допуск: 1 ошибка

• Ожидаемый результат: соответствие начинается с 7-го символа

• Текст: Where is our caat if any?

• Подстрока: your cat
• Допуск: 2 ошибки

• Ожидаемый результат: соответствие начинается с 10-го символа

• Текст: Tolerance is t0o h1gh.

• Подстрока: Tolerance is too high;
• Допуск: 1 ошибка
• Ожидаемый результат: соответствие не найдено

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

Решение

Для решения этой задачи можно использовать рекурсивный алгоритм, который может не быть достаточно быстрым, особенно в случае, когда соответствие не найдено и алгоритм вынужден проверять все возможные варианты. Однако, если подстрока и допуск имеют постоянную длину, алгоритм можно считать линейным по времени выполнения.

Вот пример реализации на Object Pascal (Delphi):

function BrouteFindFirst(What, Where: string; Tolerance: Integer; var AtIndex, OfLength: Integer): Boolean;
// ... (реализация функции BrouteFindFirst)

Используя данную функцию, можно выполнить поиск подстроки с учетом допустимых искажений. Например, для текста Where is our caat if any? и подстроки your cat с допуском в 2 ошибки, функция вернет соответствие, начиная с 9-го символа, длиной в 6 символов.

Альтернативный ответ

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

Заключение

В данной статье мы рассмотрели проблему поиска подстроки с допустимыми искажениями в тексте, полученном в результате OCR-распознавания, и предложили рекурсивный алгоритм на Object Pascal. Также был представлен альтернативный источник с готовым решением для приближенного поиска. Использование таких алгоритмов позволяет значительно повысить точность и эффективность обработки текстов, содержащих ошибки OCR.

Создано по материалам из источника по ссылке.

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

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Поиск ::