数据结构-前缀树/后缀树

发表于 2020-07-26 分类于数据结构与算法

本文字数： 3.1k 阅读时长 ≈ 3 分钟

概述

前缀树 是一种专门用于处理字符串匹配问题的树形结构，它利用字符串公共前缀以减少查询所需时间。其典型应用为搜索引擎的搜索提示。

其结构图大致如下：

当面对字符串查询问题时，前缀树和哈希表通常会被同时提及，故而在此说明二者在此问题上的异同点：

前者基于 “空间换时间” 加速查询；后者基于字符串公共前缀加速查询。
前者查询过程中存在冲突问题，如果散列函数选择得当，其查询操作的平均时间复杂度为 $O(1)$；后者按序匹配字符串中字符可实现查找，故而其查询操作的时间复杂度为 $O(k),k = str.length$。

前缀树中节点需要维护一个映射所有字符的引用数组，故而其耗费空间往往大于哈希表。

如果需要使用前缀树，现实情况应最好满足以下两点：字符集相对较小、字符串前缀重合较多。

前缀树又称为 Trie 树、字典树。

结构

class TrieTree {
    // 节点结构
    private static class Node {
        // 词尾次数(end=0,表示当前节点并非任何字符串尾部;end=?,表示当前节点为?个字符串尾部)
        int end;
        // 26个元素的数组，表征26个字母
        Node[] childrens;

        public Node() {
            this.end = 0;
            this.childrens = new Node[26];
        }
    }

    // 根节点
    private Node root;
}

实现

辅助方法

当前节点的孩子节点是否均为空

private boolean isNullChildren(Node root) {
    for (Node node : root.childrens) {
        if (null != node) {
            return false;
        }
    }
    return true;
}

当前子树中插入子串，并返回插入后的子树

private Node insertTree(Node root, String str, int index) {
    // 如果当前子树为空，则先构建该子树。
    if (null == root) {
        root = new Node();
    }

    // 如果已到达字符串尾部，需更新当前节点end字段，否则找到相应字符，递归下去。
    if (index == str.length()) {
        root.end++;
    } else {
        int charIndex = str.charAt(index) - 'a';
        root.childrens[charIndex] = insertTree(root.childrens[charIndex], str, index + 1);
    }

    return root;
}

当前子树中删除指定字符串，并返回删除后的子树

private Node deleteTree(Node root, String str, int index) {
    // 当前子树为空，直接返回。
    if (null == root) {
        return null;
    }

    // 已到达字符串尾部，择情处理，否则找到相应字符，递归下去。
    if (index == str.length()) {
        // 表明存在该字符串，则次数减一。
        if (root.end > 0) {
            root.end--;
        }
    } else {
        int charIndex = str.charAt(index) - 'a';
        root.childrens[charIndex] = deleteTree(root.childrens[charIndex], str, index + 1);
    }

    // 判断当前节点是否需要删去。
    if (root.end == 0 && isNullChildren(root)) {
        return null;
    } else {
        return root;
    }
}

当前子树中查询子串

private boolean searchTree(Node root, String str, int index) {
    // 当前子树为空，直接返回false即可。
    if (null == root) {
        return false;
    }

    // 已到达字符串尾部，如果存在该字符串，则返回true，否则找到相应字符，递归下去。
    if (index == str.length()) {
        return (root.end > 0);
    } else {
        int charIndex = str.charAt(index) - 'a';
        return searchTree(root.childrens[charIndex], str, index + 1);
    }
}

初始化

1
2
3

public TrieTree() {
    // 无需任何操作。
}

查询

查询字符串

1
2
3

public boolean search(String str) {
    return searchTree(this.root, str, 0);
}

操纵

前缀树中添加字符串

public void insert(String str) {
    // 节点仅存储a-z的引用，故而需有此操作。
    str = str.toLowerCase();
    this.root = insertTree(this.root, str, 0);
}

前缀树中删除字符串

public void delete(String str) {
    // 节点仅存储a-z的引用，故而需有此操作。
    str = str.toLowerCase();
    this.root = deleteTree(this.root, str, 0);
}

扩展

优化前缀树

如上所述，前缀树中节点需要维护一个映射所有字符的引用数组，这使得其将耗费巨大空间。

我们以小写英文单词构建前缀树举例：树中节点需要维护一个引用数组，该数组映射字符集 $[a-z]$。如果向该前缀树中插入许多小写英文单词，我们将看到如下现象 (可参见图一)：

引用数组的使用率很低。一个节点含有 $26$ 个引用，通常最多仅 $10$ 余个引用处于使用之中，其余引用均为 null。
部分节点往往仅有一个子节点，即该节点仅 $1$ 个引用处于使用之中。

优化前缀树即在于如何管理引用数组。常见优化策略有如下两种：

使用平衡二叉树代替引用数组，此时如果需要映射相关字符，就向平衡二叉树中动态插入一个引用节点。
如果节点仅含有一个子节点，则压缩两个节点为一个节点，此时节点内容为 “原节点内容 + 原子节点内容”。这种前缀树又被称为 压缩前缀树。

后缀树

前缀树用于处理字符串查询匹配问题，后缀树则用于处理特定字符串的模式匹配问题，即模式是否出现于特定字符串之中？、模式在特定字符串中出现了几次，具体出现在哪些位置？

首先讲明一个结论：如果模式出现于特定字符串中，那么它一定是某个后缀的前缀。

基于此结论及前缀树的用法，我们可将特定字符串的所有后缀输入至空的前缀树之中，并使用此树解决特定字符串的模式匹配问题，而该树即是后缀树。

后缀树又称为 后缀压缩前缀树，故而其实际上是将特定字符串的所有后缀输入至压缩前缀树之中。