地址匹配密钥算法
我有两个单独的表中的地址列表,略微偏离我需要能够匹配。 例如,可以通过多种方式输入相同的地址:
- 110 Test St
- 110 Test St.
- 110 Test Street
虽然简单,但你可以想象更复杂的场景中的情况。 我正在尝试开发一种能够将上述地址作为关键字匹配的简单算法。
例如。 关键可能是“11TEST” – 110的前两个,测试的前两个和街道变体的前两个。 完整匹配键也将包括前5个邮政编码,因此在上面的示例中,完整键可能看起来像“11TEST44680”。
我正在寻找有效的算法或资源的想法,我可以在开发时考虑这些因素。 任何想法都可以是伪代码或您选择的语言。
我们只关心美国的地址。 事实上,我们只查看来自俄亥俄州和密歇根州的250个邮政编码的地址。 我们也无法访问任何邮政软件,尽管对于具有成本效益的解决方案的想法是开放的(它基本上是一次性使用)。 请注意,这是来自政府来源的初始数据转储,因此有关用户如何清理它的建议对我构建应用程序很有帮助,但我希望能够将地址匹配为最佳状态。尽可能好。
我正在研究类似的算法,它应该在我完成时处理加拿大,美国,墨西哥和英国的地址。 我面临的问题是他们在我们的数据库中以3字段明文格式[谁认为这是一个好主意应该被拍摄恕我直言],所以试图处理农村路线,一般交付,大容量接收器,多个国家,省与州与县,邮政编码与邮政编码,拼写错误是一个不小或简单的任务。
拼写错误本身并不是一件小事 – 尤其是当你到达使用法国名字的国家时 – 匹配Saint,Sainte,St,Ste,Saints,Saintes,Sts,Stes,Grand,Grande,Grands,Grandes,有或没有句号或连字符名称的较大部分不会导致性能问题的终结 – 特别是当St可能意味着圣人或街道时,可能会或可能没有输入正确的背景(即女性与男性)。 如果地址输入正确但省份或邮政编码不正确怎么办?
一个开始搜索的地方是Levenstein距离算法 ,我发现它对于消除大部分拼写错误非常有用。 之后,主要是搜索关键字并与邮政数据库进行比较。
我真的很想与目前正在开发工具的任何人合作,也许我们可以互相协助,找到一个共同的解决方案。 我已经成为那里的一部分并且已经克服了我到目前为止提到的所有问题,让其他人研究同样的问题对于反弹意见真的很有帮助。
干杯 – [ben at afsinc dot ca]
如果您更喜欢开发一个而不是使用现有产品,该产品使用了此处提到的许多技术,请参阅: http : //www.melissadata.com/dqt/matchup-api.htm
免责声明:我在公司的发展和工作中发挥了作用。
在英国,我们会使用:
- 房屋名称或号码(其中名称包括公寓楼的单位数)
- 邮编
您当然应该使用邮政编码,但在美国,我相信与英国的邮政编码相比,您的邮政编码涵盖的范围非常广泛。 因此,您需要使用街道和城市。
你的例子不会区分11 Test Street,110 – 119 Test Street等。
如果您的公司可以访问地址查找系统,我会通过它运行所有数据,以便以一致的格式返回数据,可能还有可用于匹配的地址密钥。
如果我要对此进行破解,我会使用预定义的操作顺序将每个地址字符串转换为树。
例如。 110 Test Street Apt 3. Anywhere California 90210 =>
- 获取地址类型。 例如,街道地址具有农村路线所处理的不同格式,并且按国家/地区不同。
- 鉴于这是一个街道地址,获取表示街道类型的字符串并将其转换为枚举(eBoulevard,eRoad等…)
- 鉴于这是街道地址,请拉出街道名称(小写商店)
- 鉴于这是街道地址,请提取街道号码
-
鉴于这是一个街道地址,寻找任何公寓号码(可以在带有短划线的街道号码之前,可以在“Apt。”之后等等)
eStreet //1.an enum of possible address types eg. eStreet, eRuralRoute,... | eStreet //2.an enum of street types eg. eStreet, eBlvd, eWay,... / | \
名称编号Apt | | | 测试110 3
例如。 RR#3 Anywhere California 90210 =>
- 获取地址类型:乡村路线
-
鉴于这是一个乡村路线地址,请获取路线编号
eRuralRoute | 3
你需要为国家/地区和邮政信息做类似的事情。
然后比较生成的树。
这使得比较非常简单,但是,生成树的代码非常棘手。 你想在成千上万的地址上测试它的垃圾。 如果它只是你关心的美国地址,你的问题会更简单; 已经提到的英国地址非常不同,加拿大地址可能包含法语(例如Place D’Arms,Rue Laurent等……)
如果贵公司编写自己的地址规范化工具具有成本效益,那么我建议从USPS地址标准开始 。 或者,有许多供应商提供服务器端工具和Web服务来规范化,纠正和validation地址。
我的公司为此目的使用AccuMail Gold ,因为它不仅仅是标准化和更正地址。 当我们考虑甚至一周工资的成本来开发内部工具时,购买现成产品的选择是显而易见的。
如果您不选择使用现有系统,一个想法是执行以下操作:
- 从地址行中提取数字
- 用空白替换常见的街道词
- 创建匹配字符串
即:“555运河街”:
- 提取号码为“555”+“运河街”
- 替换街道词语给出“555”+“运河”
- 创建匹配字符串给出“555Canal”
“Canal st 555”将给出相同的匹配字符串。
通过街道词我的意思是你的语言中的“街道”的单词和缩写,例如“st”,“st。”,“blv”,“ave”,“avenue”等等都从字符串中删除。
通过提取数字并将它们与字符串分开,无论它们是第一个还是最后一个都无关紧要。
使用主键的标识 ,这将始终是唯一的,并将使以后更容易合并重复。
使用用户界面强制正确输入数据。 让它们在自己的文本框中输入每个组件。 门牌号码在自己的方框中输入,街道名称在自己的方框中,城市在自己的方框中,状态从选择列表中输入等。这将使查找匹配更容易
有两个过程“保存”
- 在初始保存之后,搜索以查找匹配项,向它们显示可能的匹配列表以及新匹配项。
- 在他们选择新的保存后,如果他们选择现有的那个使用该ID
清理数据。 尝试剥离“街道”,“st”,“驱动器”等,并将其存储为StreetType char(1),它将FK用于包含正确缩写的表格,以便您可以构建街道。
看看SOUNDEX和DIFFERENCE
我曾在维护邮件列表的大型公司工作过,他们并没有尝试自动完成,他们使用人员来过滤掉新邮件,因为它很难做到。 规划合并function,以便在发生重复时手动合并重复项,并通过PK连接值。
你可以查看谷歌地图api,看看你是否可以传递你的地址并获得匹配。 我不熟悉它,这只是猜测。