2

特定のツイートのRTを検出できるようにするために、フォーマットされた各ツイートのハッシュをデータベースに保存する予定です。

どのハッシュアルゴリズムを使用する必要がありますか。もちろん、不可解なものは必須ではありません。データを何かとして保存するための最小限の方法であり、同じ場合は効率的な方法で比較できます。

これに対する私の最初の試みは、md5ハッシュを使用することでした。しかし、セキュリティが必要ないため、はるかに効率的なハッシュアルゴリズムが存在する可能性があると考えました。

4

7 に答える 7

6

本当にハッシュする必要がありますか？Twitterメッセージは十分に短い（そしてディスク容量は十分に安い）ので、メッセージをハッシュするためにクロックサイクルを消費するよりも、メッセージ全体を保存する方がよい場合があります。

于 2009-05-02T18:21:12.453 に答える
4

私は Python に詳しくありません (申し訳ありませんが、Ruby の人がここに入力しています) が、いくつかのことを試すことができます。

前提: 時間の経過とともに数十万件のツイートを保存する可能性が高いため、1 つのハッシュをテーブル内の「すべてのレコード」と比較するのは非効率的です。また、RT は必ずしも元のツイートのカーボン コピーではありません。結局のところ、元の作者の名前が通常含まれており、140 文字の制限の一部を占めています。それでは、「ダム」ハッシュよりも正確に一致するソリューションを使用できるでしょうか?

  1. タグ付けとインデックス作成

    標準的な方法で、メッセージのコンポーネント部分にタグを付けてインデックスを付けます。これには、ハッシュされた #....、アットマーク @.... および URL 文字列を「タグ」として扱うことが含まれます。ノイズ ワードと句読点を削除した後、残りの単語もタグとして扱うことができます。

  2. 高速検索

    データベースは、複数のグループ メンバーシップを非常に迅速に見つけるのが苦手です (Mysql または Postgresql を使用していると仮定しますが、これはひどいものです)。代わりに、 Sphinx Searchなどのフリー テキスト エンジンのいずれかを試してください 。複数のグループ メンバーシップの解決 (つまり、キーワードが存在するかどうかのチェック) が非常に高速です。

    Sphinx などを使用して、抽出したすべての「タグ」を検索します。これはおそらく、「元の可能性のあるツイート」の小さな結果セットを返します。次に、類似性マッチング アルゴリズムを使用してそれらを 1 つずつ比較します (ここでは Python http://code.google.com/p/pylevenshtein/の 1 つです) 。

テキストマイニングの世界へようこそ。

幸運を！

于 2009-05-02T18:57:56.373 に答える
2

ハッシュをまったく使用しないという Chris のコメントに同意します (データベース エンジンが 140 文字のフィールドを効率的にインデックス化できることを願っています)。

ハッシュを使用する場合は、MD5 も最初の選択肢 (16 バイト) で、次に SHA-1 (20 バイト) が続きます。

何をするにしても、文字の合計を使用しないでください。より多くの衝突が発生する関数をすぐに思いつくことはできません (すべてのアナグラムは同じようにハッシュされます)、さらに低速です!

$ python -m timeit -s 'from hashlib import md5' 'd=md5("There once was a man named Michael Finnegan.").digest()'
100000 loops, best of 3: 2.47 usec per loop
$ python -m timeit 'd=sum(ord(c) for c in "There once was a man named Michael Finnegan.")'
100000 loops, best of 3: 13.9 usec per loop
于 2009-05-02T18:52:58.943 に答える
2

ここにはいくつかの問題があります。まず、RT は常に同一であるとは限りません。コメントを追加する人もいます。トラッキングのために URL を変更する人もいます。他の人は、RTしている人を追加します（発信者である場合とそうでない場合があります）。

したがって、ツイートをハッシュ化する場合は、ツイートの本質にまで煮詰めて、それのみをハッシュ化する必要があります。幸運を。

上で、32 ビットでは、約 65K のツイートで衝突が発生し始めると誰かが述べました。もちろん、ツイート #2 で衝突が発生する可能性があります。しかし、2^16 = ~65K ですが、2^32 = ~4 兆であるため、そのコメントの作成者は混乱していたと思います。そのため、もう少し余裕があります。

より良いアルゴリズムは、ツイートの「固有の」部分を導き出し、それをフィンガープリントすることです。これはハッシュではなく、一意性を定義するいくつかのキーワードのフィンガープリントです。

于 2009-07-16T19:07:47.130 に答える
1

ツイートの長さはわずか140文字なので、ツイート全体をデータベースに保存することもできます...

しかし、どういうわけか本当にそれらを「ハッシュ」したい場合、簡単な方法は、ツイート内のすべての文字のASCII値の合計を取得することです。

sum(ord(c) for c in tweet)

もちろん、ハッシュが一致する場合は常に、ツイート自体が同一であるかどうかを確認する必要があります。これは、同じ「合計ハッシュ」を与える2つのツイートが見つかる可能性はおそらく無視できないためです。

于 2009-05-02T18:22:41.840 に答える
0

Pythonのシェルフモジュール？http://docs.python.org/library/shelve.html

于 2009-05-02T18:20:51.707 に答える
0

文字列をハッシュしようとしていますか？組み込み型はすぐにハッシュできます。ハッシュするだけで、hash("some string")intを取得できます。Pythonが辞書に使用するのと同じ関数なので、おそらく最良の選択です。

于 2009-05-03T18:59:30.030 に答える