使用计算上廉价的Python散列算法检测转推

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

  •  03-07-2019
  •  | 
  •  

题

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

我应该使用什么样的哈希算法。隐秘当然不是必不可少的。只是将数据存储为一种最小化的方式，然后可以以有效的方式对数据进行比较。

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

有帮助吗？

解决方案

您正在尝试散列字符串吗？内置类型可以立即进行哈希处理，只需执行 hash（“some string”）即可获得一些int。它与python用于dictonarys的功能相同，因此它可能是最佳选择。

其他提示

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

我不熟悉Python（对不起，Ruby家伙在这里打字）但是你可以尝试一些东西。

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

  1. 标记＆amp;索引

    标记和索引组成部分 标准方式的消息。这个 可能包括治疗哈希＃.... 标记为@ ....和URL字符串为 ＆QUOT;标记＆QUOT ;.删除噪音后的话 和标点符号，你也可以 将剩余的单词视为标签 太

  2. 快速搜索

    数据库发现很糟糕 多个团体成员非常 很快（我会假设你使用它们 Mysql或Postgresql，都是 这很可怕）。而是尝试一个 像自由文本引擎的 Sphinx Search 。他们很 解决多个团体成员的速度非常快（即 检查关键字是否存在。）

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

    3. 现在让我热烈欢迎您加入文本挖掘的世界。

    祝你好运！

我回应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

这里有一些问题。首先，RT并不总是相同的。有些人添加评论。其他人更改了跟踪网址。其他人则认为他们是RT的（可能是也可能不是发起者）。

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

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

更好的算法可能是尝试推导出“唯一”算法。部分推文，并指纹。它不是哈希，它是定义唯一性的几个关键词的指纹。

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

但如果你真的想要“哈希”不知怎的，一个简单的方法是只取两条推文中所有字符的ASCII值之和：

sum(ord(c) for c in tweet)

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top