Détection de retweets à l'aide d'algorithmes de hachage Python peu coûteux en calcul

Question

Pour pouvoir détecter la RT d'un tweet particulier, je prévois de stocker les hachages de chaque tweet formaté dans la base de données.

Quel algorithme de hachage devrais-je utiliser? Cryptic n'est bien sûr pas indispensable. Juste un moyen minimal de stocker des données en tant que quelque chose qui peut ensuite être comparé s’il est identique, de manière efficace.

Ma première tentative a consisté à utiliser les hachages md5. Mais j’ai pensé qu’il pouvait exister des algorithmes de hachage beaucoup plus efficaces, car la sécurité n’était pas nécessaire.

Answer 1

Vous essayez de déchiqueter une chaîne, n'est-ce pas? Les types prédéfinis peuvent être hachés tout de suite, il suffit de faire hash ("une chaîne") et vous obtenez un int. C'est la même fonction que python utilise pour les dictonarys, donc c'est probablement le meilleur choix.

Answer 2

Avez-vous vraiment besoin de hachage? Les messages Twitter sont suffisamment courts (et l’espace disque est assez bon marché) pour qu’il soit préférable de stocker le message dans son intégralité, plutôt que de perdre du temps dans les cycles de l’horloge.

Answer 3

Je ne connais pas Python (désolé, Ruby qui tape ici), mais vous pouvez essayer quelques petites choses.

Hypothèses: Vous allez probablement stocker des centaines de milliers de Tweets au fil du temps, ce qui vous permet de comparer un hachage à "chaque enregistrement". dans la table sera inefficace. De plus, les RT ne sont pas toujours des copies conformes du tweet original. Après tout, le nom de l'auteur original est généralement inclus et occupe une partie de la limite de 140 caractères. Alors, vous pourriez peut-être utiliser une solution qui correspond mieux à un "stupide" hash?

1. Balisage & amp; Indexation

   Marquer et indexer les composants de le message de manière standard. Ce pourrait inclure le traitement de hashed # ...., @ @ marqué et les chaînes d'URL comme "tags". Après avoir supprimé les mots parasites et la ponctuation, vous pourriez aussi traiter les mots restants comme des balises aussi.

2. Recherche rapide

   Les bases de données sont terribles à trouver appartenance à plusieurs groupes très rapidement (je suppose que vous utilisez soit Mysql ou Postgresql, qui sont terrible à cela). Au lieu d'essayer un des moteurs de texte libre comme Recherche Sphinx . Ils sont très très rapide à résoudre l'appartenance à plusieurs groupes (c'est-à-dire vérifier si des mots clés sont présents).

   À l'aide de Sphinx ou similaire, nous effectuons une recherche sur tous les " tags " nous avons extrait. Ce retournera probablement un petit ensemble de résultats de "Tweets originaux potentiels". Puis comparez-les un à un en utilisant l'algorithme de correspondance de similarité (en voici un en python http://code.google.com/p/pylevenshtein/)

Permettez-moi maintenant de vous souhaiter chaleureusement la bienvenue dans le monde de l'extraction de texte .

Bonne chance!

Answer 4

Je fais écho au commentaire de Chris sur le fait de ne pas utiliser de hachage du tout (votre moteur de base de données peut, espérons-le, indexer efficacement les champs de 140 caractères).

Si vous souhaitez utiliser un hachage, MD5 sera également mon premier choix (16 octets), suivi de SHA-1 (20 octets).

Quoi que vous fassiez, n'utilisez pas de somme de caractères. Je ne peux pas immédiatement créer une fonction qui aurait plus de collisions (toutes les anagrammes sont identiques), en plus c'est plus lent!

$ 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

Il y a quelques problèmes ici. Premièrement, les RT ne sont pas toujours identiques. Certaines personnes ajoutent un commentaire. D'autres changent l'URL pour le suivi. D'autres ajoutent à la personne qu'ils sont en train de faire (qui peut être ou ne pas être l'auteur).

Donc, si vous voulez hacher le tweet, vous devez le réduire à la chair du tweet, et ne le hacher que. Bonne chance.

Ci-dessus, quelqu'un a mentionné qu'avec le 32 bits, vous commenciez à avoir des collisions à environ 65 000 tweets. Bien sûr, vous pourriez avoir des collisions sur le tweet # 2. Mais je pense que l'auteur de ce commentaire était confus, puisque 2 ^ 16 = ~ 65K, mais 2 ^ 32 = ~ 4 Trillions. Donc, vous avez un peu plus de place là-bas.

Un meilleur algorithme pourrait consister à essayer de dériver le "unique". parties du tweet et empreintes digitales. Ce n'est pas un hash, c'est une empreinte digitale de quelques mots clés qui définissent l'unicité.

Answer 6

Eh bien, les tweets ne contiennent que 140 caractères. Vous pouvez même stocker l'intégralité du tweet dans la base de données ...

mais si vous voulez vraiment "hash" En quelque sorte, un moyen simple serait de prendre la somme des valeurs ASCII de tous les caractères du tweet:

sum(ord(c) for c in tweet)

Bien sûr, chaque fois que vous avez une correspondance de hachages, vous devez vérifier si les tweets sont identiques, car la probabilité de trouver deux tweets donnant le même "sum-hash" est la même chose. est probablement non négligeable.

Answer 7

Le module shelve de Python? http://docs.python.org/library/shelve.html