リレーションが文字列編集距離= 1のグラフを生成するためのブルートフォースアルゴリズムがありますか？

Question

頂点が文字列であるグラフを作成することに興味があり、そのエッジが指定された文字列メトリックの下で1の編集距離が1の関係を表す。

明らかなアプローチは、の比較をすべて行うことです。> $ n $ 頂点、 $ O（n ^ 2）$ 時間の複雑さ。

比較の並列化を除く、時間の複雑さの観点からはより良いアルゴリズムがありますか？

さまざまな長さの文字列が許可されている文字列メトリックに興味があります。

Answer 1

最悪の場合、このようなアルゴリズムは $ \ omomega（n ^ 2）$ を作動させます。$ \ omomega（n ^ 2）$ エッジ

ところで、あなたはいくつかの特定の文字列メトリックに興味がありますか？

Answer 2

bk-trees を使用することは可能です。 $ n $ の挿入ツリーに $ o（n \ log n）$ 時刻になります。この後、編集距離が正確に入力から1離れているすべての文字列に対してツリーを照会できます。これをすべて再度実行すると、 $ o（n ^ 2）$ 複雑さがありますが、非常に小さい一定の要素（このページ の正義は、ツリーの5-8％のみをクエリごとに検査する必要があります）

それがどのように機能するかの簡単な説明です：

データ構造

BKツリーは

です

• 空の
• ルート値 $ r $ のセット $ c_i $ のセット各BKツリー（ハッシュマップ、ダイナミックアレイ、または同様の）
を使用して実装されています）

メトリック（重要！）距離関数 $ d（x、y）$ d（x、y）$ は挿入と照会に使用されます。

文字列 $ s $

• ツリーが空の場合は、 $ s $ を持つ新しいノードに、root値として、
がいません。
• ツリーがroot $ r $ と子のノードの場合 $ c_i $ 、<< SPAN CLASS="math-container"> $ k= d（r、s）$ 。
  • $ k= 0 $ の場合、 $ s $ としてのスキップ挿入はすでにルートにあります。 / li>
  • それ以外の場合は、 $ s $ を $ k $ $ C_K $ 。

最後のステップは、 $ c_i $ のすべてのノードに距離 $ i $ があることを確認します。ルート

文字列 $ s $

• ツリーが空の場合は、結果を返しません
• ツリーがroot $ r $ と子のノードの場合 $ c_i $ 、<< SPAN CLASS="math-container"> $ k= d（r、s）$ 。
  • $ k= 1 $ の場合、 $ r $ を追加します（メモ：このステップは通常のBKツリークエリとは異なるです）
  • さらに、 $ s $ を再帰的にquolduge quoldum $ c_ {d-1} $ 、 $ c_d $ と $ c_ {d + 1} $ 。それらのクエリからすべての結果を返す

最後のステップは、距離がメトリックであるために他の子供をチェックする必要がないので、BKツリーの魔法があります。これは他の人がチェックされる必要がない理由の部分的な証明です：

いくつかの文字列があると仮定しましょう。 $ d（s、s、stap）がある $ x $ があるとしましょう。 X）= 1 $ ですが、子ツリー $ c_ {k + 2} $ にあります。挿入手順から、 $ d（r、x）= k + 2 $ であることがわかります。しかし、これは（メートルス空間の三角形の不等式を持つ）が

を与える

$$ K + 2= D（R、X）\ LEQ D（R、S）+ D（S、X）= K + 1 $$

しかしこれは矛盾です！ $ i> k + 1 $ 、 $ i 。これは、他の子供のすべての文字列が建設によって距離を持たないので、処理時間を節約する必要があります。

編集：別の説明： https://signal-to-noise.xyz / POST / BKツリー/