私は高度なレーベンシュタイン距離アルゴリズムを探していましたが、これまでに見つけた最高のものはO（n * m）です。ここで、nとmは2つの文字列の長さです。アルゴリズムがこのスケールである理由は、次のような2つの文字列の行列が作成されるため、時間ではなくスペースが原因です。
O（n * m）よりも優れた公的に利用可能なレーベンシュタインアルゴリズムはありますか？私は高度なコンピュータサイエンスの論文や研究を見るのを嫌がりませんが、何も見つけることができませんでした。私は、超高度で超高速のレーベンシュタインアルゴリズムを構築したと思われるExorbyteという会社を見つけましたが、もちろんそれは企業秘密です。レーベンシュタイン距離計算を使用したいiPhoneアプリを作成しています。Objective-cの実装が利用可能ですが、iPodとiPhoneのメモリ量が限られているため、可能であれば、より良いアルゴリズムを見つけたいと思います。
時間の複雑さや空間の複雑さを減らすことに興味がありますか？平均時間計算量はO（n + d ^ 2）に減らすことができます。ここで、nは長い文字列の長さ、dは編集距離です。編集距離のみに関心があり、編集シーケンスの再構築には関心がない場合は、行列の最後の2行をメモリに保持するだけでよいので、order（n）になります。
近似する余裕がある場合は、多対数近似があります。
O（n + d ^ 2）アルゴリズムについては、Ukkonenの最適化またはその拡張EnhancedUkkonenを探してください。私が知っている最良の近似は、 Andoni、Krauthgamer、Onakによるこれです。
しきい値関数のみが必要な場合（たとえば、距離が特定のしきい値を下回っているかどうかをテストする場合）、配列の主対角線の両側のn値を計算するだけで、時間とスペースの複雑さを軽減できます。Levenshtein Automataを使用して、O（n）時間で単一のベースワードに対して多くの単語を評価することもできます。オートマトンの構築もO（m）時間で実行できます。
Wikiを見てください-彼らはこのアルゴリズムを改善してスペースの複雑さを改善するためのいくつかのアイデアを持っています：
引用：
前の行と現在の行を一度に格納するだけでよいため、O（mn）ではなくO（m）という少ないスペースを使用するようにアルゴリズムを適応させることができます。
O（max（m、n））であると主張する別の最適化を見つけました：
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C
（2番目のC実装）