お互いに近い2つの文字列を見つける方法

このペアを見つけるのに最も速い実用アルゴリズムは何ですか？

2017-09-10 eleanora

あなたのデータセットは100k文字列です。新しいクエリが到着するか、またはデータセットの文字列を1つのクエリとして使用しますか？ – gsamaras

@gsamaras与えられた100kストリングの入力に対して、私は他のものよりお互いに近いペアであるただ1つの答えを求めます。 – eleanora

「The Closest Pair Problem under the Hamming Metric」のMin、Kao、Zhuは、あなたが探しているものと思われ、最も近い単一のペアを見つけることに適用されます。あなたの場合、Dは、データ（1000）の次元とnデータセットの大きさD < N ^0.294 <は、アルゴリズムはOで実行されるn（nは^1.843 D ^について

0.533）。

出典

2017-09-10 06:17:26 gsamaras

抽象的なものを見てみると、実用的なアルゴリズムに与える複雑さはO（n^2 D/log^2 D）であるようです。他のアルゴリズムは私にとっては完全に実用的ではないように見えます。 – eleanora

はい、@eleanoraは、私の更新された答えを参照してください！ – gsamaras

O（n^1.843 D^0.533）の複雑さアルゴリズムは、この論文から完全に実用的ではありません。 – eleanora

お互いに近い2つの文字列を見つける方法

答えて

関連する問題