地理编码应用中的模糊搜索

摘要

本公开描述了用于地理编码应用中的模糊搜索的系统和方法的各种实施例。对要获得其地理编码信息的输入地址执行词汇分析以得到该输入地址的部分。在一个方面，所述词汇分析可以包括解析操作、抽象操作和延伸操作中的至少一个。接下来，使用所述输入地址的部分对结节序列树执行模糊搜索，以便识别匹配所述输入地址的多个部分地址。接下来，针对识别出的多个部分地址中的每一个计算匹配和换位得分，以确定所述输入地址的最佳匹配候选。最后，利用该最佳匹配候选查询地理编码数据库以得到该输入地址的地理编码信息。

说明书

技术领域

实施例一般涉及计算机系统，并且更加具体来说，涉及用于得到地址的 地理编码(geocoding)信息的方法和系统。

背景技术

地理编码一般被称作根据诸如街道名称、邮政编码等等之类的其它地理 数据确定地理坐标(通常用纬度和经度表示)的过程。

目前，通过在存储多个地址的地理编码数据库中搜索对接收到的输入地 址的匹配来执行地理编码。如果在地理编码数据库中发现输入地址的精确匹 配，则从该地理编码数据库中取出与该输入地址对应的纬度/经度对并且将其 提供给用户。

然而，目前的地理编码技术不精准并且仅当接收到的输入地址在地理编 码数据库中有精确匹配时才管用。当一个或多个下列元素包含于地理编码过 程中时会遭遇次最佳(sub-optimal)性能：(1)如果接收到的输入地址中的一 个词(word)被拼错或者不正确的话，例如，如果地址“SAINT JOHN ROAD” 被错拼为“SANT JOHN ROAD”或者错打为“SAINT JOHN STREET”；(2) 如果接收到的输入地址中的一个词可以用多于一种的方式来表示的话，例 如，词“HIGHWAY”可以表示为“HWY”，英文单词“WEST”在法语中可 以被表示为“OUEST”；以及(3)如果输入地址的词可以以不同的方式组织 但是仍然保持相同的含义的话，例如，地址“Highway 5”可以是“Highway No.5”或者“Highway#5”或者“No.5Highway”。

因此，根据各种输入数据中任何一种返回较为精准的地理编码结果的能 力是人们所期待的。

发明内容

这里描述了用于地理编码应用中的模糊搜索的系统和方法的各种实施 例。对输入地址执行词汇分析以得到输入地址的部分(portion of the input address)。利用得到的输入地址的部分对结节序列树执行模糊搜索以识别通 过结节序列树存储的多个部分地址(partial address)中的一个或多个。

针对识别出的多个部分地址计算匹配和换位(transposition)得分，以确定 识别出的多个部分地址中的最佳匹配候选。利用最佳匹配候选查询地理编码 数据库以得到与输入地址相关的地理编码信息。

当考虑结合后面的附图给出的本发明优选实施例的以下详细说明时，本 发明实施例的这些及其它好处和特征将变得明显。

附图说明

权利要求利用具体特征阐述了本发明的实施例。在附图中的图中以示例 方式而非以限制方式示出本发明，附图中同样的参考标号表示类似元素。本 发明的实施例连同其优点可以从以下结合附图的详细说明中得到更好的理 解。

图1是示出根据实施例的用于地理编码应用中的模糊搜索的方法的流程 图。

图2是示出根据实施例的包括在对输入地址执行的词汇分析中的一个或 多个操作的框图。

图3是示出根据实施例的用于创建结节序列树的方法的流程图。

图4示出根据示范性实施例的示范性参考数据。

图5A-5B示出根据实施例使用图4的参考数据生成结节序列树。

图6示出根据实施例使用图4的参考数据生成的抽象结节序列树。

图7示出根据实施例模糊搜索图5B的结节序列树或者图6的抽象结节 序列树的方法。

图8是示出根据实施例针对识别出的多个部分地址计算匹配和换位得分 的方法的流程图。

图9示出根据实施例用于针对识别出的多个部分地址确定匹配和换位得 分的换位权重表。

图10示出根据实施例确定用于计算匹配和换位得分的字符匹配计数器 和换位次数的示范性代码。

图11是示出根据实施例用于重新排列存储在地理编码数据库中的多个 地址的方法的流程图。

图12A示出根据实施例的示范性地理编码数据库。

图12B示出根据实施例存储经重新排列的多个地址的、图12A的示范 性地理编码数据库。

图13A示出根据实施例将确定其地理编码信息的示范性输入地址。

图13B-13C示出根据实施例在对图13A的输入地址执行词汇分析之后 得到的、图13A的输入地址的部分。

图13D示出根据实施例针对图13A的输入地址的、识别出的部分地址 的列表。

图13E示出根据实施例存储在地理编码数据库中的参考数据的一部分。

图14是示出根据实施例的、可以实现针对地理编码应用中的模糊搜索 所描述的技术的计算环境的框图。

具体实施方式

这里描述了用于地理编码应用中的模糊搜索的技术的各种实施例。在下 面的描述中，阐述了大量具体细节以提供对本发明的实施例的全面理解。然 而，本领域的技术人员将认识到，可以实践本发明而无需一个或多个所述具 体细节，或者利用其它方法、组件、素材等等来实践本发明。在其它实例中， 没有示出或者详细描述公知结构、素材或操作以避免模糊了本发明的方面。

贯穿本说明书，对“一个实施例”、“本实施例”及类似短语的引用指的 是结合该实施例描述的特定特征、结构或者特性包括在本发明的至少一个实 施例中。因此，贯穿本说明书这些短语在各个位置的出现并不一定全都指代 相同的实施例。此外，特定特征、结构或者特性可以在一个或多个实施例中 以任意适合的方式组合。

图1是示出根据实施例的用于地理编码应用中的模糊搜索的方法的流程 图。在一个实施例中，地理编码应用可以用于针对输入地址寻找地理编码信 息，诸如地理坐标。可以从用户接收输入地址。输入地址可以包括一个或多 个地址分量。例如，输入地址“3，SAINT JOHN STREET，10001”包括三 个地址分量，它们是：房屋号码地址分量(3)；街道名称地址分量(SAINT JOHN STREET)；和邮政编码地址分量(10001)。

根据一个实施例，最初在块102处，对输入地址执行词汇分析。词汇分 析包括对输入地址的地址分量中的一个执行以得到输入地址的部分的一个 或多个操作，所述一个或多个操作要么单独执行要么相互结合执行。

在一个实施例中，可以基于输入地址的语言定义词汇分析。例如，如果 输入地址是英语的，那么就可以将词汇分析定义为根据空格来划分输入地 址，因为英语在每个词之间都有空格。

接下来在块104处，利用在块102处得到的输入地址的部分对结节序列 树执行模糊搜索。在一个实施例中，模糊搜索——亦称近似或不精确匹 配——是这样一种搜索技术：其搜索那些近似或者基本上匹配给定文本串模 式(pattern)的文本串。可能在执行模糊搜索的同时不经意地发生了精确匹 配。模糊搜索可能有助于找到某个词的正确匹配，即使该词被拼错。例如， 对“appple”的模糊搜索也可能找到“apple”。这是因为，模糊搜索是一种 不精确或近似的匹配技术。

在一个实施例中，结节序列树(knot-sequence tree)存储在存储器中。 结节序列树存储与存储在地理编码数据库中的多个部分地址匹配的多个部 分地址。在一个实施例中，通过结节序列树存储的部分地址是存储在地理编 码数据库中的多个地址中的一个或多个地址的一部分的精确匹配。部分地址 是存储在地理编码数据库中的多个地址的地址分量。例如，如果存储在地理 编码数据库中的地址是“3，SAINT JOHN STREET，10001”，那么存储在结节 序列树中的部分地址可以是街道名称地址分量，即“SAINT JOHN STREET”。

在一个实施例中，利用得到的输入地址的部分模糊搜索结节序列树识别 由结节序列树存储的部分地址，这些部分地址可以被称作输入地址的模糊匹 配。

在一个实施例中，模糊搜索结节序列树可以包括将输入地址的部分的一 个或多个字符与存储在结节序列树的节点中的信息的一个或多个字符相比 较，以将输入地址的这些部分与存储在结节序列树的节点中的信息进行模糊 匹配。

接下来在块106处，针对在块104处识别出的部分地址计算匹配和换位 得分，以确定识别出的部分地址中的最佳匹配候选。在一个实施例中，最佳 匹配候选可以是具有最高匹配和换位得分的部分地址。最佳匹配候选可以是 识别出的多个部分地址当中对输入地址的最佳匹配。在一个实施例中，如果 对于多于一个的部分地址的匹配和换位得分是相同的，那么多于一个的部分 地址可以被识别为最佳匹配候选。

最后在块108处，利用在块106处确定的最佳匹配候选查询地理编码数 据库以得到与该输入地址相关的地理编码信息。在一个实施例中，存储在地 理编码数据库中的参考数据包括多个地址以及与该多个地址对应的地理编 码信息。查询地理编码数据库以确定该最佳匹配候选是否匹配存储在地理编 码数据库中的参考数据中多个地址中的至少一个。从地理编码数据库中取出 (retrieved)与存储在地理编码数据库中的、匹配最佳匹配候选的地址相关的地 理编码信息。

在一个实施例中，存储在地理编码数据库中的多个地址具有地址类型以 及该地址类型的标识符。例如，对于地址“SAINT JOHN STREET”，该地址 的地址类型是“STREET”并且该地址类型的标识符是“SAINT JOHN”。至 少基于该地址类型的标识符重新排列存储在地理编码数据库中的地址。

在一个实施例中，利用地址分量(即，输入地址的部分地址)的部分对 结节序列树执行模糊搜索，并且对该输入地址的地址分量中的一个确定最佳 匹配候选。在这种情况下，该输入地址的其余地址分量与该最佳匹配候选合 并以得到一个查询。然后，利用该查询查询地理编码数据库以得到与该输入 地址相关的地理编码信息。

在上面讨论的例子中，可以利用输入地址“3，SAINT JOHN STREET， 10001”的地址分量“SAINT JOHN STREET”的部分执行对结节序列树的模 糊搜索，以将“SAINT JOHN ROAD”识别为对地址分量“SAINT JOHN STREET”的最佳匹配候选。然后，将其余地址分量“3”和“10001”与最 佳匹配候选“SAINT JOHN ROAD”合并以得到查询“3，SAINT JOHN ROAD， 10001”。然后，所得到的查询“3，SAINT JOHN ROAD，10001”可以用来查 询地理编码数据库以得到输入地址“3，SAINT JOHN STREET，10001”的地 理编码信息。

在一个实施例中，最佳匹配候选或者所得到的查询可以相应于存储在地 理编码数据库中的多个地址中的多于一个的地址。在这种情况下，对存储在 地理编码数据库中的多个地址中的多于一个的地址中的每一个确定匹配和 换位(transposition)得分。然后，与存储在地理编码数据库中的地址当中的、 具有最高匹配和换位得分的地址相应的地理编码信息被确定为该输入地址 的地理编码信息。

图2是示出根据实施例的、包括在对输入地址执行的词汇分析200中的 一个或多个操作的框图。在一个实施例中，一个或多个操作包括解析操作 202、抽象(abstraction)操作204和延伸(stretch)操作206。对输入地址单独 地或者组合地执行解析操作202、抽象操作204和延伸操作206。

在一个实施例中，解析操作202将输入地址划分以得到该输入地址的部 分。解析操作202可以根据输入地址的语言将输入地址划分为多个部分。例 如，如果输入地址是英文的，那么就可以在每个空格处对输入地址进行划分 以得到该输入地址的多个部分(词)。在上面输入地址“3，SAINT JOHN STREET，10001”的例子中，对输入地址执行解析操作在每个空格处划分输 入地址，以得到五个部分，它们是：“3”、“SAINT”、“JOHN”、“STREET” 和“10001”。如果输入地址是中文的，那么输入地址中的词就不是用空格 (white space)来分隔。因此，假如输入地址是中文的，解析操作可以使用 隐马尔可夫模型(Hidden Markov Model)以得到输入地址的部分。

在解析操作将输入地址划分为部分之后，利用输入地址的部分对结节序 列树执行模糊搜索以识别与输入地址匹配的部分地址。在一个实施例中，输 入地址的部分中的每一个都与存储在结节序列树的节点中的信息相比较。在 上面“3，SAINT JOHN STREET，10001”的例子中，部分“3”、“SAINT”、 “JOHN”、“STREET”和“10001”中的每一个都与存储在结节序列树的节 点中的信息相比较。

在一个实施例中，抽象操作204得到输入地址的抽象。诸如Metaphone、 Double Metaphone和Soundex之类的语音学关键词算法(phonetic key algorithm)是抽象操作的例子。语音学关键词算法得到输入地址的每个部分 (词)的语音学表示，作为输入地址的抽象(abstraction)。然后，利用输入地 址的抽象对结节序列树执行模糊搜索以识别与输入地址匹配的部分地址。

在上面“3，SAINT JOHN STREET，10001”的例子中，如果所执行的抽 象操作是语音学关键词算法，那么得到的抽象就是“3，SNT JN STRT，10001”， 其中“SNT”、“JN”和“STRT”分别是“SAINT”、“JOHN”和“STREET” 的语音学表示。

在一个实施例中，延伸操作206根据输入地址的语言扩展输入地址的字 符。地址的扩展可以包括将输入地址中的字符变换为不同的语言。例如，中 文拼音生成是将输入地址中的每个中文字符翻译为英文中的拼音单词的延 伸操作。

通过延伸操作206扩展输入地址中的字符以得到扩展地址。然后，利用 扩展地址对结节序列树执行模糊搜索以识别部分地址。例如，如果输入地址 是中文的，那么中文拼音生成器就得到扩展的拼音地址，其包括针对输入地 址中每个中文字符的拼音单词。

在一个实施例中，相互组合地执行解析操作202、抽象操作204和延伸 操作206。例如，一开始，可以对中文的输入地址应用中文拼音生成器(延 伸操作206)以得到扩展的拼音地址，然后可以对扩展拼音地址应用解析操 作202以得到经扩展的拼音地址的部分。然后，利用得到的扩展拼音地址的 部分对结节序列树执行模糊搜索以针对该输入地址识别部分地址。

在另一例子中，一开始可以对输入地址应用解析操作202以得到输入地 址的部分，然后可以对得到的部分执行抽象操作204。在上面例子中，可以 首先通过应用解析操作202将输入地址“3，SAINT JOHN STREET，10001” 划分为五个部分“3”、“SAINT”、“JOHN”、“STREET”和“10001”。然后 可以对得到的部分应用语音学关键词算法，即抽象操作204，以得到表示得 到的部分中的每一个的语音学关键词，即“3”、“SNT”、“JN”、“STRT”和 “10001”。然后，可以利用输入地址的部分中的每一个的抽象对结节序列树 执行模糊搜索以针对该输入地址识别多个部分地址。

图3是示出根据实施例的用于创建结节序列树的方法的流程图300。在 一个实施例中，在设计时间中创建结节序列树。使用存储在地理编码数据库 中的、包括在参考数据中的多个地址创建结节序列树。在一个实施例中，使 用部分地址创建结节序列树。结节序列树将部分地址存储在存储器中。

如图所示，一开始，在块302处，在存储在地理编码数据库中的地址的 词中识别公共字符。在一个实施例中，搜索地理编码数据库以识别存储在地 理编码数据库中的部分地址的词中的公共字符。识别存储在地理编码数据库 中的地址的词中的公共字符。例如，如果地址中的一个词是“MAIN”并且 该地址中的另一个词是“MARY”，那么识别出的公共字符就是“MA”。

在一个实施例中，搜索地址的部分以识别它的词中的公共字符。例如， 可以搜索存储在地理编码数据库中的地址的街道名称地址分量以识别街道 名称地址分量中的词中的公共字符。

在一个实施例中，识别出的公共字符存储在结节序列树的父节点中。识 别出的公共字符是存储在结节序列树的父节点中的信息，其将在该结节序列 树的模糊搜索期间与输入地址的部分相比较。

接下来在块304处，在块302处识别出的公共字符被存储在结节序列树 的父节点中。在一个实施例中，公共字符存储在结节序列树的分支序列的父 节点中。在一个实施例中，结节序列树包括一个或多个父节点，它们各自存 储在块302处识别出的公共字符中的一个。在上面的例子中，识别出的 “MAIN”和“MARY”的公共字符“MA”被存储在结节序列树的父节点中。

在一个实施例中，结节序列树包括分支序列。分支序列可以包括通过指 示遍历该分支序列的方向的分支连接的一个或多个节点。在一个实施例中， 存储在分支序列的节点中的信息的组合可以识别存储在结节序列树中的一 个或多个部分地址。父节点是分支序列的根节点。在一个实施例中，父节点 是一个或多个分支序列的根节点。

接下来在块306处，与在块302处识别出的公共字符相关联的多个词当 中的词的其余部分被存储在该分支序列的子节点中。父节点和子节点可以通 过指示遍历该分支序列的方向的分支连接。在上面的例子中，词“MAIN” 和“MARY”的其余部分分别是“IN”和“RY”。其余部分“IN”和“RY” 被存储在分离的子节点中并且通过分离的分支连接到该父节点，该父节点存 储公共的一个或多个具有分支的字符“MA”。

在一个实施例中，如果公共字符仅与地址中的一个词关联，那么其余部 分被存储在父节点中。

最后在块308处，地址被存储在与该分支序列关联的一个或多个序列信 息块中。在一个实施例中，部分地址被存储在与该分支序列关联的一个或多 个序列信息块中。在一个实施例中，与该分支序列关联的序列信息块存储部 分地址，其包含存储在该分支序列的父节点中的公共字符或者存储在该分支 序列的父节点和子节点中的公共字符与其余部分的组合。例如，部分地址 “STREET MAIN，10001”被存储在与这样的分支序列关联的序列信息块中： 该分支序列的父节点存储“MA”。

在一个实施例中，序列信息块可以与多于一个的分支序列关联。例如， 存储“SAINT JOHN STREET”的序列信息块可以与第一序列信息块、第二 信息块和第三序列信息块关联，其中第一序列信息块的父节点存储 “SAINT”，第二信息块的父节点存储“JOHN”，第三序列信息块的父节点 存储“STREET”。

在一个实施例中，序列信息块引用结节序列树的一个或多个序列信息块 当中的其它序列信息块。存储在其它序列信息块中的部分地址的部分与存储 在该序列信息块中的部分地址的部分相关。例如，存储地址“West Street” 的序列信息块可以引用存储地址“Ouest Road”的另一序列信息块。存储在 地址“Ouest Road”的其它序列信息块中的部分“Ouest”与存储在序列信息 块中的地址“West Street”的部分“West”相关。

在一个实施例中，如果识别出的部分地址存储在引用其它序列信息块的 序列信息块中，那么存储其它序列信息块中的部分地址被视为识别出的部分 地址。

图4示出根据示范性施例的示范性参考数据400。正如以上的讨论，参 考数据可以存储在地理编码数据库中。如图所示，存储在地理编码数据库中 的参考数据包括多个地址402和与地址402相应的地理编码信息404。在一 个实施例中，地址402包括街道名称地址分量406、邮政编码地址分量408 和房屋号码范围地址分量410。

图5A-5B示出根据实施例使用图4的参考数据400生成结节序列树 500。使用部分地址——即图4的地址402的街道名称地址分量406——生成 结节序列树500。在一个实施例中，当对结节序列树的模糊搜索要针对街道 名称地址分量406来执行时，使用街道名称地址分量406来生成结节序列树 500。

一开始，识别多个词——即街道名称地址分量406中的“MAY”、 “STREET”、“AVENUE”、“MARY”、“SAINT”、“JOHN”、“LAKE”、 “ROAD”、“5”和“5X”——中的公共字符。如图5A中所示，识别出的公 共字符是：相应于街道地址分量中的词“MAY”和“MARY”的“HA”；相 应于街道地址分量中的“SAINT”和“STREET”的“S”；相应于街道地址 分量中的“5”和“5X”的“5”；相应于街道地址分量中的“JOHN”的“J”； 相应于街道地址分量中的“ROAD”的“R”；相应于词“LAKE”的“L”； 以及相应于街道地址分量中的“AVENUE”的“A”。

接下来如图5A中所示，识别出的公共字符“HA”、“S”、“5”、“J”、 “R”、“L”和“A”中的每一个都分别被存储在父节点502、504、506、508、 510、512和514中。在一个实施例中，父节点中识别出的公共字符是存储在 父节点中的信息。如图5B中所示，父节点502是分支序列516和518的根 节点，父节点504是分支序列520-528的根节点，父节点506是分支序列 530和532的根节点，父节点508是分支序列534的根节点，父节点510是 分支序列536的根节点，父节点512是分支序列538的根节点，以及父节点 514是分支序列540的根节点。

接下来，词“MAY”的其余部分——即，与存储在父节点502中的公共 字符“MA”关联的“Y”——被存储在分支序列516的子节点542中。父 节点502和子节点542通过指示遍历分支序列516的方向的分支544连接， 即，如果对结节序列树500执行模糊搜索的话，那么首先搜索存储在父节点 502中的信息，然后搜索存储在子节点542中的信息。

词“MARY”的其余部分——即，与存储在父节点502中的公共字符 “MA”关联的“RY”——被存储在分支序列518的子节点546中。父节点 502和子节点546通过指示遍历分支序列518的方向的分支548连接。

词“SAINT”的其余部分——即，与存储在父节点504中的公共字符“S” 关联的“AINT”——被存储在分支序列520的子节点550中。父节点504 和子节点550通过指示遍历分支序列520的方向的分支552连接。词 “STREET”的其余部分——即，与存储在父节点504中的公共字符“S”关 联的“TREET”——被存储在分支序列522-528的子节点554中。父节点 504和子节点554通过分支556连接。

词“5X”的其余部分——即，与存储在父节点506中的公共字符“5” 关联的“X”——被存储在分支序列530的子节点558中。父节点506和子 节点558通过指示遍历分支序列530的方向的分支560连接。父节点506也 通过指示遍历分支序列532的方向的分支564与子节点562连接。

而且，分别存储在父节点508、510、512和514中的公共的一个或多个 字符J、R、L和A仅相应于街道名称地址分量406中的多个词中的一个词， 即，分别相应于“JOHN”、“ROAD”、“LAKE”和“AVENUE”。因此，分 别与公共字符J、R、L和A相应的其余部分“OHN”、“OAD”、“AKE”和 “VENUE”与公共字符一起被分别存储在父节点508、510、512和514中。

在一个实施例中，结节序列树500包括存储多个部分地址的序列信息块。 序列信息块可以与一个或多个分支序列关联。在一个实施例中，存储在分支 序列的父节点和子节点中的信息标识存储在与该分支序列关联的序列信息 块中的部分地址。如图所示，分支序列信息块566存储部分地址“STREET 5X， 20001”。分支序列信息块566与分支序列528和530关联。分支序列530的 父节点和子节点，分别为506和558，存储“5X”，其标识存储在与分支序 列530关联的分支序列信息块566中的部分地址“STREET 5X，20001”。分 支序列528的父节点和子节点，分别为504和554，存储“STREET”，其也 标识存储在与分支序列528关联的分支序列信息块566中的部分地址 “STREET 5X，20001”。

类似地，分支序列信息块568存储部分地址“STREET 5，20001”并且 与分支序列526和532关联。分支序列信息块570存储部分地址“SAINT JOHN STREET”并且与分支序列524和534关联。分支序列信息块572存 储部分地址“LAKE ROAD”并且与分支序列536和538关联。分支序列信 息块574存储部分地址“AVENUE MARY”并且与分支序列518和540关联。 分支序列信息块576存储部分地址“MAY STREET 10001”并且与分支序列 516和522关联。

在一个实施例中，分支序列信息块574引用如箭头578所指的另一分支 序列信息块572。存储在另一分支序列信息块572中的部分地址“LAKE ROAD”的部分“ROAD”与存储在序列信息块574中的部分地址“AVENUE MARY”的部分“AVENUE”相关。

图6示出根据实施例使用图4的参考数据生成的抽象结节序列树 (abstraction knot-sequence tree)600。在一个实施例中，在设计时间创建抽象 结节序列树600并且将其存储在存储器中。在一个实施例中，抽象结节序列 树600的父节点存储街道名称地址分量406的词中的公共字符的抽象。抽象 结节序列树的子节点存储与存储在父节点中的公共字符关联的词的其余部 分的抽象。

正如以上关于图5A-5B所讨论的那样，针对街道名称地址分量中的多 个词识别出的公共字符是“MA”、“S”、“5”、“J”、“R”、“L”和“A”。在 一个实施例中，如果公共字符与多于一个的词关联的话，那么就得到该公共 字符的抽象。而且，如果公共字符仅与一个词关联的话，那么就得到该词的 抽象。正如以上所讨论的，与多于一个的词相关的公共字符是“MA”、“S” 和5。公共字符“MA”的抽象是“M”，公共字符“S”和“5”的抽象与输 入相同，即，分别是“S”和5。如图所示，得到的抽象“M”被存储在分支 序列616的父节点602中。得到的抽象“S”被存储在分支序列620-628的 父节点604中。得到的抽象“5”被存储在分支序列630和632的父节点606 中。

公共字符“J”、“R”、“L”和“A”仅与一个词关联，分别是“JOHN”、 “ROAD”、“LAKE”和“AVENUE”。词“JOHN”、“ROAD”、“LAKE”和 “AVENUE”的抽象分别是“JN”、“RD”、“LKE”和“AVE”。词“JOHN” 的抽象，即“JN”，存储在分支序列634的父节点608中；词“ROAD”的 抽象，即“RD”，存储在分支序列636的父节点610中；词“LAKE”的抽 象，即“LKE”，存储在分支序列638的父节点612中；以及词“AVENUE” 的抽象，即“AVE”，存储在分支序列640的父节点614中。

接下来，得到与公共字符关联的词的其余部分的抽象。与公共字符“MA” 关联的其余部分分别是“Y”和“RY”。其余部分“Y”和“RY”的抽象与 输入相同，即，分别是Y和RY。其余部分“Y”和“RY”的抽象分别存储 在分支序列616和618的子节点642和646中。

存储在父节点604中的公共字符“S”的其余部分是“AINT”和“TREET”。 其余部分“AINT”的抽象是“NT”，其存储在分支序列的子节点650中。其 余部分“TREET”的抽象是“TRT”，其存储在子节点654中。与公共字符 “5”关联的词的其余部分是“X”。其余部分“X”的抽象与输入相同，即 “X”，其存储在分支序列630的子节点658中。

分支644、648、652、656、660和664具有与图5B的分支544、548、 552、556、560和564类似的特征。分支序列信息块666-676具有与图5B 的分支序列信息块566-576类似的特征。

图7示出根据实施例模糊搜索图5B的抽象结节序列树500或者图6的 抽象结节序列树600的方法700。

一开始在块702处，执行校验以确定存储在结节序列树的父节点中的信 息的第一个字符是否匹配输入地址的部分的第一个字符。在一个实施例中， 执行校验以确定输入地址的部分中至少其中一个部分的第一个字符是否匹 配结节序列树的父节点中存储的信息。正如以上所讨论的那样，存储在地理 编码数据库中的多个地址的每个词中的公共字符是存储在父节点中的信息。 在一个实施例中，执行校验以确定存储在结节序列树的父节点中的公共字符 是否匹配输入地址的每个部分中的第一个字符。

在一个实施例中，得到输入地址的每一个部分的抽象。例如，得到输入 地址的每一个部分的语音学表示。然后，执行校验以确定输入地址的每一部 分的抽象的第一个字符是否匹配存储在抽象结节序列树的父节点中的信息。

在一个实施例中，确定输入地址的部分的抽象与存储在结节序列树的父 节点中的信息，然后执行校验以确定存储在父节点中的信息的抽象的第一个 字符是否匹配输入地址的部分的抽象的第一个字符。例如，如果输入地址是 “SAINT JOHN STREET”，那么输入地址的部分是“SAINT”、“JOHN”和 “STREET”。输入地址的部分的抽象是“SNT”、“JN”和“STRT”。这些抽 象中的每一个，即“SNT”、“JN”和“STRT”，都与存储在结节序列树的父 节点中的信息的抽象或者存储在抽象结节序列树的父节点中的信息相比较。

假如存储在父节点中的信息的第一个字符匹配输入地址的部分中至少 其中一个部分的第一个字符，即如果在块702中的条件为真的话，那么就执 行校验以确定存储在父节点和子节点中的信息的组合是否匹配输入地址的 部分(块704)。在一个实施例中，在块702处执行校验以确定存储在父节点 和子节点中的信息的组合是否匹配输入地址的一部分、该部分的第一个字符 匹配存储在父节点中的信息的第一个字符。在一个实施例中，在父节点与通 过分支连接到该父节点的每一个子节点之间得到信息的组合。在一个实施例 中，在根节点是父节点的分支序列的子节点和该父节点之间得到信息的组 合。在一个实施例中，得到存储在父节点与子节点中的信息的组合的抽象， 并且将信息的组合的抽象与输入地址的部分的抽象相比较。

最后，在块706处，如果存储在分支序列的父节点与子节点中的信息的 组合匹配输入地址的部分中的至少其中一个部分，那么存储在与该分支序列 关联的序列信息块中的部分地址就被识别出来。

在一个实施例中，从用于计算匹配和换位得分的存储器中取出识别出的 部分地址。

在一个实施例中，如果存储识别出的部分地址的其中一个的序列信息块 引用另一序列信息块，那么存储在该另一序列信息块中的部分地址也被视为 识别出的部分地址。

接下来，针对识别出的多个部分地址计算匹配和换位得分。

图8是示出根据实施例针对识别出的多个部分地址计算匹配和换位得分 的方法的流程图800。在一个实施例中，针对通过模糊搜索结节序列树识别 出的多个部分地址中的每一个计算匹配和换位得分。在一个实施例中，匹配 和换位得分从识别出的多个部分地址当中确定最佳匹配候选。

一开始在块802处，将识别出的多个部分地址当中的一个识别出的部分 地址与输入地址相比较。在一个实施例中，将识别出的部分地址中的每一个 与输入地址相比较以针对识别出的部分地址中的每一个计算匹配和换位得 分。

在一个实施例中，将识别出的部分地址与输入地址相比较包括将识别出 的部分地址中的字符与输入地址中的字符相比较。在一个实施例中，将识别 出的部分地址中的字符中的每一个与输入地址中的字符中的每一个相比较。 将识别出的部分地址中的字符与输入地址中的字符相比较以匹配在识别出 的部分地址和输入地址中公用的一个或多个字符。

在一个实施例中，将识别出的部分地址中的字符按顺序与输入地址中的 字符相比较。例如，如果输入地址是“SAINT JOHN”并且针对“SAINT JOHN” 识别出的部分地址是“SAINT MARK AVENUE”，那么一开始将“SAINT JOHN”的第一个字符“S”与“SAINT MARK AVENUE”的所有字符相比 较，接下来将“SAINT JOHN”的第二个字符“A”与“SAINT MARKAVENUE” 的所有字符相比较。类似地，将“SAINT JOHN”的字符中的每一个按顺序 与“SAINT MARK AVENUE”的所有字符相比较。在本例中匹配的一个或 多个字符是“SAINT”，其在“SAINT JOHN”和“SAINT MARK AVENUE” 两者中是公用的。

在一个实施例中，在完成将识别出的部分地址中的字符与输入地址中的 字符之间的比较之后，从识别出的部分地址和输入地址两者中去除匹配的字 符以得到识别出的部分地址的其余部分和输入地址的其余部分。然后，将识 别出的部分地址的其余部分中的字符与输入地址的其余部分中的字符相比 较，以匹配在识别出的部分地址的其余部分和输入地址的其余部分中的字 符。

接下来，在块804处，针对在块802处确定的每个匹配使字符匹配计 数器递增。在一个实施例中，字符匹配计数器等于匹配的字符的数目。字符 匹配计数器可以一开始被设置为零。在上面“SAINT JOHN”和“SAINT MARK AVENUE”的例子中，字符匹配计数器的值是5，这是因为对于匹配 的字符“S”、“A”、“I”、“N”和“T”中的每一个字符匹配计数器分别递增 5次。

在一个实施例中，确定位置彼此邻近的一个或多个匹配字符的数目是否 大于位置彼此邻近的一个或多个匹配字符的预定最小数目(M)。在一个实 施例中，只有当位置彼此邻近的一个或多个匹配字符的数目大于M时才使 字符匹配计数器递增。例如，如果输入地址是“SAINT JOHN”并且识别出 的部分地址是“SAINT POPE”，那么匹配字符的数目就是6，即，“S”、“A”、 “I”、“N”、“T”和“O”。然而，位置彼此邻近的匹配字符的数目是5，即 “S”、“A”、“I”、“N”和“T”。该数目(5)应当大于M，否则对于识别出的 部分地址“SAINT POPE”的字符匹配计数器就是0。

接下来，在块806处，执行校验以确定在识别出的部分地址和输入地址 中的匹配的一个或多个字符的位置是否不同。在一个实施例中，执行校验以 确定在识别出的部分地址和输入地址中的匹配的一个或多个字符的位置是 否是对调的(transposed)，即，交换的(interchanged)。

在一个实施例中，匹配字符包括位置彼此相邻的第一匹配字符集合和位 置彼此相邻的第二匹配字符集合。在一个实施例中，如果在识别出的部分地 址和输入地址其中之一中，第一匹配字符集合和第二匹配字符集合的位置是 交换的，那么匹配字符就是对调的。考虑输入地址“STREET MAIN”和识 别出的部分地址“MAIN STREET”的例子。“STREET MAIN”和“MAIN STREET”中匹配的一个或多个字符是“STREET”和“MAIN”。位置彼此 相邻的一个或多个匹配字符的第一集合是“STREET”，并且位置彼此相邻的 一个或多个匹配字符的第二集合是“MAIN”。在“STREET MAIN”和“MAIN STREET”中一个或多个匹配字符的第一集合——即“STREET”——与一 个或多个匹配字符的第二集合——即“MAIN”——的位置是交换的。因此， 输入地址“STREET MAIN”是识别出的多个部分地址其中之一即"MAIN STREET″的换位。

接下来，如果在块806中条件为真，那么在块808中确定换位次数(a number of transposition)。在一个实施例中，换位次数是重新排列一个或多个 匹配字符的位置以使得识别出的部分地址和输入地址中的一个或多个匹配 字符的位置相同所需要的换位。在上面“STREET MAIN”和“MAIN STREET” 的例子中，所需要的换位次数是1，因为需要1次转换来将“STREET MAIN” 中的“STREET”和“MAIN”的位置改变为“MAIN STREET”。

在一个实施例中，如果块806中的条件是假，那么换位次数就是零。在 一个实施例中，定义函数transposition_gestalt以返回针对识别出的部分地址 的字符匹配计数器和换位次数。

最后，在块810处，分别在块804和808处确定的字符匹配计数器和换 位次数被用于计算识别出的部分地址的匹配和换位得分。在一个实施例中， 针对识别出的多个部分地址中的每一个执行块802-810中描述的过程以计 算多个部分地址中的每一个的匹配和换位得分。在一个实施例中，识别出的 多个部分地址当中具有最高匹配和换位得分的部分地址被确定为最佳匹配 候选。最后，利用该最佳匹配候选查询地理编码数据库以得到与该输入地址 相关的地理编码信息。

图9示出根据实施例用于确定识别出的多个部分地址的匹配和换位得分 的换位权重表900。换位权重表900包括存储换位次数902和与换位次数相 应的权重904的两个行。换位权重表900分配与换位次数相应的权重。如图 所示，如果换位次数902是0，则分配的权重904是1，如果换位次数902 是1，则分配的权重904是0.8。如果换位次数902是2，则分配的权重904 是0.3，并且如果换位次数902是3，则分配的权重904是0.1。

在一个实施例中，使用匹配和换位得分公式计算匹配和换位得分：

其中权重[i]是从换位权重表中得到的与识别出的部分地址的换位次数 相应的权重；

ret[1][i]是针对第i次换位的字符匹配计数器的值；

串A和串B分别指代识别出的部分地址和输入地址；

长度(A)和长度(B)分别指代识别出的部分地址和输入地址中的字符数 目；以及

i是换位次数。

匹配和换位得分公式将与特定换位次数相应的权重和与特定换位次数 相应的字符匹配计数器的乘积求和。所得到的总和乘以2。最后，所得到的 乘积除以识别出的部分地址与输入地址中的字符数目的总和，以得到匹配和 换位得分。

在一个实施例中，计算存储识别出的部分地址的序列信息块所引用的其 它序列信息块中存储的部分地址的匹配和换位得分。在这种情况下，在计算 该部分地址的换位和匹配得分之前，将存储在另一序列信息块中的该部分地 址的、使该部分地址与识别出的部分地址相关的部分从该部分地址和输入地 址两者中去除。

考虑将为其确定最佳匹配候选的输入地址“ST MARY”的例子。针对 输入地址“ST MARY”从结节序列树中识别出的部分地址是“ST JOHN”和 “AVENUE MARY”。部分地址“MAY STREET”存储在另一序列信息块中， 该另一序列信息块被存储识别出的部分地址“ST JOHN”的信息块引用。部 分地址“MAY STREET”中的部分“STREET”将部分地址“MAY STREET” 与部分地址“ST JOHN”相关。因为“STREET”是“ST”的别名，所以通 过用“STREET”替换输入地址中的“ST”来计算“MAY STREET”的匹配 和换位得分。为“AVENE MARY”、“ST JOHN”和“MAY STREET”计算 的匹配和换位得分分别是0.556、0.429和0.571。

可以看出，从相关序列信息块中得到的输入序列“MAY STREET”的换 位和匹配得分是最高的。然而，“MAY STREET”的换位和匹配得分仅仅由 于地址“MAY STREET”的部分“STREET”而成为最高的，而部分“STREET” 并不是输入地址“ST MARY”的一部分。因为“MAY STREET”的匹配和 换位得分值由于词“STREET”而升高，所以在从输入地址“ST MARY”和 存储在另一序列信息块中的部分地址“MAY STREET”中去除“ST”和 “STREET”之后重新计算匹配和换位得分。针对在从地址“MAY STREET” 中去除“STREET”之后得到的“MAY”计算的匹配和换位得分是0.444。

最后，再次对部分地址“AVENUE MARY”、“ST JOHN”和“MAY STREET”的换位和匹配得分求值，并且具有最高匹配和换位得分的部分地 址“AVENUE MARY”被确定为用于查询地理编码数据库的最佳匹配候选。

图10示出根据实施例确定用于计算匹配和换位得分的字符匹配计数器 和换位计数器的示范性代码。如图10中所示，已经将代码划分为四个部分 1002、1004、1006和1008，用于说明代码的功能。一开始，在代码的部分 1002中，定义transposition_gestalt函数，其以下列各项作为输入：具有m+1 个字符的第一串A、具有n+1个字符的第二串B、变量g和p(其用来识别串 A和串B中一个或多个匹配字符是否是位置对调的)、表示位置彼此邻近的 一个或多个匹配字符的最小数目的M、表示换位次数的T以及返回嵌套列表 的变量ret，其将换位次数作为第一元素以及将针对每个换位次数的字符匹 配计数器作为它后面的元素。在一个实施例中，串A是输入地址并且第二串 B是针对输入地址的识别出的部分地址。

多个变量i、j、h、max_h、pa和pb被设置为零。变量i、j和h是迭代 子(iterator)，max_h存储h的最大值，pa和pb分别是指向串A和串B的 指针。如图所示，在代码的部分1004中，嵌套循环被用于确定串A和串B 中的一个或多个匹配字符的数目(字符匹配计数器(max_h))。最内层的循 环h具有条件“ifA[i+h]＜＞B[j+h]”，其按顺序将第一串的每个字符与第二 串的全部字符进行比较。如果不满足该条件，则中断(break)条件终止最内层 循环的运行。

考虑具有11个字符(m＝10)的第一串A“STREET MAIN”和具有11 个字符(n＝10)的第二串B“MAIN STREET”的例子。位置彼此邻近的一 个或多个匹配字符的最小数目(M)被设置为3。

第一次运行内部循环h，串A的第一个字符“S”(A[0])与串B的第一 个字符“M”(B[0])相比较。因为“S”和“M”不匹配，所以最内层的循 环h中断，接下来迭代子j的值增加到1，第二次运行内部循环h，第一个字 符“S”(A[0])与串B的第二个字符“A”(B[1])相比较。该过程继续， 直到内部循环h运行到第六次。在该情形中，j的值是5并且串A的第一个 字符“S”(A[0])与串B的第六个字符“S”(B[5])匹配。字符匹配计数 器的值(h)增加1。因为条件A[i+h]＜＞B[j+h]不满足，所以最内层循环h 不中断。接下来，再次运行最内层循环。在这种情况下，第一串A的第二个 字符“T”(A[1])与第二串B的第七个字符“T”(B[6])匹配。每次运行 最内层循环，迭代子h的值都增加1。该过程继续直到第六个字符“T”(A[5]) 与第二串B的最后一个字符“T”(B[10])匹配。在该情况中，迭代子h的 值是6，其被赋给字符匹配计数器(max_h)。因为还没有确定是否有换位， 所以当换位次数是0时，字符匹配计数器(max_h)的值是6。A的指针pa 存储串A的第一匹配字符的位置，即0，并且B的指针pb存储串B的第一 匹配字符的位置，即5。

接下来，代码的部分1006确定第一串A和第二串B中的匹配字符是否 位于不同位置，即，匹配字符是否是位置对调的。只有当字符匹配计数器 (max_h)大于匹配字符的最小数目(M)时才进行该确定。定义条件集合(if (pa＜g and pb＞＝p or pb＜p and pa＞＝g)or g in(pa，pa+max_h]or p in(pb， pb+max_h]))，其校验串A和串B中的一个或多个匹配字符是否是位置对调 的。如图所示，这些条件将串A中的第一匹配字符的位置(pa)以及串B 中的第一匹配字符的位置与transposition_gestalt函数的变量g和p相比较。 如果所定义的条件中的任何一个条件被满足，那么换位次数的值(T，ret[0]) 增加1。在上面的例子中，字符匹配计数器(max_h)的值6大于最小匹配 字符数目(M)的值3。pa、pb、g和p的值分别是0、5、0和0。在上面的 例子中，所有条件均是假：(pa(0)＜g(0)且pb(5)＞＝p(0)：假；pb(5)＜p(0)且 pa(0)＞＝g(0)：假；g(0)in(pa(0)，pa(0)+max_h(6)]：假；以及p(0)in(pb(5)， pb(5)+max_h(6)]：假)，因此ret[0]的值不增加。提供换位次数和字符匹配计 数器的值的变量ret[1][ret[0]]按照字符匹配计数器(max_h)增加。在上面 的例子中，变量ret[1][ret[0]]增加6，以得到值[0，6]，即，换位次数是0并 且当换位次数是0时字符匹配计数器是6。

最后，在代码的部分1008处，再次调用transposition_gestalt函数。在一 个实施例中，从串A和B中去除串A和串B中的一个或多个匹配字符以分 别得到A’(A’＝A[0...pa]+A[pa+max_h...m])和B’(B’＝B[0...pb]+B [pb+max_h...n])。串A中的第一匹配字符的位置增加1，即pa+1赋给g，并 且串B中的第二匹配字符的位置增加1，即pb+1赋给p。然后通过A’和B’、 pa+1、pb+1以及换位次数(transposition_gestalt(A’，B’，pa+1，pb+1，M，ret[0]) 再次调用transposition_gestalt函数。在上面的例子中，在从串A和B中分别 去除匹配字符“STREET”之后，A’的值是“＜space＞MAIN”并且B’是 “MAIN＜space＞”。pa+1和pb+1的值分别是1和6，并且换位次数是0。因 此，通过值(“MAIN”，“MAIN”1，6，3，0)调用transposition_gestalt函数。

第二次调用transposition_gestalt函数，变量i、j、h和max_h再次被设 置为0。m和n的值是4。g的值是1(pa+1)并且p的值是6(pb+1)。

接下来，再次运行代码的部分1004中的嵌套循环。当再次运行部分1004 时，因为在"MAIN"中有四个匹配字符，所以字符匹配计数器(max_h)值为 4，因为在串A’之前有空格＜space＞，所以串A′中的第一匹配字符M的位 置pa是1，并且第一匹配字符M的位置pb是0。当运行代码的部分1006 时，字符匹配计数器M(4)大于最小匹配字符数目3。因此，检查用于确 定换位的条件。在这种情况下，用于确定换位的条件——pb(0)＜p(6)且pa(1) ＞＝g(1)——为真。因此，表示换位次数的变量ret[0]增加1。

最后，变量ret[1][ret[0]]提供与换位次数和与换位次数对应的字符匹配 计数器：{1，(6，4)}，即换位次数是1，当换位次数是0时字符匹配计数器 是6，并且当换位次数是1时字符匹配计数器是4。

然后，该得到的字符匹配计数器和换位次数可以用于计算多个部分地址 中的每一个的匹配和换位得分。

正如以上的讨论，具有最高匹配和换位得分的部分地址被确定为最佳匹 配候选。在确定了最佳匹配候选之后，利用最佳匹配候选查询地理编码数据 库以得到与该输入地址相关的地理编码信息。正如以上的讨论，地理编码数 据库存储参考数据，即多个地址和与多个地址相关的地理编码信息。地理编 码数据库将多个地址中的每一个存储在地理编码数据库中的、多个存储器地 址当中单独的存储器地址中。当查询地理编码数据库时，将读取多个存储器 地址以从地理编码数据库中取出与最佳匹配候选匹配的地址。

地理编码数据库将参考数据的多个地址按字母顺序存储在地理编码数 据库的存储器地址中。然而，如果可以编组在一起的两个地址被存储在彼此 远离的两个存储器地址中的话，那么按字母顺序存储地址就可能会降低地理 编码应用的性能。在这种情况下，如果查询地理编码数据库，那么就必须读 取存储可以编组在一起的两个地址的存储器地址之间的每个存储器地址以 取出这两个相关地址。因此，存储在地理编码数据库中的地址将被重新排列， 以使得可以通过读取最小数目的存储器地址从该地理编码数据库中取出匹 配最佳匹配候选的地址。

在一个实施例中，定义了一组假定条件以便重新排列存储在地理编码数 据库中的多个地址。第一假定条件是：具有最大数目字符的地址的部分被假 定为包含有关该地址的最重要信息。第二假定条件是：如果地址的两个部分 具有相同长度，那么第一部分，即位于该地址开头的地址的部分较为重要。 第三假定条件是：可能有替换物的地址的部分——例如“STREET”有替换 物“ST”——包含较少重要信息。

图11是示出根据实施例用于重新排列存储在地理编码数据库中的多个 地址的方法的流程图。在一个实施例中，在设计时间在地理编码数据库中重 新排列多个地址。

一开始，在块1102处，得到存储在地理编码数据库中的多个地址的地 址类型的缩写。在一个实施例中，得到存储在地理编码数据库中的地址中的 每一个地址的地址类型的缩写。

在一个实施例中，存储在地理编码数据库中的多个地址中的每一个都包 括地址类型以及该地址类型的标识符。地址的地址类型提供有关该地址的类 型的信息。例如，地址的地址类型可以是“STREET”、“ROAD”和 “AVENUE”，它们提供该地址是“STREET”、“ROAD”或者“AVENUE” 的信息。

在一个实施例中，地址的地址类型的缩写提供该地址类型的缩写形式。 例如，如果地址的地址类型是“AVENUE”，那么该地址类型的缩写是“AV”。

地址类型的标识符标识地址并且将该地址与存储在地理编码数据库中 的其它地址区分开。在一个实施例中，地址类型的标识符可以是标识街道的 街道名称。例如，如果地址是“AVENUE JOHN”，那么该地址的地址类型就 是“AVENUE”并且地址类型的标识符是“JOHN”。

在一个实施例中，将得到的地址类型的缩写以及地址类型的标识符组合 在一起形成与存储在地理编码数据库中的多个地址中的每一个相应的缩写 地址。在上面“AVENUE JOHN”的例子中，地址类型“AVENUE”的缩写 “AV”与地址类型的标识符“JOHN”组合在一起，以得到与地址“AVENUE JOHN”相应的缩写地址“AV JOHN”。

接下来，在块1104处，基于缩写地址的部分中的字符数目重新排序缩 写地址的部分。在一个实施例中，缩写地址的部分被重新排序以使得在缩写 地址中具有最大数目字符的部分位于缩写地址的开头。在上面的例子中，缩 写地址“AV JOHN”的部分“JOHN”具有最大数目的字符。因此，缩写地 址“AV JOHN”被重新排序为“JOHN AV”。

在一个实施例中，对经重新排序的缩写地址执行抽象操作(abstraction  operation)以得到抽象的(abstract)重新排序的缩写地址。在上面的例子中， 抽象的重新排序的缩写地址是“JNAV”，对应于经重新排序的缩写地址 “JOHNAV”。

接下来，在块1106处，按字母顺序排列所得到的重新排序的缩写地址。 在一个实施例中，基于重新排序的缩写地址的第一个字符，按字母顺序排列 经重新排序的缩写地址。在一个实施例中，基于抽象的经重新排序的缩写地 址的第一个字符，按字母顺序排列抽象的经重新排序的缩写地址。

最后，在块1108处，以与重新排序的缩写地址的排列相应的次序重新 排列存储在地理编码数据库中的多个地址。在一个实施例中，以与经排列的、 抽象的重新排序的缩写地址相应的次序重新排列存储在地理编码数据库中 的多个地址。

图12A示出根据实施例的示范性地理编码数据库1200。正如以上的讨 论，地理编码数据库1200存储参考数据1202。参考数据1202可以包括多个 地址以及地理编码信息。在一个实施例中，地理编码数据库1200包括多个 存储器地址并且参考数据存储在地理编码数据库1200中的多个存储器地址。 如图所示，地理编码数据库1200包括三个存储器地址块1204、1206、和1208， 其中每个块具有0XF存储器地址。参考数据1202包括存储在存储器地址块 1204的存储器位置1212处的地址“AVENUE MARY”1210，存储在存储器 地址块1206的存储器位置1216处的地址“MAY STREET”1214，和在存储 器地址块1208的存储器位置1220处的地址“ST JOHN”1218。

地址“AVENUE MARY”1210的地址类型是“AVENUE”并且地址类 型的标识符是“MARY”，地址“MAY STREET”1214的地址类型是“STREET” 并且地址类型1214的标识符是“MAY”，地址“ST JOHN”的地址类型是 “ST”——其是“STREET”的首字母缩写，并且地址类型的标识符是 “JOHN”。

地址“AVENUE MARY”1210和“MAY STREET”1214可以编组在一 起，因为地址类型“AVENUE MARY”1210的标识符——即“MARY”—— 以及地址“MAY STREET”1214的标识符——即“MAY”——彼此相类似。 而且，地址“ST JOHN”1218和“MAY STREET”1214相关，因为地址“MAY STREET”1214的最长部分——即“STREET”——与其缩写——即“ST JOHN”1218中的“ST”——是相同的。当利用最佳匹配候选——其与可以 编组在一起的这些地址其中之一相匹配——查询地理编码数据库1200时， 必须读取三个存储器地址块1204、1206和1208以便从地理编码数据库1200 中取得这些地址。这将明显降低地理编码应用的性能。

因此，地理编码数据库1200被重新排列，以使得利用尽可能小的存储 器读取，从地理编码数据库1200中取得可以编组在一起的地址1210、1214 和1218。

正如以上的讨论，对于重新排列多个地址来说，一开始得到存储在地理 编码数据库1200中的多个地址1210、1214和1218的地址类型的缩写。地 址“AVENUE MARY”1210的地址类型“AVENUE”的缩写是“AV”，地址 “MAY STREET”1214的地址类型“STREET”的缩写是“ST”，地址“ST JOHN”1218的地址类型——即“ST”——是“STREET”的缩写，因此不 改变。

缩写“AV”与地址类型“MARY”的标识符组合，以得到与地址“AVENUE MARY”1210相应的缩写地址“AV MARY”，缩写“ST”与地址类型“MAY” 的标识符组合，以得到与地址“MAY STREET”1214相应的缩写地址“MAY ST”。正如以上的讨论，地址“ST JOHN”的地址类型——即“ST”——已 经是缩写形式，因此“ST JOHN”的缩写地址是“ST JOHN”1218。

接下来，基于缩写地址的部分中的字符数目重新排序缩写地址的部分。 缩写地址“AV MARY”的部分“MARY”具有最大数目的字符。因此，缩 写地址“AV MARY”被重新排序为“MARY AV”。类似地，地址“ST JOHN” 和“MAY ST”被分别重新排序为“JOHN ST”和“MAY ST”。在对缩写地 址重新排序之后，经重新排序的缩写地址是“MARY AV”、“JOHN ST”和 “MAY ST”。

在一个实施例中，得到与经重新排序的缩写地址相应的、抽象的重新排 序的缩写地址。所得到的与重新排序的缩写地址“MARY AV”相应的、抽 象的重新排序的缩写地址是“MRYAV”，与重新排序的缩写地址“JOHN ST” 相应的、抽象的重新排序的缩写地址是“JN ST”，以及与重新排序的缩写地 址“MAY ST”相应的、抽象的重新排序的缩写地址是“MYST”。

接下来，按字母顺序排列所得到的抽象的经重新排序的缩写地址。基于 首部的一个或多个字符——分别是MR、JN和MY，按字母顺序排列抽象的 经重新排序的缩写地址“MRYAV”、“JNST”和“MYST”。所得到的经排列 的、抽象的重新排序的缩写地址是“MRYAV”、“MYST”和“JNST”。

最后，以与抽象的重新排序的缩写地址“MRYAV”、“MYST”和“JNST” 的排列对应的次序，重新排列存储在地理编码数据库1200中的多个地址 1210、1214和1218。在得到经排列的抽象的重新排序的缩写地址之后，将 看到，分别与“MRYAV”和“MYST”相应的地址“AVENUE MARY”1210 和“MAY STREET”1214可以编组在一起。在一个实施例中，可以编组在 一起的地址被存储在邻近的存储器位置。

图12B示出根据实施例存储经重新排列的多个地址的、图12A的示范 性地理编码数据库1200。如图12B中所示，可以编组在一起的地址“AVENUE MARY”1210和“MAY STREET”1214被存储在存储器地址块1204的相邻 存储器地址1212和1222中。这保证当利用最佳匹配候选查询地理编码数据 库时将仅仅读取两个存储器地址。这可以提供地理编码应用的性能上的改 进。

图13A示出根据实施例将确定其地理编码信息的示范性输入地址。如图 所示，输入地址1300是“JOHN SANTE AVE”。在一个实施例中，从用户接 收输入地址1300。

图13B-13C示出根据实施例在对图13A的输入地址1300执行词汇分 析之后得到的、图13A的输入地址的部分。对输入地址“JOHN SANTE AVE” 1300执行的词汇分析是解析操作，其后是抽象操作。解析操作在空格处对输 入地址“JOHN SANTE AVE”1300进行解析以得到输入地址“JOHN SANTE AVE”1300的三个部分：“JOHN”1302、“SANTE”1304和“AVE”1306。

然后，对得到的部分“JOHN”1302、“SANTE”1304和“AVE”1306—— 它们是在解析操作之后得到的——执行抽象操作。如图13C中所示，对部分 “JOHN”1302得到的抽象是“JN”1308，对部分“SANTE”1304得到的 抽象是“SNT”1310，以及对部分“AVE”1306得到的抽象是“AV”1312。

在得到输入地址1300的部分1302、1304和1306的抽象1308、1310和 1312之后，对图5B的结节序列树执行模糊搜索以识别出存储在结节序列树 500中的多个部分地址——它们是输入地址“JOHN SANTE AVE”500的模 糊匹配。在一个实施例中，通过将抽象“JN”1308、“SNT”1310和“AV” 1312中的每一个的第一个字符与存储在结节序列树500的父节点502-514 中的信息的第一个字符相比较，来执行对结节序列树500的模糊搜索。在一 个实施例中，将抽象“JN”1308、“SNT”1310和“AV”1312的第一个字 符与存储在抽象结节序列树600的父节点602-614中的信息的第一个字符 相比较。

抽象“JN”1308的第一个字符与存储在分支序列534(图5B)的父节 点508中的信息“JOHN”的第一个字符匹配。因此，分支序列534被遍历， 以将存储在与分支序列534关联的分支序列信息块570中的部分地址 “SAINT JOHN STREET”识别为输入地址“JOHN SANTE AVE”1300的可 能匹配中的一个可能匹配。

部分“AV”1312的第一个字符，即“A”，与存储在分支序列540的父 节点514中的信息“AVENUE”的第一个字符匹配。分支序列540被遍历以 将存储在与分支序列540关联的分支序列信息块574中的部分地址 “AVENUE MARY”识别为输入地址“JOHN SANTE AVE”1300的一个可 能匹配。因为存储识别出的部分地址“AVENUE MARY”的分支序列信息块 574引用存储地址“LAKE ROAD”的分支序列信息块572。因此，地址“LAKE ROAD”也是针对输入地址“JOHN SANTE AVE”1300识别出的部分地址中 的一个。

部分“SNT”1310的第一个字符“S”匹配存储在父节点504(图5B) 中的信息。如图5B中所示，存储“S”的父节点504具有分别存储“AINT” 和“TREET”的两个子节点550和554。因此，得到对存储在父节点和子节 点中的信息的组合的抽象。存储在父节点504“S”和子节点550“AINT” 中的信息的组合——即，″SAINT"——的抽象是“SNT”。存储在父节点504 “S”和子节点550“AINT”中的信息的组合——即，″SAINT"——的抽象 是“SNT”。

得到的信息组合的抽象两者——即“SNT”和“STRT”，都与输入地址 1300的部分“SNT”1310相比较。因为存储在分支序列520的父节点504 和子节点550中的、信息组合的抽象“SNT”与输入地址1300的部分“SNT” 1310匹配，所以遍历包括父节点504和子节点550的分支序列520。因此， 存储在与分支序列520关联的分支序列信息块570中的部分地址“SAINT JOHN STREET”被识别为输入地址“JOHN SANTE AVE”1300的一个部分 地址。

图13D示出根据实施例针对图13A的输入地址1300识别出的部分地址 的匹配部分地址列表1314。如图所示，列表1314包括通过模糊搜索结节序 列树得到的识别出的部分地址“SAINT JOHN STREET”、“LAKE ROAD” 和“AVENUE MARY”。

接下来，针对识别出的部分地址“SAINT JOHN STREET”、“AVENUE MARY”和“LAKE ROAD”中的每一个计算匹配和换位得分。针对“SAINT JOHN STREET”、“AVENUE MARY”和“LAKE ROAD”计算的匹配和换 位得分分别是0.5290、0.24和0。

基于计算出的匹配和换位得分，具有最高得分的识别出的部分地址 “SAINT JOHN STREET”被识别为最佳匹配候选。

最后，利用该最佳匹配候选查询地理编码数据库以得到与图13A的输入 地址1300相关的地理编码信息。

图13E示出根据实施例存储在地理编码数据库中的参考数据1316的一 部分。如图所示，参考数据的该部分包括最佳匹配候选“SAINT JOHN STREET”和与最佳匹配候选“SAINT JOHN STREET”相关的地理编码信 息1318。与最佳匹配候选相关的地理编码信息1318是输入地址1300“JOHN SANTE AVE”的地理编码信息。从地理编码数据库取出地理编码信息1318 并且将其提供给用户。

上面示出的软件组件有形地在计算机可读存储介质上存储为指令。术语 “计算机可读存储介质”应当采取包括存储一个或多个指令集的单个介质或 者多个介质。术语“计算机可读存储介质”应当采取包括能够承受一组物理 改变以物理存储、编码或者以另外方式承载用于由计算机系统运行的指令集 的任意物理物品，所述指令集导致计算机系统执行这里描述、表示或者示出 的任何方法或者过程步骤。计算机可读存储介质的例子包括但是不局限于： 磁介质，诸如硬盘、软盘和磁带；光介质，诸如CD-ROM、DVD和全息设 备；磁光介质；以及专门配置为存储和运行诸如专用集成电路(“ASIC”)、 可编程逻辑器件(“PLD”)以及ROM和RAM设备的硬件设备。计算机可 读指令的例子包括诸如由编译器产生的机器代码，以及包含由计算机使用解 释器运行的高级代码的文件。例如，可以使用Java、C++或者其它面向对象 的编程语言和开发工具实现本发明的实施例。本发明的其它实施例可以取代 机器可读软件指令在硬线电路中实现或者结合机器可读软件指令实现。

图14是示范性计算机系统1400的框图。计算机系统1400包括处理器 1402，其运行存储在计算机可读存储介质1422上的软件指令或者代码以执 行上面所示的本发明的方法。计算机系统1400包括介质读取器1416，用于 从计算机可读存储介质1422中读取指令并且将指令存储在存储器1404中或 者随机存取存储器(RAM)1406中。存储器1404提供较大空间用于保存静 态数据，其中至少一些指令可以被存储用于今后运行。所存储的指令可以进 一步被编译以产生这些指令的其它表示并且将其动态地存储在RAM 1406 中。处理器1402从RAM 1406中读取指令并且根据指令执行动作。根据本 发明的一个实施例，计算机系统1400还包括：输出设备1410(例如，显示 器)，用于将运行结果的至少一些作为输出——包括但并不限于视觉信 息——提供给用户；以及输入设备1412，用于利用输入数据的装置提供给用 户或者其它设备和/或以另外的方式与计算机系统1400交互。输出设备1410 和输入设备1412中的每一个都可以通过一个或多个附加的外围设备相连， 以便进一步扩展计算机系统1400的能力。可以提供网络通信器1414以将计 算机系统1400连接至网络1420并且依次连接到其它设备——这些设备连接 到例如包括其它客户端、服务器、数据存储和接口的网络1420。计算机系统 1400的模块经由总线1418互连。计算机系统1400包括数据源接口1408， 用于访问数据源1424。可以经由以硬件或者软件实现的一个或多个抽象层访 问数据源1424。例如，可以通过网络1420访问数据源1424。在一些实施例 中，可以经由诸如语义层之类的抽象层访问数据源1424。

数据源是信息资源。数据源包括启用数据存储和检索的数据的源。数据 源可以包括数据库，诸如关系数据库、交易数据库、层级数据库、多维数据 库(例如OLAP)、面向对象的数据库等等。更多数据源包括制表数据(例 如，电子表格、划界文本文件)、通过标记语言标记的数据(例如，XML数 据)、交易数据、未结构化数据(例如，文本文件、抓屏)、层级数据(例如， 文件系统中的数据、XML数据)、文件、多个报告以及可通过由基础软件系 统(例如ERP系统)等等产生的已建立协议访问的任意其他的数据源，协 议诸如开放数据库连接(ODBC)。数据源还可以包括这样的数据源：其中数 据没有被有形地存储或者以另外方式地短暂存储，诸如数据流、广播数据， 等等。这些数据源可以包括关联的数据基础、语义层、管理系统、安全性系 统等等。

在上面的描述中，阐述了大量具体细节以提供对本发明的实施例的全面 理解。然而，本领域的技术人员将看到，可以在没有一个或多个所述具体细 节的条件下实践本发明，或者利用其它方法、组件、素材等等来实践。在其 它实例中，没有示出或者详细描述公知操作或结构以避免模糊了本发明的方 面。

尽管这里示出且描述的过程包括一系列步骤，但是将理解，本发明的不 同实施例不局限于这些示出的步骤次序，因为一些步骤可能以不同次序发 生，一些与不同于这里所示和描述的其它步骤同时发生。此外，不是所示出 的所有步骤都需要来实现依照本发明的方法。而且，将理解，所述过程可以 结合这里示出和描述的装置和系统以及结合未示出的其它系统来实现。

本发明的实施例的上述描述和图示——包括抽象中所描述的——并不 意为穷举性或限制本发明为所公开的准确形式。尽管这里出于说明性目的描 述了本发明的具体实施例和例子，但是如本领域技术人员将看到，在本发明 的范围内各种等效修改是可能的。根据上面的具体说明可以进行这些修改。 而是，本发明的范围将由后面的权利要求确定，将依照所建立的权利要求结 构的声明来解释权利要求。