OCRの後に同様の文字列を見つけるためにレーベンシュタイン距離を使用しています。ただし、一部の文字列では、視覚的な外観は明らかに異なりますが、編集距離は同じです。
たとえば、文字列Coは次の一致を返します。
CY (1)
CZ (1)
Ca (1)
CoそれがOCRエンジンからの結果であることを考慮Caすると、一致する可能性が高くなります。したがって、レーベンシュタイン距離を計算した後、視覚的類似性で並べ替えてクエリ結果を絞り込みたいと思います。この類似性を計算するために、Arial などの標準的なサンセリフ フォントを使用したいと思います。
この目的で使用できるライブラリはありますか、またはこれを自分で実装するにはどうすればよいですか? または、レーベンシュタイン距離よりも正確な文字列類似性アルゴリズムはありますか?これをさらに使用できますか?
視覚的な類似性に基づいてある種の「交換コスト」を計算できる表を探している場合、私はしばらくそのようなものを探していましたが、ほとんど成功しなかったので、新しいものとして調べ始めました。問題。私は 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
現状では、これは私の目的には原始的すぎて、さらに作業が必要です。ただし、それを使用したり、目的に合わせて調整したりできる場合があります。スキームはかなり単純です。このランキングは等幅フォントのランキングです。サンセリフ フォントを使用している場合は、値を再加工する必要があります。
この表は、小文字と大文字のすべての文字を含むハイブリッド表ですが、大文字のみと小文字のみに分割すると、より効果的であることが証明される可能性があり、特定の大文字と小文字のペナルティを適用することもできます.
これは初期の実験であることを覚えておいてください。それを改善する方法 (たとえば、ビット シーケンスを変更するなど) を見つけた場合は、ぜひお気軽に実行してください。
したがって、距離関数では、異なる文字のペアを置き換えるためのコストが異なります。
つまり、関連する文字に関係なく 1 つまたは 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 が間違っている場合、文字は類似している必要があります)。
一般に、私はDamerau-LevenshteinがLevenshteinよりもはるかに頻繁に使用されるのを見てきましたが、基本的に転置操作が追加されています。これは、人間のスペルミスの 80% 以上を占めると考えられているため、必ず考慮する必要があります。
特定の問題に関しては、アルゴリズムを簡単に変更して、大文字を大文字以外の文字に置き換えるときにコストを増やし、その逆を行ってそのようなものを取得できます。
dist(Co, CY) = 2
dist(Co, CZ) = 2
dist(Co, Ca) = 1