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

Question

Интересно, если в Perl/MySQL, если возможно построить список вариантов слов на основе заданного слова, к которому слово может иметь общие ошибки OCR (т.е. 8 вместо b)? Другими словами, если у меня есть список слов, и в этом списке есть слово «Алфавит», то есть способ расширить или построить новый список, чтобы включить мое исходное слово плюс варианты ошибок OCR «Алфавит»? Так что в моем выходе, я мог бы иметь следующие варианты для алфавита, возможно:

Alphabet 
A1phabet 
Alpha8et 
A1pha8et 

Конечно, было бы полезно для кода для большинства, если не всех общих иных ошибок, которые появляются в OCR'ed тексте. Такие вещи, как 8 вместо b, или 1 вместо l. Я не хочу исправлять ошибки, потому что в моих данных я мог бы иметь ошибки OCR, но хочу создать вариантный список слов в качестве моего вывода, основанный на списке слов, которые я даю ему как вход. Поэтому, по моим данным, у меня может быть Alpha8et, но если я сделаю простой поиск алфавита, он не найдет этой очевидной ошибки.

Мой быстрый и грязный подход MySQL

Select * from 
(SELECT Word 
FROM words 
union all 
-- Rule 1 (8 instead of b) 
SELECT 
case 
    when Word regexp 'b|B' = 1 
     then replace(replace(Word, 'B','8'),'b','8') 
    end as Word 
FROM words 
union all 
-- Rule 2 (1 instead of l) 
SELECT 
case 
    when Word regexp 'l|L' = 1 
     then replace(replace(Word, 'L','1'),'l','1') 
    end as Word 
FROM words) qry 
where qry.Word is not null 
order by qry.Word; 

Я думаю, что должно быть более автоматизированный и чистым методом

Answer 1

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

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

Этот пример, в Ruby, показывает рекурсивную функцию.Сбор нужных ошибок может занять вас:

VARIATIONS = { 
    'l' => ['1'], 
    'b' => ['8'], 
} 

def variations(word) 
    return [''] if word.empty? 
    first_character = word[0..0] 
    remainder = word[1..-1] 
    possible_first_characters = 
    [first_character] | VARIATIONS.fetch(first_character, []) 
    possible_remainders = variations(remainder) 
    possible_first_characters.product(possible_remainders).map(&:join) 
end 

p variations('Alphabet') 
# => ["Alphabet", "Alpha8et", "A1phabet", "A1pha8et"] 

Оригинальное слово включено в список вариантов. Если вы хотите только возможного MIS-сканирования, а затем удалить исходное слово:

def misscans(word) 
    variations(word) - [word] 
end 

p misscans('Alphabet') 
# => ["Alpha8et", "A1phabet", "A1pha8et"] 

---

Быстрой и грязная (и непроверенная) версия программы командной строки будет пара вышеуказанных функций с эта «основная» функция:

input_path, output_path = ARGV 
File.open(input_path, 'r') do |infile| 
    File.open(output_path, 'w') do |outfile| 
    while word = infile.gets 
     outfile.puts misscans(word) 
    end 
    end 
end 

Answer 2

Эффективным способом для достижения этой цели является использование bitap algorithm. Perl имеет re::engine::TRE, привязку к libtre, которая реализует нечеткое соответствие строки в регулярном выражении:

use strict; 
use warnings qw(all); 
use re::engine::TRE max_cost => 1; 

# match "Perl" 
if ("A pearl is a hard object produced..." =~ /\(Perl\)/i) { 
    say $1; # find "pearl" 
} 

Плюс, есть agrep инструмента, который позволяет использовать libtre из командной строки:

$ agrep -i -E 1 peArl * 
fork.pl:#!/usr/bin/env perl 
geo.pl:#!/usr/bin/env perl 
leak.pl:#!/usr/local/bin/perl 

Когда ты необходимо сопоставить несколько слов с текстом OCRized, есть два разных подхода.

Вы можете просто создать один регулярному_выражению со всем словарем, если он достаточно мал:

/(Arakanese|Nelumbium|additionary|archarios|corbeil|golee|layer|reinstill\)/ 

Большого словарем запросы могут быть оптимизированы путем создания индекса триграммы. Perl имеет String::Trigram для выполнения этого в памяти. Несколько СУРБД также имеют расширения индекса триграмм. PostgreSQL приправленный pg_trgm позволяет писать запросы, как это, которые достаточно быстро, даже для очень больших словарей:

SELECT DISTINCT street, similarity(street, word) 
    FROM address_street 
    JOIN (
     SELECT UNNEST(ARRAY['higienopolis','lapa','morumbi']) AS word 
    ) AS t0 ON street % word; 

(это один взял ~ 70ms на столе с ~ 150К строк)