32ビット番号を並べ替えて一意のエントリを見つける方法は？

Question

"file" - ファイル名のデータセットがあり、その後に32ビットの番号が続きます - ファイルのハッシュのようなものです。

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

どのように私は他のどのS2の接頭辞ではありませんs2のように、独自のファイルを取得するつもりです - 番号がユニークであることを意味します。 2つの同じs2がある場合、それらの両方は、他のs2の接頭辞でない場合には一意です。

私は高速なソリューションを探しています。私は、各文字列を他の文字列と比較するソリューションを考え出すことができましたが、時間がかかり不自然になります。もう一つの選択肢は、テーブルのために何とかMySQLエンジンを使用することでしたが、どうしたらよいか分かりません。手伝ってくれますか？

Answer 1

trieを使用して、文字列が他の文字列の接頭辞でないことを確認できます。

あなたがトライに挿入すると、あなたはこれらの例の両方をチェックします：

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

これは、Nが文字列の数（トライへの挿入数を測定する）であるO（N）解になります。それぞれの挿入は、その文字列の長さだけ実行されます。

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