計算コストが低い Python ハッシュ アルゴリズムを使用したリツイートの検出

StackOverflow https://stackoverflow.com/questions/815313

  •  03-07-2019
  •  | 
  •  

質問

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

どのようなハッシュ アルゴリズムを使用すればよいですか。もちろん、Cryptic は必須ではありません。データを何かとして保存し、同じであるかどうかを効率的な方法で比較できる最小限の方法です。

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

役に立ちましたか？

解決

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

他のヒント

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

私はPythonに慣れていません（申し訳ありませんが、Rubyの人がここに入力しています）が、いくつか試してみることもできます。

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

  1. タグ付け＆amp;インデックス作成

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

  2. 高速検索

    データベースは検索時にひどい 複数のグループメンバーシップ すぐに（私はあなたのどちらかを使用すると仮定します MysqlまたはPostgresql、これらは これでひどい）。代わりに試してみてください のようなフリーテキストエンジンの Sphinx Search 。彼らはとても 複数のグループメンバーシップの解決が非常に高速です（つまり、 キーワードが存在するかどうかを確認します）。

    Sphinxなどを使用して、 すべての＆quot;タグ＆quot;抽出しました。この おそらく小さなものを返します 「潜在的なオリジナルのツイート」の結果セット。次に、それらを1つずつ比較します 類似性マッチングアルゴリズムの使用 （Pythonの http://code.google.com/p/pylevenshtein/）

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

がんばって！

ハッシュをまったく使用しないという 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

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

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

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

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

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

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

sum(ord(c) for c in tweet)

もちろん、ハッシュが一致する場合は常に、ツイート自体の同一性を確認する必要があります。おそらく無視できない。

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top