MENU

利用Trie树构建有穷自动机

November 10, 2018 • Read: 267 • 编译原理

Trie树简介

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

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

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

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

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

有穷自动机


上图有穷自动机中的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树,因为数组的下标只能是数字,不能是字符,所以我们人为规定一下,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图如下:

Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment