Rilevamento di Retweet mediante algoritmi di hash Python a basso costo computazionalmente

Question

Per essere in grado di rilevare RT di un particolare tweet, intendo archiviare nel database gli hash di ciascun tweet formattato.

Quale algoritmo di hashing dovrei usare. Criptico ovviamente non è essenziale. Solo un modo minimo di archiviare i dati come qualcosa che può quindi essere confrontato se è lo stesso, in modo efficiente.

Il mio primo tentativo è stato usando gli hash md5. Ma ho immaginato che possano esserci algoritmi di hash che sono molto più efficienti, poiché non è richiesta sicurezza.

Answer 1

Stai cercando di eseguire l'hashing di una stringa, giusto? I tipi predefiniti possono essere subito cancellati, basta fare hash (" some string ") e ottieni un po 'di int. È la stessa funzione che python usa per dictonarys, quindi è probabilmente la scelta migliore.

Answer 2

Hai davvero bisogno di fare l'hash? I messaggi di Twitter sono abbastanza brevi (e lo spazio su disco abbastanza economico) che potrebbe essere meglio archiviare l'intero messaggio, piuttosto che consumare cicli di clock per hash.

Answer 3

Non ho familiarità con Python (scusate, ragazzo di Ruby che scrive qui) ma potreste provare alcune cose.

Ipotesi: Probabilmente memorizzerai centinaia di migliaia di tweet nel tempo, quindi confrontando un hash con "ogni record" nella tabella sarà inefficiente. Inoltre, le RT non sono sempre copie carbone del tweet originale. Dopotutto, il nome dell'autore originale è generalmente incluso e occupa parte del limite di 140 caratteri. Quindi forse potresti usare una soluzione che corrisponde più accuratamente di un "stupido" hash?

1. Tagging & amp; Indicizzazione

   Contrassegna e indicizza le parti componenti di il messaggio in modo standard. Questo potrebbe includere il trattamento dell'hash # ...., @-contrassegnato @ e stringhe URL come & Quot; tag " ;. Dopo aver rimosso le parole di rumore e punteggiatura, potresti anche tratta le parole rimanenti come tag anche.

2. Ricerca veloce

   I database sono terribili da trovare appartenenza a più gruppi rapidamente (suppongo che tu usi entrambi Mysql o Postgresql, che sono terribile in questo). Invece provane uno dei motori di testo libero come Ricerca Sfinge . Loro sono molto molto velocemente nel risolvere l'appartenenza a più gruppi (ad es. verifica se sono presenti parole chiave).

   Usando Sfinge o simili, cerchiamo tutti i tag " " abbiamo estratto. Questo probabilmente restituirà un piccolo set di risultati di "potenziali tweet originali". Quindi confrontali uno per uno usando l'algoritmo di matching di somiglianza (eccone uno in Python http://code.google.com/p/pylevenshtein/)

Ora lascia che ti dia un caloroso benvenuto nel mondo del text mining .

Buona fortuna!

Answer 4

Mi associo al commento di Chris sul non usare affatto un hash (si spera che il tuo motore di database possa indicizzare efficientemente campi di 140 caratteri).

Se volessi usare un hash, anche MD5 sarebbe la mia prima scelta (16 byte), seguita da SHA-1 (20 byte).

Qualunque cosa tu faccia, non usare la somma dei caratteri. Non riesco immediatamente a trovare una funzione che avrebbe più collisioni (tutti gli anagrammi hanno lo stesso hash), inoltre è più lento!

$ 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 5

Ci sono alcuni problemi qui. Innanzitutto, le RT non sono sempre identiche. Alcune persone aggiungono un commento. Altri cambiano l'URL per il monitoraggio. Altri aggiungono nella persona che stanno RT (che può essere o meno l'originatore).

Quindi se hai intenzione di eseguire l'hashing del tweet, devi ridurlo alla carne del tweet, e solo l'hash. Buona fortuna.

Sopra, qualcuno ha detto che con 32 bit, inizierai ad avere collisioni a circa 65K tweet. Certo, potresti avere collisioni sul tweet n. 2. Ma penso che l'autore di quel commento fosse confuso, poiché 2 ^ 16 = ~ 65K, ma 2 ^ 32 = ~ 4 Trilioni. Quindi hai un po 'più di spazio lì.

Un algoritmo migliore potrebbe essere quello di provare a derivare il "unico" parti del tweet e impronte digitali. Non è un hash, è un'impronta digitale di alcune parole chiave che definiscono unicità.

Answer 6

Bene, i tweet hanno una lunghezza di soli 140 caratteri, quindi puoi persino memorizzare l'intero tweet nel database ...

ma se vuoi davvero " hash " in qualche modo, un modo semplice sarebbe quello di prendere semplicemente la somma dei valori ASCII di tutti i personaggi nel tweet:

sum(ord(c) for c in tweet)

Naturalmente, ogni volta che hai una corrispondenza di hash, dovresti controllare i tweet stessi per identità, perché la probabilità di trovare due tweet che danno lo stesso "sum-hash" è probabilmente non trascurabile.

Answer 7

Modulo shelve di Python? http://docs.python.org/library/shelve.html