algorithm - 如何判断字符相似度？

Question

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

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

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

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

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

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

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

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

请记住，这是早期实验。如果您发现了改进它的方法(例如，通过更改位序列)，请尽管这样做。