`
晨星★~雨泪
  • 浏览: 448188 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

有限状态机和地址识别

阅读更多

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



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

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



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

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

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

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

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

固定链接  |

分享到:
评论

相关推荐

    VHDL——有限状态机

    ### VHDL中的有限状态机设计概述 #### 一、有限状态机(FSM)的重要性与优点 有限状态机(Finite State Machine, FSM)是一种被广泛应用于数字逻辑设计中的模型,尤其在VHDL语言中有着非常重要的地位。在设计复杂的...

    用有限状态机进行软件设计

    有限状态机主要有两种类型:确定性有限状态机(Deterministic Finite Automaton, DFA)和非确定性有限状态机(Non-deterministic Finite Automaton, NFA)。DFA每次只能根据当前状态和输入产生唯一的新状态,而NFA则...

    如何使用有限状态机及其应用

    - **编译器设计**:编译器的词法分析和语法分析部分常常利用有限状态机来识别和解析源代码中的关键字、运算符等。 - **网络协议**:TCP/IP协议栈中的许多协议如HTTP、FTP等,其状态管理都是基于有限状态机的,确保...

    基于有限状态机的STM32系统按键识别方法.pdf

    为了提高按键识别的准确性和效率,引入了有限状态机(Finite State Machine,FSM)的概念。有限状态机是一种数学模型,它由有限个状态、条件、动作和次态组成。在按键识别的过程中,每个状态对应按键操作过程中的...

    有限状态机与Verilog设计.pdf

    在数字电路设计中,有限状态机(FSM)是一种十分重要的概念,它用于实现数字电路设计的控制部分。FSM的出现,解决了纯硬件数字系统顺序控制方式不灵活的问题,并且以其结构模式简单、易于构成同步时序逻辑模块、硬件...

    基于有限状态机的Morse码识别算法设计与实现_吴鑫辉.pdf

    以上知识点综合了文档中提到的内容,详细介绍了基于有限状态机的莫尔斯码自动识别算法的设计原理、实现方法和应用场景。通过这一算法的介绍,我们了解到为提高莫尔斯码译码的准确性,在编程实现和信号处理方面所采取...

    计算理论导引讲义 有限状态机模型

    正则语言是由有限状态机识别的语言,这意味着每一个正则表达式都可以转化为等价的有限状态机,反之亦然。这一转化过程是通过构造如诺尔曼构造(Nerode's construction)或狄克斯特拉构造(Myhill-Nerode ...

    状态机按键 多个独立按键识别 单击 双击 长按 2019.12.30.zip

    状态机,全称为有限状态机(Finite State Machine,FSM),是一种模型化复杂逻辑行为的有效工具。在按键识别中,状态机通过切换不同的状态来响应按键的不同事件,如按下、释放以及连续按下等。状态机的每个状态代表...

    利用有限状态机设计的数字密码锁

    在有限状态机的框架下,系统的行为被严格定义在有限的状态和转移逻辑之中,这不仅简化了设计流程,还避免了传统设计中可能出现的信号干扰和毛刺现象。此外,本系统的设计程序简洁,资源利用高效,易于硬件实现,为...

    有限状态机驱动的整形,浮点型数值识别器1

    在本节中,我们将探讨如何使用有限状态机(FSM)来识别整型和浮点型数值。有限状态机是一种模型,它根据当前状态和输入来决定下一个状态,非常适合用于解析数字格式。在这个实例中,我们将看到如何通过编程实现这个...

    基于分层有限状态机的时间序列数据挖掘与预测方法.pdf

    有限状态机按照表达能力可以分为确定性有限状态机(DFA)和非确定性有限状态机(NFA),以及它们的扩展形式,如有限状态转录机(PDA)等。 2. 分层有限状态机:分层有限状态机是有限状态机的一种扩展,它通过引入多...

    基于有限状态机的Web漏洞扫描器识别研究.pdf

    基于有限状态机的Web漏洞扫描器,可以有效地识别和分析这些应用中可能存在的安全问题,从而为构建安全可靠的移动互联网环境提供重要的技术支撑。 总结来说,网络安全研究中针对Web漏洞的自动识别是一个复杂而重要的...

    单片机编程中有限状态机的应用.pdf

    有限状态机的基本原理是通过有限个状态和在这些状态间转移的规则来处理逻辑和控制程序流程。在单片机这种硬件系统中,由于其存储资源有限,使用有限状态机可以让程序设计更加简洁和高效,从而提升单片机的处理时效性...

    状态机设计fpga

    明德扬科技教育有限公司提出了一种新的四段式状态机的设计方法,它将状态机的设计分为四个部分: 1. 同步时序的always模块,负责描述状态从次态迁移到现态的过程。 2. 组合逻辑的always模块,用以描述各个状态之间的...

    单片机多按键状态机的实现

    单片机多按键状态机的实现是嵌入式系统中常用的一种处理多个按键输入的方法,尤其在资源有限的环境中,如消费电子产品、智能家居设备等。本文将深入探讨如何设计和实现一个这样的系统。 首先,我们需要了解单片机。...

    基于有限状态机的STM32系统按键识别方法.zip

    本资料"基于有限状态机的STM32系统按键识别方法"探讨了如何通过有限状态机(FSM)来高效、可靠地实现STM32对按键事件的处理。 有限状态机是一种模型,用于描述一个系统在不同时间可能处于的不同状态以及如何在这些...

Global site tag (gtag.js) - Google Analytics