2

大量の文字列を保存し、重複をチェックするための最良の方法は何だろうか。

私たちは自分たちの優先順位について考えなければなりません：

  • 重複チェック速度
  • 新しい文字列時間を挿入する
  • ハードディスクのストレージスペース
  • ランダムアクセス時間

私たちのターゲットが高速重複チェックと新しい文字列の挿入時間（ランダムアクセスやストレージスペースの問題なし）である場合、最良の解決策は何ですか？SQLデータベースについて考えますが、このソリューションに最適なDBはどれですか？MySQLのようにSQLDBを使用する場合、どのストレージエンジンが最適ですか？（もちろん、データ量のためにメモリを除外する必要があります）

4

3 に答える 3

5

入力文字列でハッシュ関数を使用します。出力ハッシュは、レコードの主キー/IDになります。

次に、DBに次のハッシュ/ID/主キーがあるかどうかを確認できます。

  • そうでない場合：これは新しい文字列です。文字列とハッシュをidとして含む新しいレコードを追加します。
  • 含まれている場合：ロードされたレコードの文字列が入力文字列と同じであることを確認します。
    • 文字列が同じ場合：重複しています
    • 文字列が異なる場合：これは衝突です。衝突解決スキームを使用して解決します。（以下のいくつかの例）

速度と予想される文字列の数、およびハッシュ衝突の要件/保証に基づいて、使用するハッシュ関数/スキーム/強度を検討する必要があります。

衝突を解決するいくつかの方法：

  • 2番目のハッシュ関数を使用して、同じテーブルに新しいハッシュを作成します。
  • レコードにマークを付け（たとえばNULLを使用）、2番目の「衝突」テーブルでより強力な2番目のハッシュ関数（より広いドメインを使用）で繰り返します。クエリで、文字列が衝突としてマークされている場合（たとえば、NULL）、衝突テーブルで再度ルックアップを実行します。また、動的完全ハッシュを使用して、この2番目のテーブルにそれ以上の衝突が発生しないようにすることもできます。

もちろん、これがどれだけ永続的である必要があるか、および使用すると予想されるメモリの量/文字列の数に応じて、データベースなしで、メモリ内で直接これを行うことができます。これははるかに高速です。

于 2012-04-13T09:51:34.383 に答える
4

NoSQLソリューションを検討することをお勧めします。

Redis。Redisを使用して解決されたユースケースのいくつか：

memcached。memcachedとRedisのいくつかの比較：

OMGPOPのDrawSomethingをサクセスストーリーの1つとして数えるMembase/Couchbase。RedisとMembaseの比較：

いくつかの質問：

  • 文字列のセットの大きさはどれくらいですか？
  • アプリケーションは大量に読み取られますか、それとも書き込みが多くなりますか？または両方？
  • データをディスクに永続化する頻度を教えてください。
  • N個の最新の文字列要件はありますか？

お役に立てれば。

于 2012-04-14T01:24:30.027 に答える
1

文字列を格納するための接尾辞木を生成します。http://www.daimi.au.dk/~mailund/slides/Ukkonen-2005.pdfのようなUkkonenのアルゴリズムは、接尾辞木を作成する方法についての洞察を提供します。この接尾辞木を保存する方法はいくつかあります。ただし、一度生成されると、ルックアップ時間は非常に短くなります。

于 2012-04-13T23:35:04.067 に答える