string - ハミング距離を使用して一連の文字列をクラスター化する最適な方法

Question

n 個の文字列 (n > 100 万) を持つデータベースがあり、各文字列は 100 文字で、各文字はa、b、cまたはのいずれかdです。

それぞれに最も近い文字列を見つけたいと思います。最も近いとは、ハミング距離が最小であると定義します。それぞれの k に最も近い文字列 (k < 5) を見つけたいと思います。

例

N = 5
i1 = aacbdbbb
i2 = abcbdbbb
i3 = bbcadabd
i4 = bbcadabb

HammingDistance(i1,i2) = 1
HammingDistance(i1,i3) = 5
HammingDistance(i1,i4) = 4
HammingDistance(i2,i3) = 4
HammingDistance(i2,i4) = 3
HammingDistance(i3,i4) = 1

k=1 の場合、{(i1,i2),(i2,i1),(i3,i4),(i4,i3)} を返す必要があります。k=2 の場合、{ (i1,{i2,i4}),(i2,{i1,i4}),(i3,{i4,i2}),(i4,{i3,i2})} を返す必要があります。等々。各文字列について、k-最も近い文字列を見つける必要があります。

単純なソリューションの複雑さは O(n^2) 時間です。より複雑なソリューションを見つけたいと思います。他の解決策をいくつか見つけましたが、どれもナイーブに勝るものはありませんでした。

このような文字列をクラスターに最適に分散するにはどうすればよいですか? 1 つの文字列が両方または複数のクラスターに存在する可能性があります。解決策は、決定論的または確率論的である可能性があります。