2

为了能够检测特定推文的 RT，我计划将每条格式化推文的哈希值存储在数据库中。

我应该使用什么哈希算法。神秘当然不是必需的。只是一种将数据存储为某种东西的最小方法，如果它相同，则可以以一种有效的方式进行比较。

我的第一次尝试是使用 md5 哈希。但我认为可以有更有效的散列算法，因为不需要安全性。

4

7 回答 7

6

你真的需要散列吗？Twitter 消息足够短（并且磁盘空间足够便宜），最好只存储整个消息，而不是消耗时钟周期来散列它。

于 2009-05-02T18:21:12.453 回答
4

我对 Python 不熟悉（抱歉，Ruby 人在这里打字）但是你可以尝试一些事情。

假设： 随着时间的推移，您可能会存储数十万条推文，因此将一个哈希与表中的“每条记录”进行比较将是低效的。此外，RT 并不总是原始推文的副本。毕竟，通常会包含原作者的姓名，并且会占用 140 个字符的限制。因此，也许您可​​以使用比“哑”哈希更准确匹配的解决方案？

  1. 标记和索引

    以标准方式标记和索引消息的组成部分。这可能包括将散列 #....、at-marked @.... 和 URL 字符串视为“标签”。去除干扰词和标点符号后，您还可以将剩余的词也视为标签。

  2. 快速搜索

    数据库很难快速找到多个组成员（我假设您使用的是 Mysql 或 Postgresql，这很糟糕）。而是尝试使用Sphinx Search等自由文本引擎之一 。他们在解决多个组成员身份方面非常快速（即检查关键字是否存在）。

    使用 Sphinx 或类似工具，我们搜索我们提取的所有“标签”。这可能会返回一个较小的“潜在原始推文”结果集。然后使用相似度匹配算法将它们一一进行比较（这里是 Python http://code.google.com/p/pylevenshtein/中的一个）

现在让我热烈欢迎您来到文本挖掘的世界。

祝你好运！

于 2009-05-02T18:57:56.373 回答
2

我回应 Chris 关于根本不使用哈希的评论（您的数据库引擎有望有效地索引 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
于 2009-05-02T18:52:58.943 回答
2

这里有几个问题。首先，RT 并不总是相同的。有些人添加评论。其他人更改 URL 以进行跟踪。其他人添加了他们正在 RT 的人（可能是也可能不是发起人）。

因此，如果您要对推文进行哈希处理，您需要将其归结为推文的内容，并且只对其进行哈希处理。祝你好运。

上面，有人提到使用 32 位，您将在大约 65K 条推文处开始发生冲突。当然，您可能会在推文 #2 上发生冲突。但我认为该评论的作者很困惑，因为 2^16 = ~65K，但 2^32 = ~4 万亿。所以你有更多的空间。

更好的算法可能是尝试导出推文的“独特”部分，并对其进行指纹识别。它不是散列，而是定义唯一性的几个关键词的指纹。

于 2009-07-16T19:07:47.130 回答
1

好吧，推文只有 140 个字符长，所以你甚至可以将整个推文存储在数据库中......

但如果你真的想以某种方式“散列”它们，一个简单的方法是只取推文中所有字符的 ASCII 值的总和：

sum(ord(c) for c in tweet)

当然，每当你有匹配的哈希时，你应该检查推文本身是否相同，因为找到两条给出相同“sum-hash”的推文的概率可能是不可忽略的。

于 2009-05-02T18:22:41.840 回答
0

Python的搁置模块？http://docs.python.org/library/shelve.html

于 2009-05-02T18:20:51.707 回答
0

您正在尝试对字符串进行哈希处理吗？内置类型可以立即进行散列，只需执行此操作即可hash("some string")获得一些 int。它与 python 用于字典的函数相同，因此它可能是最佳选择。

于 2009-05-03T18:59:30.030 回答