如何确定字符相似度？

Question

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

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

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

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

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

- Pedro

---

这可以非常具体地针对您使用的图像处理机和OCR程序。在我看来，最好的策略是创建一个训练数据集并通过实证计算这些概率。 - ElKamina

Answer 1

如果您正在寻找一张表格，可以根据视觉相似性计算“替换成本”，我已经搜索了一段时间，但没有找到合适的东西，所以我开始将其作为一个新问题来考虑。我没有使用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

这个方案还比较原始，需要更多的工作。不过您可能可以使用它，或者根据自己的需求进行调整。这个方案非常简单，适用于等宽字体。如果您使用无衬线字体，则可能需要重新设置值。

该表是一个混合表，包括所有字符，大小写字母。但是，如果将其分成只有大写字母和小写字母的表，则可能会更有效，并且还可以应用特定的大小写惩罚。

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

- David

Answer 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出错，则字符必须相似）。

- Andrew Tomazos

Answer 3

通常情况下，我经常看到使用 Damerau-Levenshtein 而不是仅使用 Levenshtein，它基本上添加了转置操作。它应该能够解释超过80％的人类拼写错误，因此你应该考虑使用它。

至于你的具体问题，你可以轻松修改算法，使替换大写字母为小写字母时增加代价，反之亦然，以获得类似以下的结果：

dist(Co, CY) = 2
dist(Co, CZ) = 2
dist(Co, Ca) = 1

- Charles Menguy