Алгоритм — Улучшение исправления орфографии на основе набора букв с похожими формами в Переполнение стека
Я разрабатываю систему коррекции орфографии для неанглийского языка, которая работает на выходе OCR. Я использую очень большие словари, чтобы проверить орфографические ошибки и дать предложения.
Большинство орфографических ошибок происходит из-за букв, которые имеют похожую форму. Например ـجـ , ـچـ , ـحـ , ـخـ или же غ , ع и т. д. Эти буквы существуют также на английском языке, например I, l а также u, v , y,
Система проверки правописания дает некоторые подсказки для слова, которое мы хотим проверить. Например, если мы введем voga это предложит эти слова:
volgabogayogatoga
Поскольку длина voga 4, тогда мы оставим только 4-буквенные предложения. Теперь, потому что механизм OCR может обнаружить v как y (потому что их формы похожи), мы выберем yoga как лучшее предложение для voga как выходной сигнал OCR.
На нашем языке такой выбор очень эффективен. Например, если мы введем مدپر, эти слова будут предложены:
مدارامدارمدیرمراد
На основе наших наборов (в этом примере: ـبـ , ـپـ , ـیـ а также ز , ر , ژ а также ذ , د а также مـ , فـ , قـ) и длина слова, مدیر будет лучшим вариантом для مدپر,
Обычно я использую эту функцию на языке сценариев PHP, чтобы сохранить слова одинаковой длины, которые предлагаются, а затем создать все возможные комбинации неправильно написанного слова, заменив все наборы (например, مدپر, فدپر, قدپر а потом مذپر , فذپر , قذپر и так далее), а затем поиск того же слова в списке предложений. Но этот метод реализации очень медленный (особенно в большом контексте) и делает его практически бесполезным.
Каков наилучший метод или алгоритм для реализации такого рода функций в PHP?
Обновить:
Механизмы, которые создают списки предложений, оптимизированы и обычно включают правильное слово в список предложений. Проблема в том, что моя система должна выбрать одно из предложений в качестве правильного слова без какого-либо искусственного интеллекта. Поэтому я думаю, что этот метод хорош в моем языке, потому что есть много наборов, в которых буквы имеют одинаковую форму, и именно поэтому механизмы OCR обычно неправильно распознают слова. Но если есть лучшие методы, вы можете предложить их.
Решение
Я все еще думаю, что этот вопрос слишком широк, чтобы задавать его здесь. Мне все еще кажется, что вы понятия не имеете, как это сделать, поэтому вам не следует спрашивать о решении PHP. На мой взгляд, этот вопрос в первую очередь об алгоритмическом решении, а не о программировании или реализации. Я уверен, что существует много разных решений, и, поскольку несколько лет назад мы провели научное исследование в этой области, я собираюсь предложить одно решение, которое позволит вам понять, как вы можете это сделать.
Допустим, у вас есть «слово OCR», которое недопустимо, и вы хотите выбрать лучшее действительное слово, чтобы заменить его из своего словаря действительных слов.
-
Начните со стандартного алгоритма предложения. Таким образом, вы получите несколько слов-кандидатов.
-
Теперь вычислите «расстояние» этих слов до слова OCR.
-
Используйте кандидата с минимальным вычисленным расстоянием.
Вопрос теперь в том, как вычислить расстояние двух слов. Вы можете начать с Расстояние Хемминга — но этот классический алгоритм недостаточно хорош для вашей ситуации, и он не будет делать больше, чем вы уже получили на шаге 1, поэтому вам нужно сделать что-то более подходящее для вас. Проще говоря, вы хотите дать некоторый бонус за аналогичные символы / буквы. Мы использовали нечеткие автоматы, чтобы решить ту же самую ситуацию для анализа ДНК. Было бы слишком долго писать полный алгоритм здесь, поэтому, пожалуйста, посмотрите на наша газета если вам нужно больше информации. (Ссылка идет на репозиторий Researchgate.)
Вы также можете полностью пропустить шаг 1 и создать глобальную поисковую систему для похожих слов со сходством, что также описано в нашей статье. Я бы проголосовал за этот глобальный подход.
Другие решения
Других решений пока нет …