特定のツイートのRTを検出できるように、フォーマット済みのツイートのハッシュをデータベースに保存する予定です。計算上安価なPythonハッシングアルゴリズムを使用してリッツを検出
どのようなハッシュアルゴリズムを使用する必要がありますか。もちろん、不可解なことは必須ではありません。データを効率的に同じであれば比較できる最小限の方法です。
これで私の最初の試みはmd5ハッシュを使用することでした。しかし、セキュリティが必要ないので、はるかに効率的なハッシュアルゴリズムがあると思いました。
文字列をハッシュしようとしていますか？組み込み型はすぐにハッシュすることができます。ちょうどhash("some string")を実行すると、intが得られます。 Pythonがdictonarysに使用するのと同じ関数なので、おそらく最良の選択です。
それは32ビット値を生成しませんか？彼はメッセージを破棄してハッシュだけに依存する予定であるため、このアプリケーションはそれよりも多くの衝突耐性を必要としていると思います。 32ビットの値では、スティーブンフライの30分のような、65kのつぶやき内での衝突が予想されます。 –
Pythonのshelveモジュールですか？ http://docs.python.org/library/shelve.html
本当にハッシュする必要がありますか？ Twitterのメッセージは十分に短く（ディスクスペースも十分に安い）、ハッシュするためにクロックサイクルを食べるのではなく、メッセージ全体を保存するほうが良いかもしれません。
さて、与えられた140文字の文字列とそのような文字列の何千もの文字列を比較することは計算上高価になります。 私は、カウント（ハッシュ）を使ってdbを照会するのが簡単で効率的だと考えました。私が間違っていると私を悔い改めてください –
いつもあなたのつぶやきを並べ替え、バイナリ検索を使用することができます。あなたのデータベースが本当に巨大な場合は、基数検索を使用してください。 （リニアランタイム、どのようにクールですか？） –
リッツイートは頻繁に同一ではありません。あなたが何らかの「正規化」を最初に実行しない限り、ハッシュはこれに気付かないでしょう。 – pchap10k
さて、あなたも、データベース全体つぶやきを保存することができるように、ツイートは...、のみ140文字の長
ですが、あなたは本当に何とか「ハッシュ」、それらをしたい場合は、簡単な方法は、ちょうどになりますもちろん
sum(ord(c) for c in tweet)
、あなたはハッシュの試合があるとき、あなたは同一性のためのツイートを自分でチェックする必要があり、その2つのつぶやきを発見する確率理由：つぶやきのすべての文字のASCII値の合計を取ります同じ "sum-hash"を与えることはおそらく無視できないでしょう。
正しい答えを与えるシンプルなハッシュはありますか？_ほとんどの場合_ –
ハッシュをまったく使用しないことについての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
"sum"は恐ろしいハッシュコードです。しかし、140 * 255は35700で、私のシステムでは16ビットしか格納されません;-) –
そうです、あなたの指は脳より少し速く動いています。 –
私はPythonに慣れていません（ごめんなさい、Rubyの男がここに入力しています）が、いくつか試してみることができます。
仮定： あなたは可能性が高いので、表に「すべてのレコード」に対して1つのハッシュを比較することは非効率的になり、時間をかけてツイートの数十万人を格納します。また、RTはオリジナルのツイートのカーボンコピーであるとは限りません。結局のところ、元の著者の名前は通常含まれ、140文字の制限の一部を占めています。だから、 "ダム"ハッシュよりも正確に一致するソリューションを使用することができますか？
タグとインデックス標準的な方法で メッセージの構成部品&インデックスタグ付け。この には、ハッシュされた＃....、 at-marked @ ....およびURL文字列（ 「tags」）の処理が含まれます。ノイズワード と句読点を削除した後、 も残った単語をタグ として扱うことができます。
高速検索
データベースは非常に 迅速 複数のグループメンバーシップを見つけることで恐ろしいです（私はあなたがこの時ひどい をしている のMySQLやPostgreSQL、のいずれかを使用してと仮定します）。代わりに のフリーテキストエンジンを Sphinx Searchのように試してみてください。複数のグループメンバーシップを解決する際に非常に早く（キーワードが存在するかどうかを確認するのに ）、非常に早く です。
スフィンクスなどを使用して、私たちが抽出したすべての「タグ」の を検索します。この はおそらく "潜在的なオリジナルのつぶやき"の小さなセット の結果セットを返します。そして、暖かくテキストマイニングの世界にあなたを歓迎今、私を聞かせて類似マッチングアルゴリズム （ここではPython http://code.google.com/p/pylevenshtein/の1である）
を使用して1 によってそれらを1つずつ比較します。
幸運を祈る！
もちろん、私はすべての@wordsと句読点の "ツイートをきれいにする"必要があります。 タグ付けするのではなく、集計（ハッシュ）としてデータベースに問い合わせることができるユニークな値を生成する方が簡単ではない –
RTのサンプルを分析して、ほとんど同じであることを確認しましたか？これに頼ることができれば、ハッシュはより簡単になります。 私の素早く野生的な推測はRTの10〜20％が元のものにぼんやりとしていないかもしれません。高い精度が必要な場合は、RTのように見えるツイートの意味のあるランダムサンプル（1000-10000）を取得します（RT @ ....で始まり、via @ ....、Retweet @ ..）。 .. "または" @ ... said "）、それらがどれほど元のものと一致するかを測定する。 精度があまり重要でない場合は、時間を節約してハッシュするだけです。高速ハッシュ検索のアイデアもありましたので、以下で説明します。 ：D – pchap10k
ここにいくつかの問題があります。まず、RTは常に同じではありません。一部の人はコメントを追加します。トラッキングのためにURLを変更するものもあります。他の人は自分がRTしている（発信者かもしれないし、そうでないかもしれない）人物を追加します。
ツイートをハッシュする場合は、ツイートの肉に煮詰めて、それをハッシュする必要があります。がんばろう。
上記のように、32ビットで言及した人は、約65Kのつぶやきで衝突が発生するでしょう。もちろん、あなたはツイート＃2に衝突する可能性があります。しかし、2^16 =〜65Kだから2^32 =〜4兆であるので、そのコメントの著者は混乱していたと思います。だからあなたはもう少し部屋を持っています。
より良いアルゴリズムは、ツイートの「ユニークな」部分を引き出し、それを指紋しようとすることかもしれません。ハッシュではなく、一意性を定義するいくつかのキーワードの指紋です。
はい、私はストップワードを落とし、何らかの単語周波数指紋を作成することがここに行く方法だと思います。 –
CRCの保存と比較はどうですか？ – dirkgently
あなたはこの問題についていくつか考えるかもしれません。再ツイートは、再ツイートのための厳密で速いルールがないので、パターンマッチングの問題の多くです。その結果、オリジナルのツイートの一部のみが利用可能になる可能性がありますので、ハッシュは機能しません。 テキストインデクサーを使用するには、以下を参照してください – jottos
@jottosこの目的のために、RTで始まるすべての単語はリツイートであり、右のものの％。実用上十分です。 私はすべての@ワードRTのツイートを「クリーン」にしなければならないので、ハッシングが可能かもしれません。 –