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

StackOverflow https://stackoverflow.com/questions/815313

  •  03-07-2019
  •  | 
  •  

Вопрос

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

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

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

Это было полезно?

Решение

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

Другие советы

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

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

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

<Ол>

  • Пометка и усиление Индексация

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

  • Быстрый поиск

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

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

    • Теперь позвольте мне тепло приветствовать вас в мире интеллектуального анализа текста .

    Удачи!

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

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

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

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

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

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

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

    sum(ord(c) for c in tweet)

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

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

    Лицензировано под: CC-BY-SA с атрибуция
    Не связан с StackOverflow
    scroll top