如何确定字符相似度？

Question

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

例如,字符串Co将返回以下匹配项:

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

考虑到,这Co是OCR引擎的结果,Ca将比那些更可能匹配.因此,在计算Levenshtein距离之后,我想通过视觉相似性排序来改进查询结果.为了计算这种相似性,我想使用标准的sans-serif字体,比如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

就目前而言,这对我的目的而言太过原始,需要更多的工作.但是,您可以使用它,或者根据您的目的调整它.该计划相当简单.此排名适用于单声道空间字体.如果您使用的是无衬线字体,那么您可能需要重新处理这些值.

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

请记住,这是早期的实验.如果您看到一种方法来改进它(例如通过更改位序列),请务必随意这样做.