0

レーベンシュタイン距離でリストをソートするための O(n) またはより高速なアルゴリズムはありますか? 私は SO でいくつかの解決策を見てきましたが、それらはすべて従来の並べ替えを呼び出します。ここで、入力のバイト数を合計するとします。レーベンシュタイン距離でほぼソートされたハッシュ キーが得られます。たとえば、一連のランダムな文字列を取得し、バイトの合計によってハッシュを計算しました。

[ { hash: 2826, val: 'LKAMFKLFUAHUHAUHAUHAU:ANGONEGANAILFJAL:' },
  { hash: 2829, val: 'LKAMFKLFLFUAHUAHUHAUAHANGONEGANAILFJAL:' },
  { hash: 2845, val: 'LKAMFKLFLFAKAKKAKAfiO:ANGONEGANAILFJAL:' },
  { hash: 3064, val: 'LKAMFKLFKKKlaNflanfiO:ANGONEGANAILFJAL:' },
  { hash: 3092, val: 'LKAMFKLFLFklaNflanfiO:ANGONEGANAILFJAL:' },
  { hash: 3203, val: 'LKAMFKLFLFklaNflanfiRSRSRSRSRRNAILFJAL:' },
  { hash: 3249, val: 'LKNFUU{N{UAFN{NF}FNPNF{FN{APNF{WNFF{NF' },
  { hash: 3843, val: 'ddddddddddaaaaaaaaaddddddddddaaaaaaaaaa' },
  { hash: 3858, val: 'safndjnjcmxn,znv,mnm,n,mvnm,vn,mznv,mvv' },
  { hash: 3934, val: 'nngnangngdsgsangnanwns.mnv.nv.xnjvnsf.,' },
  { hash: 3972, val: 'adadsadadsadadadsadsadadsadsadadsadsada' },
  { hash: 3992, val: 'adsadadadsadasdasdafadfasfdsafsafasfafd' },
  { hash: 4041, val: 'asfdsafasdfsafafasdfasdfafsdfdasfasfasf' },
  { hash: 4047, val: 'kkkkkkkkkkkdddddddddkkkkkkkkkkddddddddd' },
  { hash: 4058, val: 'jfjfjfjfjfjfjfjfjfjfjfjfjfjfjfjfjfjfjfj' },
  { hash: 4081, val: 'ioudnjkanfjfhjhfjhakfshfkjhdajhkjafhkjf' },
  { hash: 4082, val: 'ioudnjkanfjfhjhfjhakfshfkjhdakhkjafhkjf' },
  { hash: 4082, val: 'oisdnkbgjkbajkgkbgkjbkklgjklsbkbfkjafas' },
  { hash: 4090, val: 'ioudnjsanfjfhjhfjhakfshfkjhdakhkjafhkjf' },
  { hash: 4099, val: 'asldfjlkcmclmasldkkjflksajflkjaljfljlfa' },
  { hash: 4101, val: 'sidfjlasjflijflijlfjliafjdlifjlijfiljfl' },
  { hash: 4105, val: 'iousnjsanfjfhjhfjhakfshfkjhdakhkjafhkjf' },
  { hash: 4125, val: 'iousnjsanfjfhlhfjuakfshkkjhdakhkjafhkjf' },
  { hash: 4128, val: 'sadnfjnfjnjfnjsdfnjafnjkfnkfnjkansdfjkn' },
  { hash: 4143, val: 'dnsfanfjknasfjklnaskfnkfnklafnjkfnkldsn' },
  { hash: 4150, val: 'dskfoisandginsgnlgn:nglngbtbiybuburubsu' },
  { hash: 4155, val: 'afadfsfsfsdfffsfsfsfsdfsfsfsdfsfsfsfsfs' },
  { hash: 4166, val: 'kjdkljkljkljlkjkljlkjlkjlkjlkjljlkjljlk' },
  { hash: 4211, val: 'jsanjnvjksnfkjsanfuiawngingiuilugniugng' },
  { hash: 4229, val: 'kllnlknlknklnklnlnlknknklnlnlnklnlknlkn' },
  { hash: 4238, val: 'lsniorhgpwoiqutoiuieofnionofnoinfonfioa' },
  { hash: 4349, val: 'iasfioehwoptqpoituopqwtuoquweporuqiorur' },
  { hash: 4374, val: 'ioequroiqwuroiuriouroiuopriuprouqpourrq' },
  { hash: 4377, val: 'iiuouoiuoiuouoiuuououoiuououoiuououoiuo' } ]

結果はほぼソートされています。つまり、挿入ソートは非常に高速にジョブを完了できます ( 「参考文献」を参照)。

そのような大まかな実験がそれらの結果を提供した場合、SOがその答えに欠けている解決策が確かにあります。それはどれでしょうか？

4

2 に答える 2

3

以下の議論は、あなたのアイデア (私が理解しているように) は一般的なケースではうまくいかないという私の長ったらしい言い方です。理由？長さ N の 2 つの文字列間のレーベンシュタイン距離は N である必要がありますが、文字列のチェックサムは同一であるためです。たとえば、文字列を逆にします。さらに、レーベンシュタイン距離が 1 の 2 つの文字列間のチェックサムの差は 255 (または Unicode では 65,536) になる可能性があります。そのような範囲では、「ほぼソート」できたとしても (以下を参照)、あまりメリットはありません。

単純なチェックサムとレーベンシュタイン距離の間には相関関係があることがわかりました。明らかな関係です。2 つの文字列間のレーベンシュタイン距離が小さい場合、これら 2 つの文字列にはほとんど同じ文字が含まれています。したがって、単純なチェックサムを計算すると、非常によく似た値になります。時々。

しかし、他の誰かが指摘したように、その逆は真実ではありません。文字列abcdefとのfedcbaチェックサムは同じですが、このような短い文字列のレーベンシュタイン距離はかなり大きくなります。

これは反転だけに当てはまるわけではありません。たとえば、文字列を考えてみましょう00000000。文字列の0000000~チェックサムは11111111、たとえ Lev. 距離ははるかに小さいです。

一般的なケースでは、チェックサムと Lev の関係が分かると思います。距離は...時には偶然です。しかし、その特定の問題は無視して、ソートに関する仮説に移りましょう。

私が理解しているように（そして、正直なところ、あなたの質問はこの点で完全に明確ではありません）、レーベンシュタイン距離に基づいて文字列のリストをソートしたいと考えています。何からの距離とは言いませんが、どこかに開始文字列 、S他の文字列の束があり、他の文字列[S1, S2, S3, etc.]のリストを Lev で並べ替えたいと仮定します。からの距離S。

あなたの仮説は、各文字列の単純なチェックサムを計算すると、その並べ替えをより迅速に実行できるようになるというものです。

問題は、チェックサムを計算したら、それらをソートする必要があることです。これには、従来の比較ソートでは時間がかかります (いずれにせよ、特別な目的のソートを使用しているO(n log n)場合は、少なくとも時間がかかります)。O(n)そして、おそらくほぼ順序付けられたリストを取得したら、Lev を計算する必要があります。いずれにせよ、実際の距離を反映するようにリストの順序を並べ替えます。しかし、ポイントは何ですか？

Lev を計算する必要があります。とにかく距離、そしてあなたは何かをソートするのに少なくとも 時間を費やすでしょう. Lev を計算するだけでより迅速に計算できるのに、チェックサムの計算と並べ替えに余分な手間をかける必要はありません。距離とそれらをソートしますか？O(n)

于 2013-03-03T15:37:33.470 に答える
1

O(n log n) 境界は、順序付けられた型の比較に基づく、特定の種類の並べ替え用です。

この場合、順序付けは単純な符号なし整数値に基づいており、(扱っているデータによっては) 境界がかなり小さい可能性があります。この場合、あなたの選択肢は...

  1. 最大距離が十分に小さい場合は、(最初は null の) リスト ヘッド ポインターの配列を作成します。配列の添字は距離です。データをループしてリストの配列に入力し、すべてのデータを順番に抽出します。配列内の多くのヘッド ポインターが null のままになること (決して発生しない距離がたくさんあること) が心配な場合は、配列に 2 つの二重リンク リストを作成することもできます。中古品の。そうすれば、データを抽出するときに、アイテムが含まれているリストを確認するだけで済みます。

  2. 最大距離に関係なく、ハッシュ テーブルでも同じことができます。より多くのスペースが必要になるたびにテーブルが一定の係数で拡大する場合、各挿入には O(1) 時間amortizedがかかります。ループ全体を考慮すると、「償却」が定義されているため、単純に O(n) - もう償却されません。ハッシュ テーブルは通常順不同ですが、ごまかすことができます。ハッシュは距離です。データを抽出するときに複数のパスを作成することを避けるために、おそらくもう少しチートが必要ですが、それほど難しいことではありません。

チェックサムを使用しようとしても、何のメリットもありません。

すべてのアイテムを移動する必要がある可能性があるため、データを並べ替えたい場合は O(n) に勝るものはありません。各アイテムの移動先を魔法のように知っていたとしても、それらの移動を行うのはとにかく O(n) です。

また、データがすでに正しい順序になっている場合でも、単に距離を計算して、それも O(n) であることを確認します。

レーベンシュタイン距離を 1 つの文字列に割り当てることはできず、別の文字列に対して相対的であるため、考え直して少し緊張しています。

「最も近い」ものを検索できるように文字列のインデックスを作成する場合は、Steve Hanov のブログ の Vantage Point Trees に関するこの投稿を参照する必要があります。

ただし、それを使用して O(n) パフォーマンスが得られるとは思えません。

于 2013-03-03T15:59:33.353 に答える