Detectar retweets utilizando algoritmos de hash de Python computacionalmente económicos

Question

Para poder detectar la RT de un tweet en particular, planeo almacenar hashes de cada tweet con formato en la base de datos.

¿Qué algoritmo de hash debo usar? Críptico, por supuesto, no es esencial. Solo una forma mínima de almacenar un dato como algo que luego puede compararse si es lo mismo, de una manera eficiente.

Mi primer intento en esto fue mediante el uso de hashes md5. Pero pensé que puede haber algoritmos de hash que son mucho más eficientes, ya que la seguridad no es necesaria.

Answer 1

¿Estás intentando hacer un hash de una cadena, verdad? Los tipos incorporados se pueden hashear de inmediato, solo haga hash (" alguna cadena ") y obtendrá algo de int. Es la misma función que Python usa para los diccionarios, por lo que es probablemente la mejor opción.

Answer 2

¿Realmente necesitas hacer hash? Los mensajes de Twitter son lo suficientemente cortos (y el espacio en el disco es lo suficientemente barato), por lo que puede ser mejor simplemente almacenar todo el mensaje, en lugar de consumir ciclos de reloj para procesarlo.

Answer 3

No estoy familiarizado con Python (lo siento, Ruby guy escribiendo aquí), sin embargo, puedes probar algunas cosas.

Suposiciones: Es probable que estés almacenando cientos de miles de Tweets a lo largo del tiempo, por lo que compararás un hash con " cada registro " En la tabla será ineficiente. Además, los RT no siempre son copias de carbono del tweet original. Después de todo, el nombre del autor original generalmente se incluye y ocupa parte del límite de 140 caracteres. Por lo tanto, quizás podría usar una solución que coincida con más precisión que una " tonta " hash?

1. Etiquetado & amp; Indexación

   Etiquete e indexe las partes componentes de El mensaje de forma estándar. Esta podría incluir tratar el hash # .... at-mark @ .... y cadenas de URL como " etiquetas " ;. Después de eliminar las palabras de ruido Y la puntuación, también podrías tratar las palabras restantes como etiquetas también.

2. Búsqueda rápida

   Las bases de datos son terribles de encontrar pertenencia a múltiples grupos muy rápidamente (asumiré que estás usando cualquiera Mysql o Postgresql, que son terrible en esto). En su lugar, intente uno de los motores de texto libre como Búsqueda de Esfinge . Ellos son muy muy rápido para resolver la pertenencia a varios grupos (es decir, comprobando si las palabras clave están presentes).

   Usando Sphinx o similar, buscamos en todas las etiquetas " " nosotros extraemos Esta probablemente volverá un pequeño conjunto de resultados de " posibles tweets originales " ;. Luego compáralos uno por uno utilizando un algoritmo de correspondencia de similitud (aquí hay uno en Python http://code.google.com/p/pylevenshtein/)

Ahora, permítame darle una cálida bienvenida al mundo de minería de texto .

¡Buena suerte!

Answer 4

Me hago eco del comentario de Chris sobre no usar hash (el motor de su base de datos puede indexar campos de 140 caracteres de manera eficiente).

Si quisiera usar un hash, MD5 también sería mi primera opción (16 bytes), seguido de SHA-1 (20 bytes).

Hagas lo que hagas, no uses suma de caracteres. No puedo encontrar de inmediato una función que tenga más colisiones (todos los anagramas tienen el mismo efecto), ¡y además es más 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

Hay algunos problemas aquí. Primero, los RT no siempre son idénticos. Algunas personas agregan un comentario. Otros cambian la URL para el seguimiento. Otros agregan a la persona que están haciendo RT'ing (que puede o no ser el originador).

Entonces, si vas a hacer el hash del tweet, debes hervirlo hasta la carne del tweet, y solo hash de eso. Buena suerte.

Arriba, alguien mencionó que con 32 bits, comenzarás a tener colisiones en aproximadamente 65K tweets. Por supuesto, podrías tener colisiones en el tweet # 2. Pero creo que el autor de ese comentario estaba confundido, ya que 2 ^ 16 = ~ 65K, pero 2 ^ 32 = ~ 4 billones. Así que tienes un poco más de espacio allí.

Un mejor algoritmo podría ser intentar obtener el " unique " partes del tweet, y la huella digital. No es un hash, es una huella dactilar de algunas palabras clave que definen la singularidad.

Answer 6

Bueno, los tweets solo tienen 140 caracteres, por lo que incluso puedes almacenar todo el tweet en la base de datos ...

pero si realmente quieres " hash " De alguna manera, una forma simple sería simplemente tomar la suma de los valores ASCII de todos los caracteres en el tweet:

sum(ord(c) for c in tweet)

Por supuesto, siempre que tenga una coincidencia de hashes, debe verificar que los tweets sean iguales, porque la probabilidad de encontrar dos tweets que den el mismo " sum-hash " Probablemente no sea despreciable.

Answer 7

¿El módulo de archivado de Python? http://docs.python.org/library/shelve.html