利用Trie树构建有穷自动机

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

内容简介: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树构建有穷自动机

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

查看所有标签

猜你喜欢:

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

比特币

比特币

李钧、长铗 / 中信出版社 / 2014-1-1 / 39.00元

2009年,比特币诞生。比特币是一种通过密码编码,在复杂算法的大量计算下产生的电子货币。虽然是虚拟货币,比特币却引起了前所未有的全球关注热潮。 这一串凝结着加密算法与运算能力的数字不仅可以安全流通、换取实物,1比特币价值甚至曾高达8 000元人民币。有研究者认为比特币具备打破几千年来全球货币由国家垄断发行的可能性。在不经意间,比特币引起的金融新浪潮已悄然成型。 虚拟货币并不是新鲜事物,......一起来看看 《比特币》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

SHA 加密
SHA 加密

SHA 加密工具