代码之家 › 专栏 › 技术社区 › namezero

近似字符串匹配概率的预选

approximate metric matching string c++

0

namezero · 技术社区 · 13 年前

最近,我的任务是开发一种算法,用于检查数据库中的重复客户记录。 DB布局非常简单:数以万计的行包含FullName、Street、City、ZIP、Phone等字段。。。

先介绍一下背景:

我对算法做了一些广泛的研究,并决定每个领域都应该有一定的权重使用不同的算法,因为并非所有算法在所有情况下都能同样出色地执行。例如,LastName的权重因子为0.50。当我评估时,我会选择使用哪些算法,以及它们对最终决策的影响:
系数0.25:JaroWinkler
系数0.60:余弦2-克相似性
系数0.15:DamerauLevenstein

一切都很好,只要稍微调整一下,我就能检测到积极的一面,几乎没有错误。到现在为止,一直都还不错。然而,正如你可以想象的那样,当处理数以万计的记录时,运行时O(n^2)——或者实际上E的形式i=0到i=n——不是很有效。不用说,激进的优化,使用编译器优化速度、多线程等,只是权宜之计,因为真正的问题是复杂性。

从本质上讲,我正在寻找一种预过滤潜在匹配的方法,现在已经对此进行了三天的研究。我发现了一些关于R-树、R*-树、KD树、欧几里得向量、minhashing等的有价值的信息。然而,关于所有这些的大多数信息都是高度学术性的。我发现的最有价值的资源是“挖掘海量数据集”,第3章。

现在是我真正的问题:

我已经阅读了所有这些信息,但我不确定如何将其整合在一起。

我在考虑在树或图数据结构中进行某种索引,在那里我可以输入一个字符串,然后说“找到所有匹配概率>0.20的字符串”。这个算法应该非常快。然后,当我得到一个潜在(>0.20)匹配的列表时,我可以去用我的“昂贵”但有选择性的算法比较这几个项目。我认为,这应该会将运行时间缩短到一个非常合理的值。

我一直在努力寻找某种参考代码来做我上面想做的事情,但除了学术文章之外,我似乎没有想出任何其他东西。我确实找到了“simstring”,它实际上是经过编译的,但似乎与7条测试记录不太匹配。。有人能给我指正确的方向吗?肯定有人以前遇到过这种情况,并找到了解决方案。。。

提前非常感谢!

附言:我是用C++做这件事的,但用C#/C/Java/PHP做任何示例都可以。

2 回复 | 直到 13 年前

1

Jerry Coffin 13 年前

作为第一个切入点,我只需选择那些足够接近相同长度的字符串,它们可以在给定的概率内匹配。这不是很有选择性,但(除非你指定了非常宽松的公差)可能会消除相当大比例的不可能匹配非常迅速地(例如,对于像Levenstein这样将插入计数为1次操作的编辑度量,如果您从长度为5的字符串开始,并且需要在5次操作内匹配,那么您可以消除所有长度超过10的字符串,而无需进一步检查)。

这是否有足够的选择性,可以直接进行昂贵的比较,这是一个悬而未决的问题——显然,这将取决于你匹配的字符串长度的可变性。

2

1

namezero 13 年前

我通过做以下事情终于成功地进行了预选: 1.使用客户记录的某些字段来构建2Grams 2.将具有6个Minhash函数家族的2Grams Minhash转换为192位签名 3.使用boost::geometry库的rtree实现在签名上创建6维空间索引 4.为我正在比较的记录选择最近的k条(在我的情况下为30条)记录,并对这些候选者进行原始的“昂贵”比较 5.这将复杂性从E(i,i=n,i=1)降低到大约30n+m,其中m是建立索引所需的时间(令人惊讶的是,几乎可以忽略不计)。

我现在可以在60秒内以高精度运行15000次比较,这是在单线程测试中完成的。多线程到4或8核,这将运行得更快。