在Python中检测数据集中重复/相似字符串的算法，例如邮件主题

Question

我正在下载我所有邮件主题的长列表，目的是找出我多年前订阅过的邮件列表，并想把它们从我的Gmail账户中删除（因为我的邮箱变得很慢了）。

我特别想到的是那些经常来自同一个地址的新闻通讯，它们的主题中重复出现产品、服务或团体的名字。

我知道我可以通过某个特定邮箱地址的常见项目来搜索和排序（我打算这么做），但我想把这些数据和重复的主题行联系起来……

现在，很多主题行可能无法完全匹配，但像“Google Friends：我们的最新消息”和“Google Friends：我们今天在做什么”这样的主题行彼此之间更相似，而不是随便一个主题行。还有像“维珍航空今天有个大促销”和“搭乘维珍航空去旅行”这样的主题行也是如此。

所以——我该如何开始自动提取可能更相似的字符串的趋势或例子呢？

我考虑过的一些方法并且放弃了（因为我觉得应该有更好的办法）：

• 提取所有可能的子字符串，并按出现频率排序，然后手动选择相关的。
• 去掉前面一两个词，然后统计每个子字符串的出现次数。
• 比较条目之间的Levenshtein距离。
• 某种字符串相似度指数……

大多数方法都因为效率低下或需要大量手动干预而被拒绝。我想我需要某种模糊字符串匹配的方法……

最后，我能想到一些笨拙的方法来做到这一点，但我希望找到更通用的解决方案，所以我想把它加入我的工具集，而不是为这个数据集特别定制。

在这之后，我会将特定主题字符串与“发件人”地址进行匹配——我不确定是否有好的方法来构建一个数据结构，表示两条消息有多大可能属于“同一个邮件列表”，或者通过将我所有的邮件主题/发件人地址过滤成可能“相关”的邮件池来实现，但这是在解决这个问题之后要解决的另一个问题。

任何建议都将不胜感激。

Answer 1

平滑BLEU

你可以使用平滑-BLEU分数来比较不同的主题。BLEU是一种评估指标，用来衡量机器翻译的结果和人类翻译的相似度。平滑BLEU的计算方式和普通的BLEU分数差不多，不过在计算n-gram匹配次数时会加一，这样可以避免在评估短文本时出现乘以零的情况。

平滑BLEU的计算速度应该比Levenshtein距离快得多，同时还能保留单词顺序的信息，因为它关注的是n-gram的匹配，而不仅仅是单个单词的匹配。

遗憾的是，我没有找到Python的BLEU实现，不过你可以在NIST的网站上找到一个Perl的实现，在这里。

Answer 2

我会先把每个字符串变成一个单词的集合，或者说是多重集合（也就是可以有重复的单词），在这个过程中不考虑标点符号和大小写的区别。如果这样还不够强大，我可以再进一步考虑相邻的两个单词或者三个单词，这种组合叫做二元组和三元组。衡量两个字符串相似度的关键在于，哪些单词是两个字符串中都出现的，但这些单词在整体中并不是高频词（比如说“the”、“and”等常见词）。所以，简单的集合交集（或者多重集合交集，不过对于你的简单需求，普通集合就足够了，尤其是二元组的集合）就可以用来衡量它们的“共同性”。一个在两个字符串中都出现的单词，如果它在整体中比较少见，那么它的价值就更高，所以可以用这个单词在整个文本中出现的频率的负对数作为一个很好的起点来进行这种判断。