这是维特比最佳路径藻类的好案例吗？

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是我的算法检测到的页码。这里我们可以看到三个不同的序列，顶部和底部应该缝合在一起。正如您将注意到的，顶部序列的索引和pnum之间的偏移量是27，而底部序列的偏移量是25。造成偏移量差异的最常见原因要么是缺页，要么是扫描了两次的页。

有人建议我使用Viterbi最佳路径算法将这些序列拼接在一起，但这对我来说似乎有点过分，因为我真的只需要将序列拼接在一起，而不需要确认它们的准确性。我真的不知道该去哪里，我非常感谢任何帮助。谢谢!

Answer 1

Viterbi

是的，Viterbi会工作，稍微有点过度，但会给你很多灵活性，弥补OCR问题，缺页，重复，等等…

如果你用维基百科的伪代码，你的问题可以被重新表述为

//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]}

其他可能:使用levenshtein distance

将所有页码依次放入数组{PNUM[INDEX=0]， PNUM[INDEX=1]，…}并尝试将其与1,2,3，…马克斯(PNUM)。在计算距离时，levenshtein算法将插入更改(删除、插入、页面更改)。如果您编写代码来显示这些更改，那么您也应该有一些像样的东西。