数据清理和标准化以及地理编码方法

摘要

本技术的实施方式涉及数据清理和标准化以及应用数据清理和标准化的地理编码方法。示例性方法包括清理地理数据集合，以及利用标准化的编辑距离算法使清理后的地理数据标准化。

说明书

相关申请的交叉引用

本申请要求于2013年8月14日提交的标题为“用于地理编码和校 正地理编码的数据的系统及方法(SystemandMethodsforGeocodingand CorrectingCeocodedData)”的第61/865,984号美国临时申请的优先权， 该申请通过引用以其整体并入本文，该申请的整体包括其中所引用的全 部参考文献。

技术领域

本技术大体涉及地理编码和地图制作，并且更具体地，但不限于， 涉及恰当地对兴趣点进行地理编码的系统和方法，其中每个兴趣点由来 自不同数据库的多个有差异的表达表示。本技术使这些有差异的表达一 致化，以增加这些地理编码的位置的一致性。

发明内容

本技术的实施方式包括一种方法，包括：

(a)接收字符的两个多片段集合，字符的两个多片段集合中的每个 包括多个片段，片段中的每个包括格式；

(b)通过以下操作清理字符的两个多片段集合中的每个：(i)如果 片段的格式未处于标准化格式，则将字符的多片段集合的多个片段中的 片段转化成标准化格式；以及(ii)通过根据转化的片段和未转化的片段 中产生连续字符串来缩小字符的两个多片段集合中的每个；以及(c)利 用字符的清理后的多片段集合计算距离分数，距离分数表示字符的清理 后的多片段集合中的字符之间的差异。

本技术的其它实施方式包括一种计算装置，包括：(a)存储器，用 于存储可执行指令；以及(b)处理器，用于执行可执行指令，以：(i) 接收字符的两个多片段集合，字符的两个多片段集合中的每个包括多个 片段，片段中的每个包括格式；(ii)通过以下操作清理字符的两个多片 段集合：(1)如果片段的格式未处于标准化格式，则将多片段字符串的 多个片段中的片段转化成标准化格式；以及(2)通过根据多个转化的片 段中产生连续字符串来缩小字符的两个多片段集合；(iii)计算用于字符 的清理后的多片段集合的标准化编辑距离(NLD)，其中标准化编辑距离 通过以下操作计算：(A)计算用于字符的清理后的多片段集合的编辑距 离(LD)；(B)利用方程：NLD＝1-(LDexp1-abs([LSexp1]-[LSexp2]))/min ([LDexp1],[LSexp2])将LD标准化，其中LSexp1是字符的清理后的多片 段集合的第一字符串的长度，并且LSexp2是字符的清理后的多片段集合 的第二字符串的长度。

本技术的另外的实施方式包括一种地理编码的方法，地理编码的方 法包括：(a)接收可能表示同一兴趣点的、字符的两个多片段集合，字 符的两个多片段集合中的每个包括多个片段，片段中的每个包括格式； (b)如果片段的格式未处于标准化格式，则将多片段字符串的多个片段 中的片段转化成标准化格式；(c)通过根据转化的片段和未转化的片段 中产生连续字符串来缩小字符的两个多片段集合中的每个；(d)利用字 符的清理后的多片段集合计算距离分数，距离分数表示字符的清理后的 多片段集合中的字符之间的差异；(d)将距离分数与阈值比较；以及(e) 如果距离分数小于阈值，则将数据库中字符的清理后的多片段集合确定 为表示同一兴趣点。

附图说明

图1是用于实施本技术的多方面的计算环境的高阶示意图。

图2是示出了地理编码过程的示意性流程图。

图3是地图的立体图，该立体图示出了表示同一物理兴趣点的两个 地理编码点之间的物理距离计算的过程。

图4是本技术的方法的流程图。

图5是用于执行标准化编辑距离计算和物理距离计算的方法的流程 图。

图6是用于建立并使用地理数据实例的片段/字段排列的方法的流程 图。

图7是用于实现根据本技术的实施方式的计算系统的示意图。

具体实施方式

在以下的说明中，为了说明而非限制的目的，阐述了例如具体实施 方式、过程、技术等的具体细节以便提供对本发明的彻底理解。然而， 对本领域技术人员显而易见的是，本发明可以以背离这些具体细节的其 它实施方式实施。

在本说明书的各个部分中的“一个实施方式”或“实施方式”意指 结合该实施方式描述的特定特征、结构或特点包括在本发明的至少一个 实施方式中。因此，在本说明各个部分的不同位置的表达“在一个实施 方式中”或“在实施方式中”或“根据一个实施方式”(或者具有类似意 思的其它表达)的出现不必全部表示相同的实施方式。此外，在一个或 多个实施方式中，这些特定的特征、结构或特点可以以适当的方式结合。 此外，根据本文中的论述的上下文，单数的词语可包括其复数形式，并 且复数的词语可包括其单数形式。类似地，用连字号连接的词语(例如 “on-demand”)有时可以与其未用连字号连接的版本(例如“ondemand”) 互换使用，用大写字母开头的词条(例如“Software”)可以与不用大写 字母开头的版本(例如“software”)互换使用，复数词语可以用或者不 用撇号表示(例如，PE's或PEs)，并且用斜体印刷的词语(例如，“N+1”) 可以与其不用斜体印刷的版本(例如“N+1”)交换使用。这种偶尔可互 换的使用不应被认为是互相不一致。

此外，一些实施方式可以“用于……(执行任务或任务的集合)的装 置”的形式描述。应理解，本文中的表述“用于……的装置”在结构上例 如是处理器、存储器、例如照相机的I/O装置或它们的组合。可替代地， “用于……的装置”可包括描述功能或方法步骤的算法，而在其它实施 方式中，“用于……的装置”可用数学公式、可编程排序程序表示，或者 表示成流程图或信号图。

本文中所使用的术语仅是为了描述特定的实施方式，并且不意在限 制本发明。如在本文中所使用的，单数形式的“一个(a或an)”和“该 (the)”也旨在包括复数形式，除非上下文中另外明确指示。还应进一步 理解，当在本说明书中使用时，术语“包括(comprises)”和/或“包括 (comprising)”指出所述的特征、整体、步骤、操作、元件和/或组件的 存在，但是不排除一个或多个其它特征、整体、步骤、操作、元件、组 件和/或它们的组合的存在和附加。

首先，应注意术语“联接的”、“连接的”、“连接”、“电连接”等在 本文中可互换使用，以泛指处于电连接/电子连接的状态。类似地，当第 一实体电力地向第二实体发送和/或接收(无论通过有线装置还是无线装 置)信息信号(无论包括数据信息还是包括非数据/控制信息)而不考虑 这些信号的类型(模拟或数字)时，第一实体被认为是与第二实体(一 个或多个实体)“通信”。应进一步注意，本文中所示出并讨论的各种附 图(包括组件图示)仅为了说明性的目的，并且不是按比例描绘的。

地理编码通常是不精确的处理，这是因为表示兴趣点的源数据可能 是不正确的和/或缺乏完整信息。这种错误的源数据使得兴趣点被不正确 地标绘在地图上，而这对地图的终端用户会产生有害影响，并且会影响 地图供应商的可信度。

兴趣点在地图上的正确标绘对保持特征的位置映射的一致性和可用 性至关重要。从经验出发，已经确定例如旅馆的全部兴趣点的25％未被 正确标绘。例如，这些旅馆可能放置在距它们的正确位置超过1英里远 的位置。这归因于用于旅馆的不完整的、错误的或未充分格式化的地理 位置数据(在下文中称为“地理数据”)。此外，映射系统通常依托多个 有差异的数据库，多个有差异的数据库中的每个可能使用不同格式来定 义兴趣点。例如，一个旅馆数据库可将旅馆的地址格式化成“205^thAvenue West,NewYork”，而另一旅馆数据库可将完全相同的旅馆的地址格式化 成“20FifthAve.,W.newyork”。尽管这些地址指代位于同一位置的同一旅 馆，但地址的格式化可能在将旅馆标绘在地图上时引入错误。

有利地，本技术利用地理数据清理、距离和标准化处理来弥补这些 不足之处。应理解的是，虽然将在地理数据的背景中对本技术进行描述， 但是本文中所描述的清理和标准化处理可应用于需要数据格式一致的任 何数据处理方法。例如，在输入数据容易以各种格式提供从而在应用输 入数据时可导致错误的情况下，可使用本技术。

本技术通过识别需要验证的兴趣点和对其重新格式化，改进了地理 编码处理。本技术使用本文中所描述的地理数据格式化方法，对来自不 相关的数据库的兴趣点进行匹配，并且用映射逻辑整合来自不相关的数 据库的这些地理数据供给，以提供良好的标绘精度。本技术还精确地标 绘新的兴趣点。因此，本技术的一些实施方式在地理编码以及地图制作 的技术领域提供了改进，并且具体地而非限制性地，对利用根据本技术 的实施方式清理且标准化的地理数据映射兴趣点提供了改进。本技术的 这些和其它优点参照图集(图1至图7)在下文中提供。

图1是本技术的计算架构(在下文中称为架构100)的高阶示意图。 架构100包括数据清理和标准化系统(在下文中称为“服务器105”)、第 一地理数据源10、第二地理数据源115、网络120和格式化的地理数据 数据库125。

服务器105、第一地理数据源110和第二地理数据源115通过网络 120互相通信联接。网络120可包括任何适当的私人或公共通信网络。

通常，地理数据由服务器105从多个地理数据源例如第一地理数据 源110和第二地理数据源115接收。应理解的是，还可以包括更多的地 理数据源。这些地理数据源中的每个可为服务器105提供表示各种兴趣 点(POI)的地理数据实例。例如，第一地理数据源110和第二地理数据 源115可以是与提供旅馆预约的网站相关的旅行服务数据库。这些地理 数据源还可以是旅馆拥有的私有旅馆数据库。

地理数据实例，例如地理数据实例110A-N，可包括任何数量的信息 字段。例如，地理数据可包括信息字段例如POI名称、街道地址、城市、 州、国家、邮政编码、电话号码、传真号码、网站/域名/URL(统一 资源定位器)、坐标例如经纬度以及这些信息字段的组合。根据本技术， 还同样考虑使用应为本领域普通技术人员所知的其它信息字段。在一些 实施方式中，地理数据的字段称为片段。因此，地理数据的实例可具有 多个片段(例如，多个字段)。

地理数据可作为文件、数据库条目、制表符定界文件、逗号分隔值 文件或其它类似的数据结构而存储在数据库中。如上所述，来自不同的 源的用于相同兴趣点的地理数据相对于彼此可能是有差异的。例如，一 些字段可能被不同地格式化，例如，在街道地址在一个地理数据实例中 规定成“145^thSt.”而在另一地理数据实例中规定成“145Street”时。在 有些情况下，地理数据字段可能是不正确的。例如，兴趣点的城市可能 是“帕洛阿尔托(PaloAlto)”，而实际上应该是“门洛帕克(MenloPark)”。 此外，语言差异可能导致不正确的地理编码。例如，街道地址在一个地 理数据实例中可能列为“123Avenida”，而在另一地理数据实例中列为 “123Avenue”。如果映射功能不能补偿语言差异，那么语言上的差异可 能导致兴趣点的不正确的标绘。

在一些实施方式中，通过服务器105获得的地理数据最初通过确定 地理数据中的兴趣点(POI)处理。服务器105将获得地址字段，例如来 自从地理数据源获得的地理数据的街道地址、城市、州、邮政编码等等。 服务器105使用地址字段将POI标绘在地图上。

服务器105然后确定POI地址的潜在精度，并且还选择相互匹配的 任何POI。在一些实施方式中，服务器105通过计算标绘在地图上的POI 地址之间的距离确定POI地址的精度。服务器105还考虑第一地理数据 源110和第二地理数据源115的初始精度等级。也就是说，在有些情况 下，第一地理数据源110和第二地理数据源115将各自向服务器105提 供精度值，该精度值表示该地理数据源提供的地理数据的精确程度。在 有些情况中，如果这些精度值被确定为不正确的，则服务器105可不信 任由第一地理数据源110和第二地理数据源115提供的精度值。

POI地址可通过将这些POI地址与包括经纬度信息的坐标数据库比 较来进行验证。在有些情况中，POI地址可包括坐标，并且这些地理数据 坐标可以与坐标数据库中的坐标比较，以确定POI地址的精度。例如， 如果POI地址是“1234MainStreet”以及37纬度和-132经度，则服务器 105可在坐标数据库中查寻坐标，并且将POI街道地址与坐标比较，以得 知POI街道地址是否大体上对应于坐标。在这两个点可标绘在地图上并 且两者之间的距离可忽略时，POI街道地址和坐标是大体上对应的。例如， 当地图的用户使用该地图不会被引导至错误的位置时，该距离是可以忽 略的。在有些情况中，距离的间隔尺寸和紧密度可通过位置确定。例如， 当POI位于存在诸多单行道的人口密集的城市地区时，该距离需要是更 小的，以降低用户会采取错误的街道或到达错误的位置的可能性。在另 一方面，如果POI位于不存在可能会使终端用户困惑的邻近位置的人口 稀少的地区，则该距离可以是较大的。

总之，地图系统管理员可设置用于距离的阈值。如果距离大于阈值， 则POI可通过服务器105被标记成不正确的或需要重新编码。也就是说， 服务器105可请求地理数据源将地理数据重新编码。可替代地或此外， 在某些实施方式中，用于POI的地理数据可被服务器105忽略或者删除。

现同时参考图1和图2，服务器105还配置为管理用于同一POI的地 理数据的多个实例。在多个数据源提供关于同一POI的地理数据时，POI 重复出现。此外，多个旅馆预约系统可向服务器105供给它们的旅馆POI 地理数据。为了在地图上呈现这些旅馆POI地理数据实例，通过服务器 实施比较和/或一致化。

根据某些实施方式，服务器105至少包括处理器150和存储器155。 存储器155通常包括清理模块160、距离模块165和标绘模块175。

处理器150运行存储在存储器中的清理模块160以执行各种操作。 在一个实施方式中，清理模块160配置为将地理数据的实例拆分成字段。 应理解的是，地理数据的实例通常还可称为字符的多片段集合。例如， 地理数据的一个实例可包括“HotelMainstreet1234Main St.,Anytown,State,USA，99991,(34,-123)”。此外，地理数据可具有任何格 式。例如，地理数据可包括布置在成列列表或成行列表中的字段、逗号 分隔值的集合、字段的制表符定界集合或可能适当的任何其它格式。服 务器105将地理数据的实例拆分成分离的字段，例如：名称＝Hotel Mainstreet；街道地址＝1234MainSt.；城市＝Anytown；州＝State；国家＝USA； 邮政编码＝99991；纬度＝34；经度＝-123。

在一些实施方式中，清理模块160将地理数据的实例中的所有大写 字母转化成小写字母。此外，清理模块160会将所有非字母数字字符从 地理数据的实例中除去。非字母数字字符的除去使字段能够串接或简化 成单个字符串。

清理模块160然后可用多个特殊用途的清理器例如字段清理模块 180A-N处理地理数据的实例的字段。通常，如果片段的格式未处于标准 化格式，则清理模块160配置为将片段或字段转化成标准化格式。字段 清理模块180A-N的以下示例用于将字段转化成标准格式，以便使表示同 一POI的地理数据的有差异的字段一致化。

字段清理模块180A-N的数量将取决于存在于地理数据的实例中的 字段数量。字段清理模块180A-N中的每个配置为清理特定类型的地理数 据字段。例如，名称字段清理模块180A清理地理数据的实例中的名称字 段。在一个示例中，如果名称字段既不包括词语“hotel(旅馆)”也不包括 “inn(客栈)”或另一类似的词语例如“汽车旅馆(motel)”，则名称字段 清理模块180A会将词语“旅馆(hotel)”加入名称字段。因此，用于名 称字段的标准化格式需要词语“旅馆”存在于名称字段中。街道地址字 段清理模块180B配置为使地理数据的实例的街道字段标准化。例如，街 道地址字段清理模块180B可执行字段数据的替换，例如将“Avenida”、 “Avenue”和“Av”替换成“ave”。因此，“ave”是标准化格式。在另 一示例中，“Four”、“Fourth”、“4^th”、“IV”、“quatre”和“cuatro”全部 变换成标准化格式“4”。因此，对于街道地址数据的每种类型，应用了 标准化格式，以使得诸多不同的格式被标准化成标准格式。

在一个非限制性示例中，地理数据的第一实例包括街道地址字段 “205thAvenueWest，NewYork”，其被转化成“205avewnewyork”。大 写字母转换成小写字母，并且移除了非字母数字字符例如间隔和逗号。 然后，对地址字段进行处理，以将“5th”更换成“5”、将“avenue”更 换成“ave”并且将“west”更换成“w”。

在另一示例中，地理数据的第二实例包括街道地址字段“20FifthAve., W.,newyork”，其被转化成“205avewnewyork”。大写字母转换成小写字 母，并且除去了非字母数字字符例如间隔和逗号。然后，对一个地址字 段进行处理以将“Fifth”更换成“5”。

在该示例中，地理数据的第一实例可来自第一地理数据源110，并且 地理数据的第二实例可来自第二地理数据源115。

城市、州和国家字段也可以按照类似的方式使用它们相应的标准化 模块进行清理。在清理/标准化后，清理后的地址字段和城市字段可通 过服务器105提交至地理编码引擎170，地理编码引擎170识别地理数据 的实例之间可能的匹配。地理编码引擎170可与服务器105一体形成， 或者在一些实施方式中包括一个或多个第三方地理编码引擎。

在另一示例中，清理后的地址和城市可提交至本地目录引擎185例 如虚拟的白页或黄页，以确定清理后的地址是否与本地目录引擎185中 的列表相关。

在一个实施方式中，距离模块165被运行，以计算清理后的地理数 据的两个实例之间的编辑距离(Levenshteindistance，LD)。通常，编辑 距离在两个字符串序列之间计算。本领域普通技术人员应能够计算用于 地理数据的一对清理后的字符串的LD。通常，LD是表示将第一字符串 转换为对应的第二字符串需要对第一字符串进行替换的数量的数值。编 辑距离具有多个简单的上边界和下边界。这些包括：(a)LD总是至少为 两个字符串的尺寸的差异；(b)LD至多为较长的字符串的长度；(c)当 且仅当字符串相等时，LD是零；(d)如果字符串相同尺寸，汉明间距是 关于LD的上边界；(e)两个字符串之间的LD不大于它们距第三字符串 的LD之和(三角不等式)。

例如，第一清理后的字符串包括根据“100AvenidadeRepublica, Madrid”清理的“100avedereublicamadrid”，并且第二清理后的字符串是 根据“100RepublicaAvenue,Madrid”清理的“100republicaavemadrid”。

“100AvenidadeRepublica,Madrid”和“100RepublicaAvenue, Madrid”之间的LD是17，这意味着必须对“100AvenidadeRepublica, Madrid”进行17次替换以获得“100RepublicaAvenue,Madrid”。还可以 对第一清理后的字符串和第二清理后的字符串计算Ldexp1，其为9，这 意味着必须对“100avedereublicamadrid”进行九次替换以获得 “100republicaavemadrid”。

值得提到的是，距离模块165将来自两个地理数据实例的类似字段 类型进行比较或匹配。例如，距离模块165将一个地理数据实例中街道 地址字段与第二地理数据实例的街道地址字段比较。不考虑字段类型而 进行字段之间的比较会导致距离模块165产生粗劣的比较结果。

距离模块165通过首先确定第一清理后的字符串的长度(其是22) 和第二清理后的字符串的长度(其是21)，将LDexp1值标准化。

在确定这些长度值之后，距离模块165利用下列等式计算标准化的 LD(NLD)值：

NLD＝1-(LDexp1-abs([LSexp1]-[LSexp2]))/min([LDexp1],[LSexp2]) [式1]

其中LSexp1是字符的清理后的多片段集合中的第一字符串的长度， LSexp2是字符的清理后的多片段集合中的第二字符串的长度，并且 LDexp1是为清理后的这一对字符串而计算的LD。距离模块165的输出 是用于由距离模块165进行比较的、地理数据的一对实例中的每个的 NLD分数。

详细地，距离模块165从第一字符串的长度中减去第二字符串的长 度，并且将该值除以LDexp1和第二字符串的长度中的最小值。获得以上 所得到的值的绝对值并且从1中减去该值。然后，从LDexp1中减去该绝 对值。然后，距离模块165将该最终的数乘以100以获得NLD。在以上 的示例中，第一清理后的字符串和第二清理后的字符串的NLD是61.9％。

在一些实施方式中，距离模块165可计算用于地理数据实例的片段/ 字段的各种置换的NLD值。继续以上示例，地址字段的置换(在单词顺 序上的改变)将包括“100deReublicaAve,Madrid”和“100RepublicaAve, Madrid”。清理后的版本将是“100dereublicaavemadrid”和 “100republicaavemadrid”。利用式1为这对地理数据实例计算出了90.1％ 的NLD值。可通过对从地理数据实例中提取的字段的重新排列，执行多 种类型的置换。在一个实施方式中，距离模块165可执行两个地理数据 实例之间的匹配字的成对比较。成对比较功能是为了减小为所得到的清 理后的字符串而计算的LD。距离模块165还为地理数据实例的字段的每 个可能的置换计算NLD值，并且确定最高排序的NLD值。

此外，置换过程可以以字段级或片段级出现，以使得字段的子部分 被重新排列。例如，“100AvedeReublica,Madrid”可被重新排列成“100 deReublicaAve,Madrid”或“100ReublicadeAve,Madrid”。

参考图6，示出并详细解释了用于建立并且使用地理数据实例的片段 /字段的置换的过程的示例性流程图。

在一些实施方式中，距离模块165可应用NLD阈值，NLD阈值确定 何时NLD太大而不能将第一清理后的字符串和第二清理后的字符串考虑 成对应于同一POI。例如，NLD阈值可以是80％。因此，小于80％的任 何NLD将指示地理数据实例可能不能表示同一POI。尽管在NLD小于 80％时地理数据实例有可能确实表示同一POI，地理数据实例可能需要地 图标绘或人验证以便做出最终决定。地理数据的实例(第一清理后的字 符串和第二清理后的字符串从其中获得)可被标记以备进一步复查。此 外，服务器105可提示地理数据源它们的数据在格式和/或内容上可能不 正确。NLD阈值可设置成所需的任何灵敏度。

虽然以上示例预期使用80％NLD阈值，但是应理解的是，该NLD 阈值仅是一个示例，并且NLD阈值可设置成任何所需值，以使得系统的 终端用户能够设置用于比较地理数据实例的所需灵敏度级别。

在另一示例中，为第一清理后的字符串“sheratonhotel”和第二清理 后的字符串“sheratonhoteldowntowntoronto”计算NLD。在该示例中，虽 然LD是指示字符串彼此不完全相似的15，但是计算出NLD是100％， 指示清理后的字符串相同并且均表示同一POI。虽然LD指示第一字符串 和第二字符串之间大的距离差异，但是在利用式1取第一字符串和第二 字符串的最小值时，NLD等式实质上忽略了第二字符串中额外的字符。

因此，本技术通过利用可用于各种目的的标准化的LD提供了与使用 普通的LD计算相比的诸多优点，也就是说，将通常会被认为高度不符合 (例如，较大距离)的字符串确定为表示同一内容。在一个实施方式中， 该内容包括地理数据，但是其它内容包括由多个字段(例如，片段)表 示的任何类型的数据。

在一些实施方式中，如果NLD小于80％，则距离模块165可实施两 个清理后的地址之间的物理距离核对。例如，距离模块165可与标绘模 块175配合以确定两个点之间的物理距离。标绘模块175会将第一清理 后的地址标绘在地图上并且将第二清理后的地址标绘在地图上。距离模 块165可计算第一清理后的地址和第二清理后的地址之间的物理距离。 例如，距离模块165可计算地图上两个标绘的点之间的地理距离。

因为物理距离小于100英尺，所以，即使NLD小于阈值，距离模块 165也会将第一清理后的地址和第二清理后的地址考虑成表示同一POI。 回到以上示例，第一清理后的字符串“100avedereublicamadrid”和第二 清理后的字符串“100republicaavemadrid”在标绘在地图上时显示物理距 离为零。因此，虽然NLD(61.9％)稍微小于80％的阈值，但是清理后 的地址确实表示同一POI。

参考图3，第一清理后的地址在地图300上标绘为点305。第二清理 后的地址在地图300上标绘为点310。实际的兴趣点是位于两个街道320 和325的十字路口处的旅馆315。第一点305和第二点310之间的距离 330可通过确定用于点305和点310中的每个的坐标计算(或估算)。在 一个实施方式中，如果地图300包括坐标，则坐标可被确定。当点在地 图300上重叠时，坐标可被估算。

此外，由于距离330实质上是零，因此确定点305和点310描述对 应于旅馆315的同一POI。此外，服务器105可比较地理数据实例的名称 字段或其它字段以证实第一点和第二点之间的一致。

图4是本技术的示例性方法的流程图。该方法包括405接收字符的 两个多片段集合(例如，地理数据的实例)。应理解，字符的两个多片段 集合中的每个包括多个片段或字段。此外字段中的每个包括格式。例如， POI名称、城市、街道地址、州等等。

如果片段的格式未处于标准化格式，则该方法包括在415通过首先 将多片段字符串的多个片段中的片段转换成标准化格式，来对字符中的 两个多片段集合中的每个进行清理。转换可以对未处于标准化格式的每 个片段执行。例如，标准化格式“5”可应用于字段例如“fifth”、“5^th”、 “V”等等。如果需要，则可使每个字段标准化。

接着，清理包括在420通过根据转化的片段和未转化的片段建立字 符的连续字符串使字符的两个多片段集合中的每个缩小。也就是说，一 些片段/字段可能不需要清理。服务器105将使转化的片段和未转化的片 段两者结合成一个字符串。缩小过程可包括在425将大写字母更换成小 写字母，并且在430将非字母数字字符除去。

接下来，该方法包括在435利用字符的清理后的多片段集合计算距 离分数。应理解的是，距离分数表示字符的清理后的多片段集合中的字 符之间的差异。在图5中示出并且描述了用于计算距离分数的示例性方 法。

参考图5，示出了用于计算标准化编辑距离(NLD)的方法。该方法 包括在505接收第一清理后的字符串和第二清理后的字符串(例如，清 理后的字符串)。在一些实施方式中，该方法包括在510计算第一字符串 和第二字符串两者的编辑距离。该方法还包括515确定第一字符串和第 二字符串中的每个的字符长度并且利用该字符长度计算NLD。NLD可利 用以上更详细描述的式1计算。

如上所述，NLD是根据字符内容表示字符串的“接近程度”的百分 比分数。例如，“1234mainst”和“1234mainst”的NLD是100％，然而 “100avedereublicamadrid”和“100republicaavemadrid”的NLD是61.9％。

该方法还包括在520将NLD与阈值比较，并且在525如果NLD不 满足或超过阈值时，实施第一字符串和第二字符串之间的物理距离计算。 例如，61.9％的NLD可以与80％的阈值比较。由于NLD不满足阈值，所 以服务器105可实施物理距离计算。

例如，服务器可将第一字符串和第二字符串标绘在地图上，并且更 具体地，标绘第一字符串和第二字符串的街道地址。在其它实施方式中， 如果第一字符串和第二字符串包括坐标，则第一字符串和第二字符串可 利用坐标标绘。标绘的点之间的距离可被确定并且与距离阈值比较。例 如，如果距离小于100英尺，则标绘的点可被认为是表示同一POL。

图4和图5的流程图可包括与流程图中所描述的那些步骤相比更少 或者更多的步骤。另外，流程图的方法步骤可根据说明书或本文中提供 的示例进行替代。

图6是用于建立并且使用地理数据实例的片段/字段的置换以及计 算并且比较为成对的地理数据实例生成的NLD值的方法的流程图。如上 所述，以下的示例会将地理数据实例称为“字符的多片段集合”。

首先，选择出字符的两个多片段集合中的第一个。字符的两个多片 段集合中的第二个保持不变。在选择了字符的两个多片段集合中的第一 个后，该方法包括在605根据字符的两个多片段集合中的第一个建立字 符的多个置换的多片段集合。这个过程包括将字符的两个多片段集合中 的这一个集合的多个片段中的片段的字符重新排序，以建立置换的片段。 重新排列的步骤对于字符的第一个多片段集合发生多次以建立字符的多 个置换的多片段集合。

接下来，该方法包括建立字符的成对的多片段集合。这些对包括字 符的多个置换的多片段集合中的一个和字符的两个多片段集合中的第二 个。例如，第一对将包括字符的多片段集合“HotelCalifornia,LosAngeles downtown”和字符的第二多片段集合“LosAngelesCaliforniahotel”。在 第二配对中，字符的置换的多片段集合“CaliforniaHotelLosAngeles downtown”与字符的第二多片段集合“LosAngelesCaliforniahotel”配对。 在第三配对中，字符的另一置换的多片段集合“LosAngelesCalifornia Hoteldowntown”与字符的第二多片段集合“LosAngelesCaliforniahote” 配对。

接下来，该方法包括在610使字符的成对的多片段集合标准化。此 外，字符的成对的多片段集合包括多个置换的多片段集合的各种组合以 及如上所述的字符的两个多片段集合中的第二个。

在一个实施方式中，该方法包括在615为字符的成对的多片段集合 中的每对计算标准化编辑距离(NLD)。

在一些实施方式中，该方法包括确定字符的所有成对的多片段集合 中最高排序的NLD。

在另一实施方式中，该方法包括在620从字符的所有成对的多片段 集合中确定最小NLD。具有最小NLD的一对被认为是地理编码的实例 (例如，字符的成对的多片段集合)中最佳匹配的一对。

图7是以计算机系统1的形式的示例性设备的图形表示，在计算机 系统1中，可执行用于使得设备执行本文中所讨论的方法中的任何一个 或更多个的指令的集合。在不同的实施方式中，设备作为独立的装置操 作或可连接(例如，网络连接)至其它设备。在网络连接的部署中，设 备可以在服务器-客户网络环境中作为服务器或客户设备操作，或者可在 对等(或分布式)网络环境中作为对等设备操作。设备可以是个人电脑 (PC)、平板PC、机顶盒(STB)、个人数字助理(PDA)、蜂窝式电话、 便携式音乐播放器(例如便携式硬盘音频设备例如活动图像专家组音频 层3(MP3)播放器)、环球网设备、网络路由器、开关或电桥，或者可 以是能够执行指明将由该设备采取的行动的一组指令(按顺序的或不按 顺序的)的任何设备。而且，虽然仅示出了一个设备，但是词语“设备” 还应理解为包括设备的任何集合，这些设备单独或共同执行一组(或多 组)指令以实施本文中所讨论的方法中的任何一个或更多个。

示例性计算机系统1包括一个处理器或多个处理器5(例如，中央处 理器(CPU)、图形处理单元(GPU)或者这两者)以及主存储器10和 静态存储器15，主存储器10和静态存储器15通过总线20互相通信。计 算机系统1可进一步包括视频显示器35(例如，液晶显示器(LCD))。 计算机系统1还可包括一个(多个)字母-数字输入装置30(例如，键盘)、 光标控制装置(例如鼠标)、语音识别或生物特征测量验证单元(未显示)、 驱动单元37(也称为磁盘驱动器单元)、信号生成装置40(例如，扬声 器)和网络接口装置45。计算机系统1还可包括数据加密模块(未显示) 以将数据加密。

磁盘驱动单元37包括计算机或设备可读介质50，在计算机或设备可 读介质50上存储了指令的一个或多个集合和包括或利用本文中所描述的 方法或功能中的任何一个或多个的数据结构(例如，指令55)。指令55 在其通过计算机系统1的执行期间还可完全或至少部分地归于主存储器 10内和/或归于处理器5内。主存储器10和处理器5也可构成设备可读 介质。

指令55还可利用多个公知的传送协议中的任何一个(例如，超文本 传送协议(HTTP))经由网络接口装置45通过网络140(见图2)传输 或接收。虽然在示例性实施方式中示出了设备可读介质50是单个介质， 但是词语“计算机可读介质”应被理解为存储指令的一个或多个集合的 一个介质或多个介质(例如，集中式或分布式数据和/或相关的缓存或服 务器)。词语“计算机可读介质”也应被考虑成包括能够存储、编码或携 带指令的集合的任何介质，或者包括能够被指令的集合使用或与指令的 集合相关的数据结构的任何介质，其中指令的集合用于通过设备执行并 且引起设备实施本应用的方法中的一个或多个。词语“计算机可读介质” 应相应地被理解成但不限于固态存储器、光学和磁性介质以及载波信号。 这种介质在没有限制的情况下还可包括硬盘、软盘、快擦写存储卡、数 字视频磁盘、随机存取存储器(RAM)、只读存储器(ROM)等等。本 文中所描述的示例性实施方式可在包括安装在计算机上的软件的操作环 境中、在硬件中或在硬件与软件的组合中实现。

本领域技术人员应认识到的是，网络服务可配置为提供接入连接至 网络服务的一个或多个计算装置的网络，而且该计算装置可包括一个或 多个处理器、总线、存储装置、显示装置、输入/输出装置等等。此外， 本领域技术人员能够理解的是，网络服务可联接至可以用于实现如本文 中所描述的公开的实施方式中的任一个的一个或多个数据库、资源库、 服务器等等。

在以下权利要求中的所有功能性描述的装置或步骤的对应结构、材 料、过程和等同意在包括用于与如具体要求的其它要求的元件共同执行 功能的任何结构、材料或动作。本技术的描述为了说明和描述的目的而 被提供，其并不是穷尽的，也不限于所公开的形式中的本技术。在不背 离本技术的范围和精神的情况下，诸多修改和变化将对本领域普通技术 人员显而易见。选择了示例性实施方式并且对其进行了描述，以便充分 解释本技术的原则以及其实际应用，并且使本领域普通技术人员中的其 他人员能够理解本技术，本技术用于具有如适于所预期的特定应用的各 种修改的各种实施方式。

在上文中，根据本技术的实施方式，参考流程图和/或方法、设备(系 统)和计算机程序产品的方块图对本技术的多方面进行了说明。应理解 的是，流程图图例和/或方框图中的每块或者流程图图例和/或方框图中的 方块的组合可通过计算机程序指令实现。这些计算机程序指令可设置到 通用计算机的处理器、专用计算机或其它可编程数据处理设备以产生设 备，以使得通过计算机的处理器或其它可编程数据处理设备执行的指令 产生用于实现流程图和/或方块图块或多个块中所规定的功能/动作的装 置。

这些计算机程序指令还可储存在可引导计算机、其它可编程数据处 理设备或其它装置以特定方式运行的计算机可读介质中，以使得计算机 可读介质中存储的指令产生一件产品，该产品包括实现流程图和/或方框 图块或多个块中所规定的功能/动作。

计算机程序的指令还可加载到计算机、其它可编程数据处理设备或 其它装置上，以引起一系列操作步骤在计算机、其它可编程设备或其它 装置上实施，从而产生计算机实现的处理，以使得在计算机或其它可编 程设备上执行的指令提供用于实现流程图和/或方块图块或多个块中规定 的功能/动作的处理。

附图中的流程图和方块图示出了根据本技术的各种实施方式的系 统、方法和计算机程序产品的可能实现方式的结构、功能和操作。在这 点上，流程图或方块图中的每块可表示包括用于实现规定逻辑函数(多 个逻辑函数)的一个或多个可执行指令的模块、片段或部分代码。还应 注意的是，在一些可替代的实现方式中，模块中所表明的功能可不按照 附图中所表明的顺序发生。例如，连续地示出的两个块事实上可以基本 上同时执行，或者，根据涉及的功能，这些块有时可以以相反顺序执行。 还应注意的是，方块图和/或流程图图例中的每个块以及方块图和/或流程 图图例中块的组合可通过实施指定功能或动作的专用硬件基系统实现或 者通过专用硬件和计算机指令的组合实现。

虽然上文为了说明性的目的对系统的具体实施方式以及示例进行了 描述，但是如相关领域技术人员将认识到的是，在本系统的范围内各种 等同的修改是可能的。例如，虽然处理或步骤以给定的顺序呈现，但是 可替代的实施方式可实施具有以不同顺序的步骤的例程，并且一些处理 或步骤可以删除、移动、增加、再分、组合和/或修改以提供替换或子组 合。这些处理或步骤中的每个可以以各种不同的方式实现。此外，虽然 处理或步骤有时显示为连续地执行，但是这些处理或步骤可改为同时执 行，或者可在不同的时间执行。

虽然以上描述了不同的实施方式，但是应当理解的是，这些实施方 式仅作为示例提供，并且不是作为限制提供。说明不意在将本发明的范 围限制到本文中所阐述的特定形式。相反，本说明意在涵盖如可能包括 在如由所附权利要求以及本领域普通技术人员能理解的其它方面限定的 本发明的精神和范围内的这种替换、修改和等同。因此，优选实施方式 的宽度和范围不应被以上描述的任一个所限制。