ハミング距離とレーベンシュテイン距離
-
14-10-2019 - |
質問
私が取り組んでいる問題については、2つのシーケンス間の距離を見つけて類似性を判断するため、シーケンスの順序は非常に重要です。ただし、私が持っているシーケンスはすべて同じ長さではないため、ハミング距離要件を満たすために両方のシーケンスが同じ長さであるように、空の点で不足した文字列をパッドします。これを行うことに大きな問題はありますか?
ハミング距離は、長さのシーケンスの距離メトリックとして、レーベンシュテインよりもはるかに高速であることがわかりました。はるかに安価なハミング距離ではなく、いつレベンシュタイン距離(またはレベンシュテイン距離の派生距離)を使用する必要がありますか?ハミング距離は、2つのシーケンス間のレベルシュテイン距離の可能性の上限と見なすことができます。したがって、シーケンスと一致する絶対的な最小数の動きの数ではなく、順序バイアス化された類似性メトリックについて2つのシーケンスを比較している場合、明らかなことはありません私がメトリックとしてハミングよりもlevenshteinを選ぶ理由はありますか?
解決
その質問は、あなたが一致しているシーケンスの種類と、あなたが望む結果に本当に依存します。
「1234567890」と「0123456789」がまったく異なると見なされていることが問題でない場合、実際にはハミング距離は問題ありません。
他のヒント
正しいヨハンの答えに加えて、パディングには問題がある可能性があります。
たとえば、比較するとき 123
に 123456
文字列の最後または文字列の開始時にパッドをパッドすると、それは異なります。の類似性 ___123
と 123456
0ですが、の類似性です 123___
と 123456
3です。