【学习】数学之美系列十:有限状态机和地址识别

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

地址的识别和分析是本地搜索必不可少的技术,尽管有许多识别和分析地址的方法,最有效的是有限状态机。 一个有限状态机是一个特殊的有向图(参见有关图论的系列),它包括一些状态(节点)和连接这些状态的有向弧。下图是一个识别中国地址的有限状态机的简单的例子。 每 一个有限状态机都有一个启始状态和一个终止状态和若干中间状态。每一条弧上带有从一个状态进入下一个状态的条件。比如,在上图中,当前的状态是“省”,如 果遇到一个词组和(区)县名有关,我们就进入状态“区县”;如果遇到的下一个词组和城市有关,那么我们就进入“市”的状态,如此等等。如果一条地址能从状 态机的起始状态经过状态机的若干中间状态,走到终止状态,那么这条地址则有效,否则无效。比如说,“北京市双清路83号”对于上面的有限状态来讲有效,而 “上海市辽宁省马家庄”则无效(因为无法从市走回到省)。 使 用有限状态机识别地址,关键要解决两个问题,即通过一些有效的地址建立状态机,以及给定一个有限状态机后,地址字串的匹配算法。好在这两个问题都有现成的 算法。有了关于地址的有限状态机后,我们就可又用它分析网页,找出网页中的地址部分,建立本地搜索的数据库。同样,我们也可以对用户输入的查询进行分析, 挑出其中描述地址的部分,当然,剩下的关键词就是用户要找的内容。比如,对于用户输入的“北京市双清路附近的酒家”,Google 本地会自动识别出地址“北京市双清路”和要找的对象“酒家”。 上 述基于有限状态机的地址识别方法在实用中会有一些问题:当用户输入的地址不太标准或者有错别字时,有限状态机会束手无策,因为它只能进行严格匹配。(其 实,有限状态机在计算机科学中早期的成功应用是在程序语言编译器的设计中。一个能运行的程序在语法上必须是没有错的,所以不需要模糊匹配。而自然语言则很 随意,无法用简单的语法描述。) 为了解决这个问题,我们希望有一个能进行模糊匹配、并给出一个字串为正确地址的可能性。为了实现这一目的,科学家们提出了基于概率的有限状态机。这种基于概率的有限状态机和离散的马尔可夫链(详见前面关于马尔可夫模型的系列)基本上等效。 在 八十年代以前,尽管有不少人使用基于概率的有限状态机,但都是为自己的应用设计专用的有限状态机的程序。九十年代以后,随着有限状态机在自然语言处理的广 泛应用,不少科学家致力于编写通用的有限状态机程序库。其中,最成功的是前 AT&T 实验室的三位科学家,莫瑞(Mohri), 皮瑞尔(Pereira) 和瑞利(Riley)。他们三人花了很多年时间,编写成一个通用的基于概率的有限状态机 C 语言工具库。由于 AT&T 有对学术界免费提供各种编程工具的好传统,他们三人也把自己多年的心血拿出来和同行们共享。可惜好景不长,AT&T 实验室风光不再,这三个人都离开了 AT&T,莫瑞成了纽约大学的教授,皮瑞尔当了宾西法尼亚大学计算机系系主任,而瑞利成了 Google 的研究员,AT&T 实验室的新东家不再免费提供有限状态机 C 语言工具库。虽然此前莫瑞等人公布了他们的详细算法,但是省略了实现的细节。因此在学术界,不少科学家能够重写同样功能的工具库,但是很难达到 AT&T 工具库的效率(即运算速度),这的确是一件令人遗憾的事。

本文分享自微信公众号 - PPV课数据科学社区(ppvke123)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2014-11-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏安智客

Frequently Asked Questions on seL4

形式化验证是近年来安全操作系统发展的热门!seL4在其官网上打出的口号就是:安全不是表现不佳的借口!

23250
来自专栏织云平台团队的专栏

腾讯社交网络图片带宽优化技术演进之路

作者介绍:游佳龙,腾讯高级工程师,目前专注于SNG组件运维工作。6年运维领域相关工作经验,具备中间、云计算、接入组件、CDN网络等建设优化能力。 前言 腾...

765100
来自专栏Android 开发者

Android P 开发者预览版首发!

26220
来自专栏Python攻城狮

Python采集微博热评进行情感分析祝你狗年脱单

如果自己需要爬(cai)虫(ji)的数据量比较大,为了防止被网站封Ip,可以分时段爬取,另外对于爬到的数据一般是用来存储数据库,这就需要对数据进行去重处理,记录...

17420
来自专栏MyBlog

软件测试方法课程笔记(1)

举某些例子, 软件测试方法有黑盒测试, 白盒测试 按阶段来区分的话有单元测试, 集成测试, 系统测试 按目的来分有性能测试等

13720
来自专栏云计算D1net

谷歌云平台加入对更多微软产品的支持

谷歌正在向Google Cloud Platform(谷歌云平台)的用户提供更多可用的微软软件。 谷歌在12月8日宣布,将允许客户在谷歌云平台上运行Window...

38770
来自专栏小狼的世界

充电:PR值的相关知识

      网站的PR值(全称为PageRank),是google搜索排名算法中的一个组成部分,级别从1到10级,10级为满分,PR值越高说明该网页在搜索排名中...

14420
来自专栏AI科技大本营的专栏

从15000个Python开源项目中精选的Top30,Github平均star为3707,赶紧收藏!

翻译 | AI科技大本营(ID:rgznai100) 参与 | SuiSui 继推出2017年机器学习开源项目Top 30榜单后,Mybridge AI又推出了...

48060
来自专栏机器之心

机器学习为核心,DeepMind助力谷歌开发的安卓 9「Pie」今日上线

今年 5 月份,谷歌 I/O 大会宣布推出安卓 9,而后经过数月的测试,谷歌收获了大量的反馈。此外,还有小米、Oppo 等 7 家设备制造商也将测试版本放到了他...

12610
来自专栏SDNLAB

OpenStack Neutron之OpenStack网络基础

OpenStack在这几年风生水起。随着核心模块稳定性的提高,OpenStack已经有了很多大规模商用的案例,所有与云相关的,无论是商用软件还是开源平台都在积极...

46590

扫码关注云+社区

领取腾讯云代金券