Это хороший случай для лучшего пути Витерби?

Question

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

В любой данной книге моя функция будет определять от 1 до 100 потенциальных последовательностей. Многие из последовательностей, которые он идентифицирует, являются ненужными... совершенно бесполезными. Однако остальные обычно являются подмножествами основных последовательностей, которые могут быть сшиты вместе для формирования более полной последовательности. Это моя проблема: как мне их сшить? Мой вывод на данный момент выглядит примерно так:

 Index: 185 PNUM: 158   
 Index: 186 PNUM: 159   
 Index: 187 PNUM: 160   
 Index: 188 PNUM: 161   
 Index: 189 PNUM: 162   
 Index: -1 PNUM: blank   
 Index: -1 PNUM: blank   
 -------------------------------------------------
 Index: 163 PNUM: 134   
 Index: 164 PNUM: 135   
 Index: -1 PNUM: blank   
-------------------------------------------------
 Index: 191 PNUM: 166   
 Index: 192 PNUM: 167   
 Index: 193 PNUM: 168   
 Index: 194 PNUM: 169   

Индекс - это количество страниц с обложки книги, включая все те авторские права, самоотверженность, страницы содержания, которые традиционно не пронумерованы. PNUM - это номер страницы, которую обнаружил мой alg. Здесь мы видим три разных последовательности, верх и низ которых должны быть сшиты вместе. Как вы заметите, смещение между индексом и pnum для верхней последовательности равно 27, а смещение для нижней последовательности - 25. Наиболее распространенной причиной разницы между смещением является либо отсутствующая страница, либо страница, которая была отсканировано дважды.

Мне предложили использовать алгоритм наилучшего пути Витерби для сшивания этих последовательностей, но мне это кажется излишним, так как мне действительно нужно только сшивать свои последовательности, а не подтверждать их точность. Я действительно понятия не имею, куда идти с этим, и я очень ценю любую помощь. Спасибо!

Answer 1

Витерби

Да, Витерби сработает, с небольшим перебором, но потом даст вам большую гибкость, чтобы компенсировать проблемы с распознаванием текста, отсутствием страниц, дубликатами и т. Д.

Если вы возьмете псевдокод Википедии, ваша проблема может быть переформулирована как

//this is the actual hidden variable you're trying to guess
states = ('i', 'ii', 'iii', 'iv', ...., '1','2','3' ....)

//what OCR will give you, a 98% accurate view of state
//blank is for when there is no page number
//other is for an OCR result you didn't anticipate, such as 'f413dsaf'
possible_observations = (blank,other, 'i','ii','iii','iv',...,'1','2','3'...)

//the probability distribution of states for the first page
//must sum to 1.0
start_probability = {'i': 0.2, '1':0.5, all the rest: (1-0.7)/numOtherStates}

//the probability that the state '2' is found after '1'
//let's put a 0.05 percent chance of duplicate
//and put a very small probability of getting somewhere random
transition_probability = {
'i' : {'ii':0.8,'1':0.1,'i':0.05,allOthers: 0.05/numOtherStates},
'1' : {'2': 0.9, '1': 0.05, allOthers: 0.05/numOtherStates}
//etc
}

//that's the probability of what you OCR will see given the true state
//for the true page '1', there's 95% percent chance the OCR will see '1', 1% it will see    
//'i', 3% it will see a blank, and 0.01%/otherObservation that it will OCR something else
//you can use some string distance for that one (Levenshtein etc...)
emission_probability = {
'1' : {'1': 0.95, 'i': 0.01, blank: 0.03, otherObservations: (0.01)/numObservations},
'2' : {'2': 0.95, 'z': 0.01, blank: 0.03, otherObservations: (0.01)/numObservations},
}

observations = for i = 1 to maxINDEX {PNUM[INDEX]}

Другая возможность: использовать расстояние Левенштейна

Поместите все номера страниц последовательно снова в массив {PNUM[INDEX=0], PNUM[INDEX=1], ...} и попробуйте сопоставить его с 1, 2, 3, ... MAX(PNUM). При вычислении расстояния алгоритм Левенштейна будет вставлять изменения (удаляет, вставляет, изменение страницы). Если вы закодируете это, чтобы показать эти изменения, у вас должно быть что-то приличное.