利用Trie树构建有穷自动机

栏目: 数据库 · 发布时间: 6年前

内容简介:Trie树,又称为前缀树或字符串树,我这里只是简单讲述一下Trie树,如果需要深入了解可以在我的博客搜索“Trie树”从一个节点连出去的边都必须标识不同的字符。所以一个节点最多有|字符集|这么多子节点。其中有一些节点是终结点,我们用黑色表示。对于每一个终结点,如果我们把从根到它的路径上的字符按顺序连起来,就对应着一个集合中的字符串比如上图中3号节点对应的路径0123上的字符串是inn,8号节点对应的路径0568上的字符串是ten。终结点与集合中的字符串是一一对应的

Trie树简介

Trie树,又称为前缀树或字符串树,我这里只是简单讲述一下Trie树,如果需要深入了解可以在我的博客搜索“Trie树”

首先看一下Trie树长什么样子

利用Trie树构建有穷自动机

上面这棵 Trie 树包含的字符串集合是 {in, inn, int, tea, ten, to}每个节点的编号是我们为了描述方便加上去的。树中的每一条边上都标识有一个字符。这些字符可以是任意一个字符集中的字符。比如对于都是小写字母的字符串,字符集就是‘a’-‘z’;对于都是数字的字符串,字符集就是‘0’-‘9’;对于二进制字符串,字符集就是 0 和 1

从一个节点连出去的边都必须标识不同的字符。所以一个节点最多有|字符集|这么多子节点。其中有一些节点是终结点,我们用黑色表示。对于每一个终结点,如果我们把从根到它的路径上的字符按顺序连起来,就对应着一个集合中的字符串

比如上图中3号节点对应的路径0123上的字符串是inn,8号节点对应的路径0568上的字符串是ten。终结点与集合中的字符串是一一对应的

有穷自动机

利用Trie树构建有穷自动机 上图有穷自动机中的 d 代表 0~9 的任一数字, E 代表科学计数法中的 e. 表示小数点,那么 7.3.3785e984e+31e-33 等都是该有穷自动机对应的文法,而 5.6e78e+ 等就不是该有穷自动机对应的文法

利用Trie树构建有穷自动机

就以上面的有穷自动机为例,构建Trie树我采用邻接矩阵的方法,具体来说就是用一个二维数组Trie[node][Charset]。解释一下这个二维数组,假设Trie[0]['d']=1,表达的意思就是0号结点能够通过字符'd'到达结点1;Trie[2]['d']=2的意思就是2号结点能通过字符'd'到达2号结点。根据这个规则,我们首先做出一个二维表

利用Trie树构建有穷自动机

这个表的含义是通过起始结点经过什么字符能到达其他结点,如果为空说明从这个起始结点并不能到达该结点,那么根据这个表,我们就能构建出Trie树,因为数组的下标只能是数字,不能是字符,所以我们人为规定一下, d 代表0, . 代表1, e 代表2, + 代表3,举个例子,Trie[0][0]=1表示0号结点能通过数字到达1号结点;Trie[4][3]=5表示4号结点能通过 + 到达5号结点。我们首先把Trie树构建出来

trie[0][0] = 1;
trie[0][1] = 3;
        
trie[1][0] = 1;
trie[1][1] = 2;
trie[1][2] = 4;
        
trie[2][0] = 2;
trie[2][2] = 4;
        
trie[3][0] = 2;
        
trie[4][3] = 5;
trie[4][0] = 6;
        
trie[5][0] = 6;
        
trie[6][0] = 6;

构建的Trie树如下图所示:

利用Trie树构建有穷自动机

Trie树构建好了,我们应该知道怎么在Trie树中查找某个字符串是否存在,假设有这么一个字符串 3.14e3 ,那么这棵树的结点转换过程就是 0->3->2->2->4->6

算法流程如下:

  1. 定义整型变量i,初始化为0,i的含义是指示当前取出的是字符串中的第i个字符
  2. 定义整型变量cur,初始化为0,表示当前处于几号结点
  3. 判断 Trie[cur][i] 的值是否存在,如果存在,则令 cur = Trie[cur][i] ,如果不存在,这直接退出程序
  4. 重复执行3操作直到 i 等于字符串的长度
  5. 判断cur是否为终结状态,如果是,则打印成功;否则打印失败

代码

import java.util.*;

public class Main {
    static Set<Integer> end = new HashSet<Integer>();
    static Map<String, Integer> kv = new HashMap<String, Integer>();
    static int[][] trie = new int[7][4];

    // d = 0
    // . = 1
    // e = 2
    // +|- = 3

    static void init() {// 初始化Trie树
        trie[0][0] = 1;
        trie[0][1] = 3;

        trie[1][0] = 1;
        trie[1][1] = 2;
        trie[1][2] = 4;

        trie[2][0] = 2;
        trie[2][2] = 4;

        trie[3][0] = 2;

        trie[4][3] = 5;
        trie[4][0] = 6;

        trie[5][0] = 6;

        trie[6][0] = 6;

        end.add(1);
        end.add(2);
        end.add(6);

        for (int i = 0; i <= 9; i++)
            kv.put(String.valueOf(i), 0);
        kv.put(".", 1);
        kv.put("e", 2);
        kv.put("+", 3);
        kv.put("-", 3);
    }

    static boolean check(String str) {
        int len = str.length();
        int cur = 0;

        if (!Character.isDigit(str.charAt(len - 1)) && !".".equals("" + str.charAt(len - 1)))
            return false;

        for (int i = 0; i < len; i++) {
            String tmp = "" + str.charAt(i);
            int c = kv.get(tmp);
            if (trie[cur][c] == 0) // 等于0就表示不存在
                return false; // 不存在就返回错误
            cur = trie[cur][c]; // 存在就更新cur结点
        }
        return end.contains(cur); // 判断最后是否到达终结状态
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String str = cin.next();
        init();
        if (check(str))
            System.out.println("Right");
        else
            System.out.println("Error");

        cin.close();
    }
}

运行的GIF图如下:

利用Trie树构建有穷自动机

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

高性能网站建设指南(第二版)

高性能网站建设指南(第二版)

Steve Souders / 刘彦博 / 电子工业出版社 / 2015-5 / 55.00元

《高性能网站建设指南:前端工程师技能精髓》结合Web 2.0以来Web开发领域的最新形势和特点,介绍了网站性能问题的现状、产生的原因,以及改善或解决性能问题的原则、技术技巧和最佳实践。重点关注网页的行为特征,阐释优化Ajax、CSS、JavaScript、Flash和图片处理等要素的技术,全面涵盖浏览器端性能问题的方方面面。在《高性能网站建设指南:前端工程师技能精髓》中,作者给出了14条具体的优化......一起来看看 《高性能网站建设指南(第二版)》 这本书的介绍吧!

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具