10

過去数日間、私はこれを広範囲に調査しました。非常に多くのことを読んだため、これまで以上に混乱しています。大規模なデータセットで最も長い共通部分文字列を見つけるにはどうすればよいですか? アイデアは、このデータ セットから重複するコンテンツを削除することです (長さが異なるため、アルゴリズムを継続的に実行する必要があります)。大規模なデータ セットとは、約 100 MB のテキストを意味します。

サフィックスツリー？サフィックス配列？ラビンカープ？最善の方法は何ですか？そして、私を助けることができるライブラリはそこにありますか?

本当に良い反応を期待して、頭がとても痛いです。ありがとうございました！:-)

4

1 に答える 1

4

私は常にサフィックス配列を使用してきました。私はいつもこれが最速の方法だと言われてきたからです。

アルゴリズムが実行されているマシンでメモリが不足している場合は、いつでも配列をハード ドライブ上のファイルに保存できます。アルゴリズムはかなり遅くなりますが、少なくとも結果は得られます。

また、ライブラリが、適切に記述されたクリーンなアルゴリズムよりも優れた仕事をするとは思いません。

LE: ところで、最長の共通部分文字列を見つけるためにデータを削除する必要はありません。

最長共通部分文字列問題から:

function LCSubstr(S[1..m], T[1..n])
    L := array(1..m, 1..n)
    z := 0
    ret := {}
    for i := 1..m
        for j := 1..n
            if S[i] = T[j]
                if i = 1 or j = 1
                    L[i,j] := 1
                else
                    L[i,j] := L[i-1,j-1] + 1
                if L[i,j] > z
                    z := L[i,j]
                    ret := {}
                if L[i,j] = z
                    ret := ret ∪ {S[i-z+1..i]}
    return ret

何もソートする必要はありません。100MB のデータを 1 回解析し、n*m の文字配列を作成してコンピューティングを保存するだけです。こちらのページもチェック

LE: Rabin-Karp はパターン マッチング アルゴリズムです。ここでは必要ありません。

于 2010-11-17T20:46:43.297 に答える