基于字典的关键词检测

Question

我想从可能存在OCR错误的扫描文档中识别关键字。基于扫描文档的每个字符及其备选字符的关键字和置信度值的列表，我如何开发一种算法来可靠地识别关键字？

对于OCR，我使用的是Tesseract，它为每个字符及其最佳备选字符提供置信度。因此，对于每个单词，我都有一个这样的列表：

 Word=order
 [0] o (93%) [alts: 0 (90%), c (83%), e (82%)]
 [1] r (96%)
 [2] d (96%)
 [3] e (90%) [alts: a (75%)]
 [4] r (95%) 

另一个包含OCR错误的示例：

 Word=PaYmeHI (Payment would be correct)
 [0] P (81%) [alts: p (78%), D (68%)]
 [1] a (76%) [alts: 3 (73%), e (63%), ö (61%)]
 [2] Y (87%) [alts: V (86%)]
 [3] m (83%) 
 [4] E (71%) [alts: € (79%), 9 (72%), % (67%), e (65%), B (64%), G (64%)]
 [5] H (76%) [alts: n (83%), D (74%), N (70%), ü (69%)]
 [6] I (75%) [alts: t (69%), { (67%), 1 (65%), i (61%)]

如你所见，tesseract并不总是选择百分比最高的结果(4，5)。

从浏览结果看，大多数值在90%以上的字符都是正确的。但是，不好的结果不一定在备选列表中包含正确的字符(请参见2，它应该是小写的y。

目前，我正在使用Levenshtein距离和字符串长度获取候选列表。此外，我排除了lev2 > 3的关键字。这只是硬编码，因为我仍在寻找确定阈值的好方法。

      int lev = getLevenshteinDistance(keyword, s);
      int lev2 = getLevenshteinDistance(keyword.toLower(), s.toLower());
      int len = Math.abs(keyword.length - s.length); 
      int x = lev + lev2 + len;

我正在按x对关键字列表进行排序，以获得最可能的结果。

因此，首先，我正在寻找一种方法来根据OCR结果和字符串长度确定一个好的阈值。较短的字符串需要比较大的字符串更低的阈值，并且需要可靠的OCR结果。以上面的例子为例:对于词序lev2 <= 1，就足够了，而对于payment，至少应该计算lev2 <= 3。

其次，我如何确定剩下的候选人中是否有一个确实与该单词匹配？在lev == 0的情况下，当所有字符的置信度为>= 90时，这是显而易见的。但是考虑到糟糕的OCR结果，我可以开发什么算法来同时包含其他OCR选择？

Answer 1

我一直在为我的一个项目考虑类似的东西；我还没有得到任何好的答案，但这里有一些想法：

我认为我们试图回答的问题是：

此文档( OCR结果)是否包含术语“订单”？

Idea 1

OCR文档包含带有某些“分数”的术语...

因此，在您的示例中，文档包含：

• order with sum( 93 ,96,96,90,95)/5 = 94
• 0rder with score = sum(90,96,96,90,95)/5 =93
• crder with score = sum(83,96,96,90,95)/5 = 92
• erder with score = sum(82,96,96,90,95)/5 = 91
• ordar with score = sum(93,96,96,75,95)/5 = 91

H113ordar with score = sum(90,96,96,75,95)/5 = 90

• crdar score = sum(83,96,96,75,95)/5 = 89 16HH2117erdar with =sum(90，96，96，75，95)/5=88

现在我们有了每个候选人的分数，我们可以在给定一些查询的情况下获得文档的分数(现在使用levenshtein距离...)

文档中给定关键字"order“的得分是

• (3-min(lev(order，order),3)*0.33) * 94，
• (3-min(lev(0rder，order),3)*0.33) * 93，
• (3-min(lev(crder，order),3)*0.33) * 92，
• ...，
• ...

如果这个分数高于某个阈值，则文档被认为匹配“order”。

Idea 2

我们可以使用一些语言模型来改善OCR结果

计算每个术语的分数，如下所示：

term        | ocr_score   |ngram score            |combined score
------------+-------------+-----------------------+---------------
order   | 94          |score(ord, rde, der)   |ocr*ngram
0rder   | 93          |score(0rd, rde, der)   |ocr*ngram
crder   | 92          |score(crd, rde, der)   |ocr*ngram
erder   | 91          |score(erd, rde, der)   |...
ordar   | 91          |score(ord, rda, der)   |...
0rdar   | 90          |score(0rd, rda, der)   |...
crdar   | 89          |score(crd, rda, der)   |...
erdar   | 88          |score(erd, rda, der)   |...

其中score(ord) = 'ord‘的三元概率

例如，谷歌图书给出了任何三元组的三元组概率(参见：http://books.google.com/ngrams/chart?content=ord&corpus=0&smoothing=3&year_start=1970&year_end=2000)

我们还可以计算一元语法、二元语法、四元语法…；然后我们可以根据单词本身的“一元语法”概率计算分数；单词的二元语法等等；然后我们还可以应用一些纯分析语言模型。

因此，我们现在对每个“候选术语”有了更多的分数，并将它们与每个分数的一些权重进行组合，以获得该术语的组合分数。

Idea 3

好的，上面的结果导致了术语/分数的爆炸性增长……这是计算密集型的；所以我们使用一些魔法，根据想法1和2为每个术语构建一个概率DFA。文档现在包含概率DFA而不是术语。Lucene的人已经做了一些工作来构建Levenshtein DFAs，并允许检查DFA1和DFA2是否快速匹配……

Answer 2

首先，我认为你的程序给你的是P(观察|符号)，而不是P(符号|观察)。P(符号|观察)\比例P(观察|符号)*P(符号)。

例如，对于支付中的e，虽然对于欧元，观察到的模式给出符号的概率最高，但观察到欧元的概率很小。因此，它最有可能是'e'，而不是欧元。

因此，我的建议是对所有可能的单词求和log( P(观察值|符号)*P(符号))，并选择最大化该值的单词。

此外，与使用P(符号)相比，您可以通过使用上下文来使用更精确的估计。