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

发表者:吴军,Google 研究员

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

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

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

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

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

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

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

赞赏

wechat pay微信赞赏alipay pay支付宝赞赏

上一篇
下一篇

相关文章

在线留言

你必须 登录后 才能留言!

在线客服
在线客服 X

售前: 点击这里给我发消息
售后: 点击这里给我发消息

智乐兔官微