近似相似值搜索算法

建议这样接近它:

1. 从不同的条目创建单词级n-grams(一个trigram/4-gram可能会做到这一点)。

2. 对字符串比较执行many x many比较,并按字符串距离对其进行聚类。有人建议莱文施泰因,有更好的工作,雅罗温克勒距离和史密斯沃特曼工作更好。像这样的图书馆 SimMetrics 会让生活更轻松

3. 一旦有了n个图群,就可以使用组成子图(即D.Jones ST=>Davy Jones ST.=>Djones ST)解析整个字符串。

不应该太难,这是一个非常普遍的问题。

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

1. 将列串成一个字符串,也许创建一个DB“视图”。例如,

   创建视图vwaddress 作为 选择前10000名 州镇、街道、房子、公寓、邮政编码, 州+镇+街+房子+公寓+邮政编码作为地址 从…

2. 编写一个单独的应用程序(例如在Java或C语言中),并使用像JaroWinkler这样的算法来估计组合地址的字符串距离,以便创建多X多个比较。写在一张单独的桌子上 地址1地址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. 最后,您可以按相似性排序,得到一组最相似的地址,并确定一个合适的阈值。不知道你为什么被卡住

我将尝试执行以下操作:

• 把地址分成多个字,同时去掉标点符号
• 检查所有不同的模式的单词,并用一个通用名称替换它们(例如,replace apartment,ap.,……由APT替换医生,…)
• 将所有单词按字母顺序放回一个字符串中
• 使用模糊字符串比较算法比较所有地址,例如Levenshtein
• 调整Levenshtein算法的参数(例如,您希望在较长的字符串上允许更多的差异)
• 最后手动检查字符串

当然,保持数据“成形”的解决方案是为数据库中的每个特性都提供显式字段。否则,你将每几个月做一次这个练习。

我在这里看到的主要问题是准确定义平等。 即使有人给乔恩写信。还有另一个琼斯。-如果它们是一样的,你永远也说不出。(乔恩·乔尼桑、乔尼森、乔尼多,随便什么;)

我在一家公司工作,我们必须准确处理这个问题——恐怕我不得不告诉你,这种检查导航系统地址列表的工作大多是“手工”完成的。缩写有时依赖于上下文,而且还有其他一些事情使这变得困难。ofc替换字符串等是用python完成的——但是告诉您这样一个缩写的含义,在少数情况下只能通过脚本完成。(“St.”->可以是“Saint”和“Street”。如何决定?不可能……这是人类的工作。

另一个大问题是,如你所说,“有街道上的DJONES”或一个人吗?还是两者兼而有之?哪一个在这里?这个DJ是和琼斯博士一样还是和唐琼斯一样?这是不可能决定的!

你可以在这里用另一个答案给出的列表做一些工作,但是它会给你足够的“误报”或者其他。

您有邮政编码字段!!!!

那么,你为什么不为你的国家买张邮政编码表呢? 用它来清理你的街道/城镇/地区/省份信息?

我在上个世纪做了一个这样的项目。基本上,这是合并后两个客户文件的合并,涉及三个不同来源的姓名和地址。

首先,正如许多海报所建议的,把所有常见的单词、缩写和拼写错误转换成“apt.”、“apment”等常见形式。

然后看一下名字,找出名字的第一个字母,加上第一个姓氏。(想想“医学博士”就不那么容易了。亨利·德·巴斯克维尔·史密斯爵士),但别担心哪里有朋友,两个都要!所以,如果你幸运的话,你会得到Hbaskerville和Hsmathie。现在去掉所有的元音,因为这是拼写变化最多的地方,所以现在你有了hbskrvll hsmth。

你也可以从“H.巴斯克维尔”,“亨利·巴斯克维尔·史密斯爵士”,不幸的是,“哈罗德·史密斯”,得到这些字符串,但我们这里讨论的是模糊匹配!

在街道、公寓和邮政编码字段上执行类似的练习。但不要丢弃原始数据!

现在,我们先来看看有趣的一点,比较每个原始字符串,并为每个完全匹配的字符串打50分。然后通过你的“标准化”字符串,给每一个准确匹配的20分。然后遍历所有的字符串,并对它们共有的每个四个字符或更多的子字符串给出5点。对于每对比较,您将得到一些分数为150,您可以将其视为某种匹配,一些分数小于50,您可以将其视为不匹配,一些中间有一些匹配的可能性。

你需要更多的调整来改善这一点,增加各种规则,比如“史密斯姓减20分”。你真的需要不断的跑动和调整,直到你对结果满意为止,但是,一旦你看到结果,你会有一种很好的感觉,那就是哪一个分数可以被认为是“匹配”,哪一个分数是你需要剔除的误报。

我认为数据量可能会影响哪种方法最适合您。
我有一个 类似的 从不同艺术家的编辑专辑中索引音乐时出现问题。有时艺术家排在第一位,有时是歌曲名,用不同的分隔符样式。

我所做的是计算其他具有相同值的条目上出现的次数,以便有根据地猜测它是歌曲名还是艺术家。

也许你可以用 soundex 或者类似的算法来寻找相似的东西。

编辑: (也许我应该澄清一下,我认为艺术家的名字比歌曲的名字更容易重复出现。)

你在评论中提到的一件重要的事情是,你将以互动的方式来做这件事。

这允许解析用户输入,同时验证对任何缩写词的猜测,并纠正许多错误(例如,电话号码输入的方式适用于某些联系人管理系统-系统尽最大努力分析和更正国家/地区代码、区号和号码,但最终向用户显示他猜测并有机会纠正输入)

如果你真的想做的很好,那么保存邮政编码、城镇、街道、缩写及其变化的数据库/字典可以改进数据验证和预处理。

所以,至少你有完全合格的地址。如果您可以对所有输入进行此操作,那么您将对所有数据进行分类,然后对某些字段严格匹配,对其他字段不严格匹配,匹配分数根据您指定的权重计算。

在您一致地预处理输入之后,n-grams应该能够找到类似的地址。

您是否为此查看了SQL Server集成服务?模糊查找组件允许您查找“接近匹配项”: http://msdn.microsoft.com/en-us/library/ms137786.aspx

对于新的输入,您可以从.NET代码调用包,并将要检查的值行作为一组参数传递,但您可能需要保留令牌索引,使其足够快,以便进行用户交互。

这里有一个地址匹配示例: http://msdn.microsoft.com/en-us/magazine/cc163731.aspx

我假设响应时间不是关键的,问题是在数据库中查找现有地址,而不是合并重复的地址。我还假设数据库包含大量的地址(比如说300万个),而不是一个可以用手或用手进行经济清理的数字。 Amazon's Mechanical Turk .

预计算-识别信息量高的地址片段。

1. 识别每个数据库字段中使用的所有唯一单词,并统计它们的出现次数。
2. 消除非常常见的单词和缩写。(街道、街道、APPT、APT等)

当显示输入地址时,

1. 确定最唯一的单词,并搜索(街道如“%jones%”)包含这些单词的现有地址。
2. 使用预先计算的统计信息估计结果集中有多少个地址
3. 如果估计的结果集太大,请选择第二个最唯一的单词,并在搜索中将其组合起来(街道如“%jones%”,城镇如“%anytown%”)
4. 如果估计的结果集太小,请选择第二个最唯一的单词,并在搜索中将其组合起来(类似街道的“%aardvark%”,或类似城镇的“%anytown”)。
5. 如果 实际的 结果集太大/太小,请重复查询,并像以前一样添加更多的术语。

这样做的目的是在地址中找到足够的具有高信息内容的片段,这些片段可以被搜索到,以提供合理数量的备选方案,而不是找到最理想的匹配。为了更好地容忍拼写错误,可以使用三元、四元图或Soundex代码来代替单词。

显然,如果您有实际州/镇/街道的列表,那么数据库和搜索地址中都可能发生一些数据清理。(我很惊讶 Armenian postal service 没有这样的清单,但我知道有些邮政服务收取的信息过多。)

作为一个实际问题,我所看到的大多数使用中的系统在可能的情况下都会试图通过他们的电话号码来查找人们的帐户:显然,这是否是一个实际的解决方案取决于数据的性质和它的准确性。

(同时考虑横向思维的方法:你能找到一家邮购邮件列表代理公司来为你清理数据库吗?他们甚至可能愿意支付你使用这些地址的费用。)

我找到了一篇很棒的文章。

添加一些DLL为 SQL用户定义函数 我们可以使用字符串比较算法 西蒙斯 图书馆。

检查它

http://anastasiosyal.com/archive/2009/01/11/18.aspx

这种变化的可能性是无数的,即使存在这样的算法,也永远不能证明是愚蠢的。毕竟,你不能对名词进行拼写检查。 您可以做的是提供一个以前输入的字段值的下拉列表,以便在特定名称已经存在的情况下,它们可以选择一个字段值。 最好是为每种价值都有单独的领域,比如公寓等等。

你可以把所有的地址都扔到谷歌地图这样的网络服务上(我不知道这个是否合适),看看它们是否能找到相同的GPS坐标。

一种方法是 Levenshtein distance 地址字段的算法。这将允许您比较字符串的相似性。

编辑 在研究了你正在处理的地址差异种类之后,这可能根本没有帮助。

另一个想法是利用学习。例如,对于每个缩写词及其在句子中的位置,您可以了解缩写词的含义。

3 Jane Dr. -> Dr (in 3rd position (or last)) means Drive
Dr. Jones St -> Dr (in 1st position) means Doctor

例如,您可以使用决策树并让用户培训系统。每种用法的例子可能不多。你不会把单个字母的缩写分类,比如D.Jones,可能是David Jones,也可能是Dr.Jones。但是经过一级翻译之后,你可以查到一个城镇的街道索引,看看你是否可以将D.扩展成街道名称。

同样,在存储之前,您将通过决策树运行每个地址。

感觉应该有一些商业产品来做这个。

一 可能是在数据库中有一个字典表,将所有变量映射到单词的“正确”版本:

*Value* | *Meaning*
Apt.    | Apartment
Ap.     | Apartment
St.     | Street

然后,在比较之前,先把每个单词查字典。

编辑:这个 单独地 太幼稚而不实际(见评论)。