python - 文字のスクランブリングを伴うレーベンシュタイン距離?

Question

文字列内の文字がスクランブルされている場合にも機能する文字列比較メトリック ala Levenshtein を探しています。そのような指標を知っている人はいますか？また、そのようなメトリックを計算できる Python モジュールがあれば素晴らしいと思います。ありがとう！

Answer 1

各タイプの文字の数を (HashMap または同等のものを使用して) カウントし、結果の値を減算して、各減算の絶対値を取得します。それらをすべて足し合わせてから、2 で割ります (それぞれの差を二重に数えたためです)。

例：

banana
batman

a - 3 , 2 -> |1| -> 1
b - 1 , 1 -> |0| -> 0
m - 0 , 1 -> |-1| -> 1
n - 2 , 1 -> |1| -> 1
t - 0 , 1 -> |-1| -> 1

したがって、あなたは持っています1+1+1+1 = 4 -> 4/2 = 2

チェック:bananaで、1 つnを a にt、1 つaを an にm変更します (2 つの変更)。batman

文字列の長さが異なる場合は、文字列の長さの差を計算し、その数を差の数から引きます (上記)。次に、2 で割り、その数を足し戻します。

例：

nab
banana

total difference count: 3
3 - 3 = 0 -> 0 / 2 = 0 -> 0 + 3 = 3

また、ここではレーベンシュタインをまったく使用しません。なぜなら、その問題の多くの困難はポジショニングであり、あなたが気にしないからです。

Answer 2

ライブラリを試すか、pylevenshteindifflibという外部ライブラリもあります。