0

「ファイル」のデータセットがあります-ファイルの名前と、その後に32ビットの数値が続きます-ファイルのハッシュのようなもの。

"file1" 6a9bd9a6 1df3b24b 7ab054dc
"file2" 6a9bd54e 1df3b24b 8cd054dc
"file3" 6a9bd9a6 7ab054dc

一意のファイルを取得するにはどうすればよいので、s2 は他の s2 のプレフィックスではありません。つまり、番号が一意であることを意味します。2 つの同じ s2 がある場合、それらが他の s2 のプレフィックスでない場合、それらは両方とも一意です。

迅速な解決策を探しています。各文字列を他の文字列と比較する解決策を考え出すことはできますが、時間がかかりすぎて効果がありません。もう 1 つのオプションは、何らかの方法でテーブルに MySQL エンジンを使用することでしたが、その方法がわかりません。手伝ってくれますか？

4

1 に答える 1

2

トライを使用して、文字列が他の文字列のプレフィックスにならないようにすることができます。

トライに挿入するときは、次の両方のケースをチェックします。

1）古いリーフノードを通過しましたか？もしそうなら、それは別の文字列が私の文字列のプレフィックスであることを意味します。
2）既存の非リーフをリーフとしてマークしたいですか？もしそうなら、私は別の文字列のプレフィックスです。

これはO（N）ソリューションであり、Nは文字列の数です（トライへの挿入数を測定します）。各挿入は、その文字列の長さだけ実行されます。

したがって、ここからハッシュを作成する場合。トライを簡単にトラバースして、目的のリーフに到達したらプレフィックスノードがあるかどうかに関する情報を使用できます。各リーフノードはパス全体を表し、それが別の文字列のプレフィックスであるかどうかを認識します。プレフィックスの場合、少なくとも1つの子ノードがあります。

于 2009-04-01T20:31:00.593 に答える