Python中的算法检测数据库中重复/相似字符串,例如邮件主题。

3
我正在下载我的邮件主题的长列表,目的是找到我多年前成为成员的电子邮件列表,并将它们从我的Gmail帐户中清除(这使得我的帐户变得非常缓慢)。
我特别考虑来自同一地址的新闻通讯,而且主题中重复了产品/服务/组的名称。
我知道我可以按特定电子邮件地址的常见项目搜索/排序(我打算这样做),但我想将该数据与重复的主题相关联....
现在,许多主题行将无法进行字符串匹配,但“Google Friends:Our latest news”和“Google Friends:What we're doing today”彼此更相似,而不是随机主题行,如: “维珍航空今天有大优惠” “乘坐维珍航空的飞行”
那么——我应该如何开始自动提取可能更相似的字符串的趋势/示例。
我考虑过并放弃的方法('因为肯定有更好的方法'):
- 提取所有可能的子字符串并按它们出现的频率排序,然后手动选择相关的子字符串 - 去掉前两个单词,然后计算每个子字符串的出现次数 - 比较条目之间的Levenshtein距离 - 一些字符串相似性指数...
其中大多数被拒绝,因为效率极低或可能需要大量手动干预。我想我需要某种模糊的字符串匹配...?
最后,我可以想到一些笨拙的方法来做到这一点,但我正在寻找更通用的方法,以便将其添加到我的工具集中,而不是针对此数据集进行特殊处理。
在此之后,我将匹配特定主题字符串与“发件人”地址的出现-我不确定是否有一种好的方法来构建表示两条消息是否属于“相同电子邮件列表”的数据结构,或通过将所有我的电子邮件主题/发件人地址过滤成可能的“相关”电子邮件池和不相关的电子邮件池-但这是解决此问题之后要解决的问题。
任何指导都将不胜感激。

你要找的词是<a href="http://en.wikipedia.org/wiki/Bayesian_probability">"贝叶斯"</a>。 - Ignacio Vazquez-Abrams
我找到了这个 Stack Overflow 的问题,其中列举了一些更著名的算法。https://dev59.com/03RB5IYBdhLWcg3wWF8H - Rizwan Kassim
2个回答

4
首先,我会将每个字符字符串转换为单词集或多重集(忽略标点符号和大小写差异)。 (如果这不够强大,在第二遍尝试中,我可以尝试相邻单词的成对或甚至三元组,称为bigrams和trigrams)。 因此,所减少的字符串之间的相似度的关键指标是哪些单词在整体上不是高频率的(不是“the”,“and”等;-)是共同的,因此简单的集合交集(或多重集合交集,但对于您的简单用例,我认为只使用bigrams的集合就足够了)应足以衡量“共性”。 对于两个字符串都常见的单词应该更有价值,因此单词在整个语料库中的负对数频率是启发式的绝佳起点。

这是一个有趣的方法 - 一个问题:我在这个项目中的一个目标是学习已经存在的算法,而不是为这个问题编写自己的算法,以便我更好地理解问题空间。这感觉像是一种特定的“适用于此案例”的方法,而不是“这是一个常用工具”,我有点担心计算强度。(不过,这仍然是我迄今为止得到的最好答案,所以谢谢!) - Rizwan Kassim
@RizwanK,处理单词流(通常是规范化的,例如大小写)而不是字符流是信息检索中非常常见的方法(而不是“工具”;-),集合或多重集合(单词、二元组、三元组)也并不罕见。如果您正在寻找现有的Python代码来帮助解决此问题,您可能会在NLTK中找到一些东西,但我不确定。但我绝对不是为了解决您特定的问题而即兴发挥数据管理方法;-)。如果有什么区别,与IR中处理的通常“文档”相比,电子邮件主题的简短性应该会减少计算负载! - Alex Martelli
但我绝对不是即兴发明数据管理方法来解决你特定的问题。 微笑 说得好。你知道你建议的方法有没有名称吗?谢谢! - Rizwan Kassim
@Rizwank,我不确定“将字符字符串转换为单词字符串”等操作是否有特定的名称。 - Alex Martelli

2

平滑BLEU

你也许可以利用主题间的平滑-BLEU得分。BLEU是一种评估指标,用于评分机器翻译系统产生的翻译与人类翻译之间的相似度。平滑BLEU的计算方式与普通BLEU得分相似,不同之处在于当评估文本的短片段时,你需要将n-gram匹配计数加一,以避免乘以零。

相比莱文斯坦距离,平滑BLEU的计算速度应该更快,同时仍然能够捕捉单词顺序信息,因为它检查的是n-gram匹配,而不仅仅是单词匹配。

不幸的是,我没有Python BLEU实现的指针,但你可以在NIST的Perl实现找到这里


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接