1

10万個の文字列を互いに比較しようとしています。問題のサイズ (つまり、セット内の #strings) をこれ以上減らすことはできません。レーベンシュタイン比を使って比較しています。ratio が 0.9 より大きい場合、2 つの文字列をリストに格納します。私の質問は、ランタイムの最適化についてです。0.9 が私の基準なので、この値を Levenshtein.ratio() に渡し、否定的な場合に早期終了を期待する方法はありますか? 早期に終了する方法があれば、ランタイムを節約できます。完全な距離を計算する前に比率を早期に取得することは、レーベンシュタイン アルゴリズムで実現可能ですか。

例えば

import Levenshtein 
Levenshtein.ratio('lot of runtime','why not an early exit in this case by taking the intended ratio')

次のようなものがありますか：

Levenshtein.ratio('lot of runtime','why not an early exit in this case by taking the intended ratio', 0.9)
4

1 に答える 1

1

はい、あなたが想定しているような早期終了は可能です。

モジュールのソース コードLevenshteinは自由に利用できるため、自分で機能を追加できます。

考慮したい別の最適化があります: 三角形の不等式です。文字列 A が文字列 B に 20% 類似しており、文字列 B が文字列 C に 90% 類似している場合、文字列 A が文字列 C に 90% 類似していないことがわかります。 ACレーベンシュタイン距離を実際に計算するために。

于 2013-01-14T18:19:43.890 に答える