有限自动机实例.

1、基于有限自动机的两个实例 报 告 人 ： 张 宇 洋 时间：2014.11.5 什么是有限自动机？什么是有限自动机？ 有限状态自动机（有限状态自动机（FA -finite automaton )：是为研究是为研究有限内存的有限内存的 计算过程计算过程和和某些语言类某些语言类而抽象出的一种计算模型。而抽象出的一种计算模型。 有限状态自动机有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多拥有有限数量的状态，每个状态可以迁移到零个或多 个状态，输入字串决定执行哪个状态的迁移。个状态，输入字串决定执行哪个状态的迁移。 系统具有有限个状态，不同的状态代表不同的意义。按照实际的需要，系统可以在

2、 不同的状态下完成规定的任务。 我们可以将输入字符串中出现的字符汇集在一起构成一个字母表。系统处理的所有 字符串都是这个字母表上的字符串。 系统在任何一个状态下，从输入字符串中读入一个字符，根据当前状态和读入的这 个字符转到新的状态。 系统中含有开始状态和终止状态。 注：终止状态并不是指一进入这种状态就终止了。而是说，到此为止的字符串作为 一个语言的一个句子。 有限状态自动机是具有离散输入和输出的系统的一种数学模型有限状态自动机是具有离散输入和输出的系统的一种数学模型。 其主要特点有：其主要特点有： 有限自动机的形式定义： 一般的有限状态自动机(FA)是一个五元组：M=(Q, , , q0,

3、F) 其中， Q状态的非空有穷集合。qQ，q称为M的一个状态。 输入字母表。输入字符串都是上的字符串。 状态转移函数，有时又叫作状态转换函数或者移动函数， ：QQ，(q,a)=p。 q0M的开始状态，也可叫作初始状态或启动状态。q0Q。 FM的终止状态集合。F被Q包含。任给qF，q称为M的终止状态。 实实例一：有限自例一：有限自动动机在机在BBS监测监测系系 统统中的中的应应用用 思路：思路： 形式语言与自动机理论形式语言与自动机理论是为了将是为了将自然语言自然语言转换转换 成为成为计算机能够识别、处理的语言计算机能够识别、处理的语言而建立的理而建立的理 论体系，利用有限自动机可以对文本信息进

4、行论体系，利用有限自动机可以对文本信息进行 智能化监测，通过对智能化监测，通过对文本的词法分析文本的词法分析可以得到可以得到 系统检测所需要的信息。系统检测所需要的信息。 BBS：即：即Bulletin Board System,电子公告栏电子公告栏 系统。它是建立在系统。它是建立在互联网互联网上，面向大众，提供上，面向大众，提供 发布公告消息、聊天、信件服务等功能，满足发布公告消息、聊天、信件服务等功能，满足 用户获取信息、交流情感等要求的信息服务系用户获取信息、交流情感等要求的信息服务系 统。统。 BBS信息检测系统主要是针对当前信息检测系统主要是针对当前BBS中危害中危害 国家安全、社会

5、稳定国家安全、社会稳定而开发的能过滤而开发的能过滤BBS中的中的 机密、敏感、不良信息机密、敏感、不良信息的系统。的系统。 知识介绍： 此处，主要是想采用自动机的理论，通过此处，主要是想采用自动机的理论，通过BBS 信息监测系统，信息监测系统，创建匹配信息树创建匹配信息树，对信息进行，对信息进行 分析、处理。分析、处理。 精确命中目标信息，尽量避免误命中。精确命中目标信息，尽量避免误命中。 本实例中所用有限自动机的定义：本实例中所用有限自动机的定义： 本例中的有限状态自动机(FA)是一个四元组：FA=(Q, , q0, F) 其中， Q一个有限状态的集合。qQ，q称为M的一个状态。 状态转移函

6、数，：QQ，(q,a)=p，代表接收机在状态q时，扫 描字符a后到达状态p 。 q0FA的开始状态，也可叫作初始状态或启动状态。q0Q 。 FFA的终止状态集合。F被Q包含。任给qF，q称为M的终止状态。 下面举出具体的例子： 定义有限状态接收机A为： (a0,同)=a1 (a1,性)=a2 (a2,倾)=a3 (a3,向)=a4 (a2,恋)=a5 (a4,好)=a6 (a5,好)=a6 假如有如下的待检测字符S1=“我认为同性恋好” 和S2=“我认为同性相斥”。 S1的推导如下： (a0,我)=a0 (a0,认)=a0 (a0,为)=a0 (a0,同)=a1 (a1,性)=a2 (a2,恋

7、)=a5 (a5,好)=a6 最后处于最终状态a6，表明该字符 串检测命中。 S2的推导如下： (a0,我)=a0 (a0,认)=a0 (a0,为)=a0 (a0,同)=a1 (a1,性)=a2 (a2,相)=a0 (a0,斥)=a0 最终处于状态a0，表明该字符串检 测未命中。 实实例二：一种基于有限自例二：一种基于有限自动动机的机的渐变渐变 镜头检测镜头检测算法算法 知识介绍： 镜头：是相机的一次连续拍摄，代表时间和空间上一组连续的动作，是 一系列相互关联的连续帧的组合。 它是视像序列的基本元素，其边界检测是视像内容分析和基于内容的事 项检索的基础；同时，提高渐变检测可以提高摄影摄像设备的

8、不变性与 灵敏性。 镜头边界检测是镜头处理的第一步，也是基于内容的视频检索、视频摘 要的基础，因此研究镜头的边界检测具有重要的现实意义。 镜头的边界可分为两类：突变和渐变。 渐变包括：溶解、淡入、淡出等效果。 目前突变的检测效果比较好，而渐变的检测效果并不理想。 主要因为(1)长度的不确定性；(2)变化类型的多样性；(3)变化的平缓性。 渐变检测的算法主要分为两个方面： 判断视像中的一帧是否是渐变边界帧，称为边界帧的判定； 判定一段包含边界帧的视像是否是渐变，称为边界帧的组合。 边界帧的判定主要采用设置阀值和统计分析等方法来实现。 （在这里我们不做介绍） 这里，主要研究边界帧组合问题。 完成了

9、渐变帧的判定后，视像序列可以看作是0和1组成的序列， 其中0代表非边界帧，1代表边界帧。 面对这个二值的序列，如何准确的检测出渐变过程是边界帧组合所研究的 问题。 提出原因： 由于渐进变化过程的由于渐进变化过程的平缓性平缓性，渐变过程中经常出现，渐变过程中经常出现帧间差异很小的帧帧间差异很小的帧，它们，它们 不满足边界帧的检测条件，所以被检测成非边界帧。不满足边界帧的检测条件，所以被检测成非边界帧。 但是但是，这些非边界帧和它前后的边界帧作为一个整体，这些非边界帧和它前后的边界帧作为一个整体属于同一渐变过程属于同一渐变过程。 以往的检测算法没有考虑到这一点，要求渐变过程的帧都要符合渐变边界帧以

10、往的检测算法没有考虑到这一点，要求渐变过程的帧都要符合渐变边界帧 的条件。这样，的条件。这样，一个完整的渐变将会被截断，甚至被认为不是渐变过程一个完整的渐变将会被截断，甚至被认为不是渐变过程。 为了解决这个问题。提出了渐变检测中的为了解决这个问题。提出了渐变检测中的“容忍度容忍度”的概念，并提出了一种的概念，并提出了一种 “具有容忍度的基于自动机的边界帧组合方法具有容忍度的基于自动机的边界帧组合方法”。 渐进检测的容忍度： 渐变检测容忍度定义：一个渐变过程中允许最多连续出现N个非渐变帧， 称N为渐变检测的容忍度。 以往算法要求渐变过程中每个帧都满足鉴别条件，所以容忍度为0，算法适 应性很差。

11、具有适当的容忍度将会提高算法的适应性和健壮性。 本实例中的有限自动机模型：本实例中的有限自动机模型： 图中信号信号0表示当前帧为非边界帧非边界帧，信号信号1表示当前帧为边界帧边界帧。 Normal为正常状态为正常状态；Buffer为变声明的准备状态。为变声明的准备状态。 在检测到3次较高的帧间差较高的帧间差(1)之后，自动机到达Prepare3状态。在 此之后，自动机可以容忍连续出现2个非渐变帧非渐变帧(0)，渐变检测的容 忍度为2 。 有限自动机有多个具有复杂意义的状态，利用这种状态记忆功能， 允许渐变中连续出现2个变化平缓的帧变化平缓的帧(非渐变帧非渐变帧)，提高了检测的适适 应性和鲁棒性应