Как удалить OCR артефакты из текста?

Question

Сгенерированные OCR тексты иногда поставляются с такими артефактами, как этот:

Diese grundsätzliche V erborgenheit Gottes, die sich nur dem N achfolger öffnet, ist mitdem Messiasgeheimnis gemeint

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

Как можно превратить вышеприведенный текст в более, скажем, каноническую форму, например:

Diese grundsätzliche Verborgenheit Gottes, die sich nur dem Nachfolger öffnet, ist mit dem Messiasgeheimnis gemeint

Можно ли сделать это эффективно для больших объемов текста?

---

Одна идея состоит в том, чтобы объединить всю строку (чтобы пропустить догадки, где границы слов), а затем запустить алгоритм сегментации текста на нем, может быть что-то похожее на это: http://norvig.com/ngrams/

Answer 1

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

Единственная реальная трудность с такими строками m i t d e m которые соответствуют двум или более отдельным словам. Простой способ состоит в том, чтобы жадно "откусывать" префиксы, которые появляются в словаре, но это может привести к неоптимальным результатам, в частности к суффиксу, который не соответствует ни одной строке словаря, даже если другой выбор точек останова будет иметь работал (например, b e i m A r z t не сработает, если вы будете жадно хвататься bei вместо beim с фронта). К счастью, существует простой подход DP с линейным временем, который будет работать лучше и даже может включать весовые коэффициенты для слов, которые могут помочь получить наиболее вероятную декомпозицию в случае, если их несколько. Для заданной строки S[1 .. n] (без удаленных пробелов) мы вычислим f (i), оценку лучшего разложения префикса length-i для S, для всех 1 <= i <= n:

f(0) = 0
f(i) = max over all 0 <= j < i of f(j) + dictScore(S[j+1 .. i])

Тогда f(n) будет баллом наилучшего возможного разложения всей строки. Если вы установите dictScore(T) равным 1 для слов, которые существуют в словаре, и 0 для слов, которые не существуют, вы получите разложение на максимально возможное количество слов; если вы установите dictScore(T), например, -1 для слов, которые существуют в словаре, и -2 для слов, которые не существуют, вы получите разложение на как можно меньшее количество слов. Вы также можете выбрать более высокие оценки для более "вероятных" слов.

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