Erkennung von Retweets mit Hilfe von billigen Python-Hash-Algorithmen

Question

Um RT eines bestimmten Tweets erkennen zu können, beabsichtige ich, Hashes für jeden formatierten Tweet in der Datenbank zu speichern.

Was Hash-Algorithmus sollte ich verwenden. Kryptisch ist natürlich nicht essentiell. Nur eine minimale Art, Daten als etwas zu speichern, das dann verglichen werden kann, wenn es auf effiziente Weise gleich ist.

Mein erster Versuch war mit MD5-Hashes. Aber ich dachte, dass es Hash-Algorithmen geben kann, die viel effizienter sind, da Sicherheit nicht erforderlich ist.

Answer 1

Sie versuchen, eine Zeichenfolge richtig zu hacken? Vordefinierte Typen können sofort hashed werden, tun Sie einfach hash("some string") und Sie erhalten einige Int. Es ist die gleiche Funktion, die Python für dictonarys verwendet, also ist es wahrscheinlich die beste Wahl.

Answer 2

Pythons Regalmodul? http://docs.python.org/library/shelve.html

Answer 3

Müssen Sie wirklich haseln? Twitter-Nachrichten sind kurz genug (und Speicherplatz ist billig genug), dass es vielleicht besser ist, nur die gesamte Nachricht zu speichern, anstatt die Taktzyklen zu verschlingen, um sie zu hashen.

Answer 4

Nun, Tweets sind nur 140 Zeichen lang sein, so dass man sogar die gesamte tweet in der Datenbank speichern könnte ...

aber wenn Sie wirklich wollen, zu „hash“ sie irgendwie, eine einfache Möglichkeit, nur wären nehmen Sie die Summe der ASCII-Werte aller Zeichen in dem Tweet:

sum(ord(c) for c in tweet) 

natürlich, wenn Sie ein Spiel von Hashes haben, sollten Sie die Tweets selbst für Gleichheit überprüfen, weil die Wahrscheinlichkeit, zwei Tweets zu finden, geben Sie das gleiche "Summen-Hash" ist wahrscheinlich nicht zu vernachlässigen.

Answer 5

Ich echo Chris 'Kommentar über die Verwendung eines Hashes überhaupt (Ihre Datenbank-Engine kann hoffentlich 140-stellige Felder effizient indizieren).

Wenn Sie einen Hash verwenden wollten, wäre MD5 meine erste Wahl (16 Byte), gefolgt von SHA-1 (20 Byte).

Was auch immer Sie tun, verwenden Sie keine Summe von Zeichen. Ich kann nicht sofort mit einer Funktion aufwarten, die mehr Kollisionen hat (alle Anagramme sind gleich), und es ist langsamer!

$ 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 

Answer 6

Ich bin nicht vertraut mit Python (sorry, Ruby Typ hier tippen), aber Sie könnten ein paar Dinge versuchen.

Annahmen: Sie werden wahrscheinlich Hunderttausende von Tweets über die Zeit zu speichern, so dass ein Hash gegen „jeden Datensatz“ in der Tabelle ineffizient wird zu vergleichen. Außerdem sind RTs nicht immer Kopien des ursprünglichen Tweets. Schließlich ist der Name des ursprünglichen Autors in der Regel enthalten und nimmt einige der 140 Zeichen Grenze. Vielleicht könnten Sie also eine Lösung verwenden, die genauer als ein "dummer" Hash entspricht?

1. Tagging & Indexing

   Tag und indizieren die Bestandteile die Nachricht in einer Standardmethode. Diese könnte Behandlung Hash #, at-markierten @ .... und URL-Strings als "Tags" enthalten. Nachdem Sie die Störwörter und die Interpunktion entfernt haben, können Sie auch die restlichen Wörter als behandeln.

2. schnelle Suche

   Datenbanken sind schrecklich bei der Suche nach mehrere Gruppenmitgliedschaft sehr schnell (ich nehme an, Ihr entweder MySQL- oder PostgreSQL-Verwendung, die schrecklich dies sind). Versuchen Sie stattdessen einen der freien Text-Engines wie Sphinx Search. Sie sind sehr sehr schnell beim Auflösen mehrerer Gruppenmitgliedschaft (d. H. überprüft, ob Schlüsselwörter vorhanden sind).

   Mit Sphinx oder ähnlich suchen wir auf alle "Tags", die wir extrahiert haben. Diese wird wahrscheinlich eine kleinere Ergebnismenge von "potenziellen ursprünglichen Tweets" zurückgeben. Dann vergleichen sie eins nach dem anderen mit Ähnlichkeit Matching-Algorithmus (hier ist ein in Python http://code.google.com/p/pylevenshtein/)

Nun mich herzlich lassen begrüßen Sie in die Welt der Text Mining.

Viel Glück!

Answer 7

Es gibt ein paar Probleme hier. Erstens sind RTs nicht immer identisch. Manche Leute fügen einen Kommentar hinzu. Andere ändern die URL für das Tracking. Andere fügen in die Person, die sie RT sind (die möglicherweise oder nicht der Urheber sein) hinzu.

Also, wenn Sie den Tweet hacken, müssen Sie es auf das Fleisch des Tweet kochen, und nur das Hash. Viel Glück.

Oben erwähnte jemand, dass mit 32-Bit, beginnen Sie Kollisionen bei etwa 65K Tweets. Natürlich könnte es bei Tweet # 2 zu Kollisionen kommen. Aber ich glaube, der Autor dieses Kommentars war verwirrt, da 2^16 = ~ 65K, aber 2^32 = ~ 4 Billionen. Du hast dort also etwas mehr Platz.

Ein besserer Algorithmus könnte sein, zu versuchen, die "einzigartigen" Teile des Tweets abzuleiten und sie abzufragen. Es ist kein Hash, es ist ein Fingerabdruck von ein paar Schlüsselwörtern, die Einzigartigkeit definieren.