用于几乎相似值搜索的算法

Question

我Persons在SQL Server 2008中有表.

我的目标是找到地址几乎相似的人.

地址与列描述state,town,street,house,apartment,postcode和phone.

由于某些州(非美国)和人为因素(地址错误等)存在某些特定差异,因此地址不会以相同的模式填充.

地址中最常见的错误

1. 区分大小写
2. 有人写了"apt.",另一个是"公寓"或"ap".(虽然地址不是用英文写的)
3. 空格,圆点,逗号
4. 写街道名称的差异,比如'博士 Jones str."或"琼斯医生街"或"D.乔恩.st."或"琼斯博士"等

主要问题是数据不是相同的模式,因此很难找到类似的地址.

这种问题有什么算法吗？

提前致谢.

UPDATE

1. 正如我所提到的,地址分为不同的列.我应该生成字符串连接列还是为每列执行步骤？我假设我不应该连接列,但如果我将单独比较列,我应该如何组织它？我是否应该找到每个列的相似性,将它们联合起来或相交或其他什么？
2. 我应该收集一些统计数据还是某种教育算法？

Answer 1

建议接近它:

1. 从各个条目创建单词级n-gram(三元组/ 4克可能会这样做)

2. 对字符串比较进行多次x比较,并按字符串距离对它们进行聚类.有人建议Levenshtein; 对于这种任务有更好的选择,Jaro-Winkler Distance和Smith-Waterman工作得更好.像SimMetrics这样的库可以让生活变得更轻松

3. 一旦你有了n-gram的集群,就可以使用组成子图解析整个字符串,即D.Jones St => Davy Jones St. => DJones St.

不应该太难,这是一个非常常见的问题.

更新:根据您的更新,以下是建议的步骤

1. 将列连接成一个字符串,也许创建一个数据库"视图".例如,

   创建视图vwAddress作为选择顶部10000州城,街道,房子,公寓,邮政编码,州+镇+街道+房子+公寓+邮政编码作为地址从...

2. 编写一个单独的应用程序(比如Java或C#/ VB.NET)并使用像JaroWinkler这样的算法来估计组合地址的字符串距离,以创建许多x多次比较.并写入一个单独的表address1 | 地址n | 相似

您可以使用Simmetrics来获得相似性:

 JaroWinnkler objJw = new JaroWinkler()
double sim =  objJw.GetSimilarity (address1, addres n);

3. 你也可以将它拼成一个地址,以便"1 Jones Street,Sometown,SomeCountry"这样的地址变成"1 Jones Street","Jones Street Sometown"等等......并比较三卦.(甚至4克)以获得更高的精度.

4. 最后,您可以按相似性排序,以获得最相似地址的集群并确定适当的阈值.不知道为什么你被卡住了

Answer 2

我会尝试做以下事情:

• 用多个单词分割地址,同时摆脱标点符号
• 检查所有通常以不同方式书写的模式的单词,并用一个通用名称替换它们(例如替换apartment,ap.,... by apt,替换Dr.博士,......)
• 将所有单词按字母顺序排列在一个字符串中
• 使用模糊字符串比较算法比较所有地址,例如Levenshtein
• 调整Levenshtein算法的参数(例如,您希望在更长的字符串上允许更多差异)
• 最后做一个字符串的手动检查

当然,保持数据"正常"的解决方案是为数据库中的每个特征提供显式字段.否则,你将每隔几个月做一次这个练习.