如何確定字符相似性？

我使用Levenshtein距離在OCR後查找類似的字符串。但是，對於某些字符串，編輯距離相同，但視覺外觀明顯不同。如何確定字符相似性？

例如字符串Co將返回這些比賽：

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

考慮，即Co是從OCR引擎的結果，Ca會比那些更可能的匹配。因此，在計算Levenshtein距離之後，我想通過視覺相似性排序來優化查詢結果。爲了計算這種相似性，我想使用標準的無襯線字體，如Arial。

有沒有可用於此目的的圖書館，或者我該如何自己實現？或者，是否有任何字符串相似度算法比Levenshtein距離更準確，我可以使用它？

來源

2012-05-03 Pedro

它可以是非常具體的，你正在使用的成像機和OCR程序本身。最佳策略，恕我直言，是創建一個訓練數據集，並憑經驗計算這些概率。 – ElKamina

如果」重新尋找一張桌子，可以讓你根據視覺相似性計算出一種「重置成本」，但我一直在尋找這樣的事情一段時間沒有成功，所以我開始將它視爲一個新問題。我沒有使用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

這一點，因爲它的立場，是我的目的，太原始了，需要更多的工作。但是，您也許可以使用它，或者也可以調整它以適應您的目的。該計劃相當簡單。這個排名是針對單一空間字體的。如果您使用的是無襯線字體，則可能需要重新處理這些值。

該表格是一個包含所有字符（大寫和小寫）的混合表格，但是如果僅將其分成大寫字母和小寫字母，則它可能證明更有效，並且還可以應用特定套管罰款。

請記住，這是早期的實驗。如果你看到一種方法來改進它（例如通過改變位排序），盡一切辦法來做到這一點。

來源

2012-05-17 18:21:39 David

所以在您的距離功能只是有不同的成本替換不同的字符對。

即，而不是更換加入一種或所涉及的兩個字符irrepective的一套成本 - 代替具有更換成本函數返回在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-03 14:42:36

一般來說，我看過Damerau-Levenshtein比Levenshtein多得多，它基本上增加了換位操作。它應該占人體拼寫錯誤的80％以上，所以你當然應該考慮這一點。

至於你的具體問題，你可以很容易地修改算法，取代與非大寫字母大寫字母時，增加了成本，而且相反，以獲得類似的東西：

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

來源

2012-05-03 14:44:17

如何確定字符相似性？

回答

相關問題