Обнаружение ретвитов с использованием недорогих вычислительных алгоритмов Python

Question

Для того, чтобы иметь возможность определять RT конкретного твита, я планирую хранить хеши каждого отформатированного твита в базе данных.

Какой алгоритм хеширования мне следует использовать. Cryptic, конечно, не является необходимым. Просто минимальный способ хранения данных как чего-то, что затем можно эффективно сравнить, если они одинаковые,

Моя первая попытка была с использованием хэшей md5. Но я полагал, что могут быть алгоритмы хеширования, которые намного более эффективны, поскольку безопасность не требуется.

Answer 1

Вам действительно нужно хешировать вообще? Сообщения Твиттера достаточно короткие (а дисковое пространство достаточно дешевое), поэтому может быть лучше просто сохранить все сообщение, а не использовать циклы часов для его хеширования.

Answer 2

Я не знаком с Python (извините, парень из Ruby пишет здесь), но вы можете попробовать несколько вещей.

Предположения: Скорее всего, со временем вы будете хранить сотни тысяч твитов, поэтому сравнение одного хеша с «каждой записью» в таблице будет неэффективным. Кроме того, RT не всегда являются точными копиями оригинального твита. В конце концов, оригинальное имя автора обычно включается и занимает часть из 140 символов. Поэтому, возможно, вы могли бы использовать решение, которое более точно соответствует «тупому» хешу?

1. Пометка и индексирование

   Пометить и проиндексировать составные части сообщение стандартным способом. это может включать обработку хэша # ...., помеченные @ .... и строки URL как «метка». После удаления шумовых слов и пунктуацию, вы могли бы также рассматривать оставшиеся слова как теги тоже.

2. Быстрый поиск

   Базы ужасны при поиске членство в нескольких группах очень быстро (я предполагаю, что вы используете либо Mysql или Postgresql, которые ужасно на этом). Вместо этого попробуйте один из свободных текстовых движков, таких как Поиск сфинкса . Они очень очень быстро разрешает членство в нескольких группах (т.е. проверка наличия ключевых слов).

   Используя Sphinx или подобное, мы ищем все "теги" мы извлекли. это вероятно, вернет небольшой набор результатов "потенциальных оригинальных твитов". Затем сравните их один за другим используя алгоритм сопоставления сходства (вот один в Python http://code.google.com/p/pylevenshtein/)

Теперь позвольте мне тепло поприветствовать вас в мире text mining

Удачи!

Answer 3

Здесь есть несколько вопросов. Во-первых, RT не всегда идентичны. Некоторые люди добавляют комментарий. Другие меняют URL для отслеживания. Другие добавляют в лицо, что они RT'ing (который может или не может быть автором).

Так что, если вы собираетесь хешировать твит, вам нужно сварить его до мяса твита, и только хэшировать это. Удачи.

Выше кто-то упомянул, что с 32-битными вы начнете сталкиваться с твитами около 65K. Конечно, вы можете столкнуться с твитом № 2. Но я думаю, что автор этого комментария был сбит с толку, так как 2 ^ 16 = ~ 65K, но 2 ^ 32 = ~ 4 трлн. Так что у вас там немного больше места.

Лучшим алгоритмом может быть попытка получить «уникальные» части твита и отследить его. Это не хеш, это отпечаток нескольких ключевых слов, которые определяют уникальность.

Answer 4

Я повторяю комментарий Криса о том, что он вообще не использует хеш (ваш механизм базы данных может эффективно индексировать поля из 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

Answer 5

Ну, твиты имеют длину всего 140 символов, так что вы даже можете сохранить весь твит в базе данных ...

но если вы действительно хотите как-то их "хэшировать", то простым способом было бы просто взять сумму значений ASCII всех символов в твите:

sum(ord(c) for c in tweet)

Конечно, всякий раз, когда у вас есть совпадение хэшей, вы должны проверять сами твиты на одинаковость, потому что вероятность нахождения двух твитов, которые дают одинаковый "суммированный хэш", вероятно, ничтожна.

Answer 6

Вы пытаетесь хэшировать строку правильно? Встроенные типы можно сразу хешировать, просто наберите hash("some string") и вы получите int. Это та же самая функция, которую python использует для dictonarys, так что это, вероятно, лучший выбор.

Answer 7

Модуль полки Python? http://docs.python.org/library/shelve.html