首页 > 好文分享 > 数学之美系列十 — 有限状态机和地址识别

数学之美系列十 — 有限状态机和地址识别

好文分享 , ,

    2006年7月5日 上午 09:09:00

    发表者:吴军,Google 研究员

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

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

    clip_image001

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

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

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

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

    在 八十年代以前,尽管有不少人使用基于概率的有限状态机,但都是为自己的应用设计专用的有限状态机的程序。九十年代以后,随着有限状态机在自然语言处理的广 泛应用,不少科学家致力于编写通用的有限状态机程序库。其中,最成功的是前 AT&T 实验室的三位科学家,莫瑞(Mohri), 皮瑞尔(Pereira) 和瑞利(Riley)。他们三人花了很多年时间,编写成一个通用的基于概率的有限状态机 C 语言工具库。由于 AT&T 有对学术界免费提供各种编程工具的好传统,他们三人也把自己多年的心血拿出来和同行们共享。可惜好景不长,AT&T 实验室风光不再,这三个人都离开了 AT&T,莫瑞成了纽约大学的教授,皮瑞尔当了宾西法尼亚大学计算机系系主任,而瑞利成了 Google 的研究员,AT&T 实验室的新东家不再免费提供有限状态机 C 语言工具库。虽然此前莫瑞等人公布了他们的详细算法,但是省略了实现的细节。因此在学术界,不少科学家能够重写同样功能的工具库,但是很难达到 AT&T 工具库的效率(即运算速度),这的确是一件令人遗憾的事。

    源文档 <http://www.googlechinablog.com/2006/07/blog-post.html>

本博客遵循CC协议2.5,即署名-非商业性使用-相同方式共享
写作很辛苦,转载请注明作者以及原文链接~
如果你喜欢我的文章,你可以订阅我的博客:-D点击订阅我的文章

  1. X﹏X 到现在还没有评论~
  1. 暂时没有trackbacks.