5

我在 OCR 之后使用 Levenshtein 距离来查找类似的字符串。但是，对于某些字符串，编辑距离是相同的，尽管视觉外观明显不同。

例如，字符串Co将返回这些匹配项：

CY (1)
CZ (1)
Ca (1)

考虑到，这Co是来自 OCR 引擎的结果，它Ca比那些更可能匹配。因此，在计算完 Levenshtein 距离之后，我想通过视觉相似度排序来优化查询结果。为了计算这种相似性，我想使用标准的无衬线字体，比如 Arial。

有没有我可以用于此目的的库，或者我如何自己实现它？或者，是否有任何比 Levenshtein 距离更准确的字符串相似性算法，我可以另外使用？

4

3 回答 3

5

如果您正在寻找一个允许您根据视觉相似性计算各种“替换成本”的表格，那么我一直在寻找这样的东西但收效甚微，所以我开始将它视为一个新的问题。我没有使用 OCR，但我正在寻找一种方法来限制在概率搜索中对错误输入字符的搜索参数。由于人类在视觉上混淆了字符，因此它们被错误输入，同样的原则应该适用于您。

我的方法是根据 8 位字段中的笔画成分对字母进行分类。这些位是，从左到右：

7: Left Vertical
6: Center Vertical
5: Right Vertical
4: Top Horizontal
3: Middle Horizontal
2: Bottom Horizontal
1: Top-left to bottom-right stroke
0: Bottom-left to top-right stroke

对于小写字符，左侧的下降线记录在位 1 中，右侧的下降线记录在位 0 中，作为对角线。

通过该方案，我提出了以下值，这些值试图根据视觉相似性对字符进行排名。

m:               11110000: F0
g:               10111101: BD
S,B,G,a,e,s:     10111100: BC
R,p:             10111010: BA
q:               10111001: B9
P:               10111000: B8
Q:               10110110: B6
D,O,o:           10110100: B4
n:               10110000: B0
b,h,d:           10101100: AC
H:               10101000: A8
U,u:             10100100: A4
M,W,w:           10100011: A3
N:               10100010: A2
E:               10011100: 9C
F,f:             10011000: 98
C,c:             10010100: 94
r:               10010000: 90
L:               10000100: 84
K,k:             10000011: 83
T:               01010000: 50
t:               01001000: 48
J,j:             01000100: 44
Y:               01000011: 43
I,l,i:           01000000: 40
Z,z:             00010101: 15
A:               00001011: 0B
y:               00000101: 05
V,v,X,x:         00000011: 03

就目前而言，这对于我的目的来说太原始​​了，需要更多的工作。但是，您也许可以使用它，或者根据您的目的对其进行调整。该方案相当简单。此排名适用于等宽字体。如果您使用的是 sans-serif 字体，那么您可能需要重新处理这些值。

该表是一个混合表，包括所有字符，小写和大写，但如果将其拆分为仅大写和仅小写，它可能会更有效，并且还允许应用特定的大小写惩罚。

请记住，这是早期的实验。如果您看到改进它的方法（例如通过更改位序列），请随时这样做。

于 2012-05-17T18:21:39.563 回答
2

因此，在您的距离函数中，替换不同字符对的成本不同。

也就是说，与其添加一个或两个不考虑所涉及字符的集合成本的替换 - 而是具有一个替换成本函数，该函数返回介于 0.0 和 2.0 之间的值，用于在某些上下文中替换某些字符的成本。

在记忆的每一步，只需调用这个成本函数：

cost[x][y] = min(
    cost[x-1][y] + 1, // insert
    cost[x][y-1] + 1, // delete,
    cost[x-1][y-1] + cost_to_replace(a[x],b[y]) // replace
);

这是我的完整编辑距离实现，只需将 replace_cost 常量交换为 replace_cost 函数，如下所示：

https://codereview.stackexchange.com/questions/10130/edit-distance-between-two-strings

在实现 cost_to_replace 函数方面，您需要一个字符矩阵，其成本基于字符的相似程度。可能会有这样的表格浮动，或者您可以通过将每对字符写入一对图像然后使用标准视觉技术比较图像的相似性来自己实现它。

或者，您可以使用有监督的方法来纠正几个 OCR 误读并注意表格中的出现，然后该表格将成为上述成本表。（即如果 OCR 弄错了，那么字符必须是相似的）。

于 2012-05-03T14:42:36.450 回答
2

一般来说，我看到Damerau-Levenshtein比Levenshtein更常用，它基本上添加了换位操作。它应该占人类拼写错误的 80% 以上，所以你当然应该考虑这一点。

至于您的具体问题，您可以轻松地修改算法以在用非大写字母替换大写字母时增加成本，反之获得类似的东西：

dist(Co, CY) = 2
dist(Co, CZ) = 2
dist(Co, Ca) = 1
于 2012-05-03T14:44:17.680 回答