数学应用-有限状态机和地址识别

发表者：吴军，Google 研究员

地址的识别和分析是本地搜索必不可少的技术，尽管有许多识别和分析地址的方 法，最有效的是有限状态机。

一个有限状态机是一个特殊的有向图（参见有关 图论的系列 ），它包括一些状态 （节点）和连接这些状态的有向弧。下图是一个识别中国地址的有限状态机的简 单的例子。

每 一个有限状态机都有一个启始状态和一个终止状态和若干中间状态。每一条 弧上带有从一个状态进入下一个状态的条件。比如，在上图中，当前的状态是 “省”，如 果遇到一个词组和（区）县名有关，我们就进入状态“区县”；如 果遇到的下一个词组和城市有关，那么我们就进入“市”的状态，如此等等。如 果一条地址能从状 态机的起始状态经过状态机的若干中间状态，走到终止状态， 那么这条地址则有效，否则无效。比如说，“北京市双清路 83 号”对于上面的 有限状态来讲有效，而 “上海市辽宁省马家庄”则无效（因为无法从市走回到 省）。

使用有限状态机识别地址，关键要解决两个问题，即通过一些有效的地址建立状 态 机，以及给定一个有限状态机后，地址字串的匹配算法。好在这两个问题都 有现成的算法。有了关于地址的有限状态机后，我们就可又用它分析网页，找出 网页中的 地址部分，建立本地搜索的数据库。同样，我们也可以对用户输入的 查询进行分析，挑出其中描述地址的部分，当然，剩下的关键词就是用户要找的 内容。比如，对 于用户输入的“北京市双清路附近的酒家”，Google 本地会自 动识别出地址“北京市双清路”和要找的对象“酒家”。

上述基于有限状态 机的地址识别方法在实用中会有一些问题：当用户输入的地 址不太标准或者有错别字时，有限状态机会束手无策，因为它只能进行严格匹配。 （其实，有限状态机在 计算机科学中早期的成功应用是在程序语言编译器的设 计中。一个能运行的程序在语法上必须是没有错的，所以不需要模糊匹配。而自 然语言则很随意，无法用简单 的语法描述。）

为了解决这个问题，我们希望有一个能进行模糊匹配、并给出一个字串为正确地 址的可能性。为了实现这一目的，科学家们提出了基于概率的有限状态机。这种 基于概率的有限状态机和离散的马尔可夫链（详见前面关于 马尔可夫模型 的系 列）基本上等效。

声明: 除非转自他站（如有侵权，请联系处理）外，本文采用 BY-NC-SA 协议进行授权 | 智乐兔
转载请注明：转自《数学应用-有限状态机和地址识别》
本文地址：https://www.zhiletu.com/archives-2803.html
关注公众号：