Trie树简介及应用

京东云开发者
• 阅读 155

作者:京东物流 马瑞

1 什么是Trie树

1.1 Trie树的概念

Trie树,即字典树,又称单词查找树或键树,是一种树形结构,典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

Trie树简介及应用

Trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is a kind of search tree—an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. It is one of those data-structures that can be easily implemented.

1.2 Trie树优点

最大限度地减少无谓的字符串比较,查询效率比较高。核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

  1. 插入、查找的时间复杂度均为O(N),其中N为字符串长度。
  2. 空间复杂度是26^n级别的,非常庞大(可采用双数组实现改善)。

1.3 Trie树的三个基本性质

  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符
  2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串
  3. 每个节点的所有子节点包含的字符都不相同

2 Trie树数据结构

以字符串”hi”和”经海路”的数据为例:

Trie树简介及应用

Java的数据结构定义:

@Data
public class TrieTreeNode {
    private Character data;
    private Map<Character, TrieTreeNode> children;
    private boolean isEnd;
    //  前缀,冗余信息,可选
    private String prefix;
    //  后缀,冗余信息,可选
    private String suffix;
}

如果只是处理26个英文字符,data可以通过children数组是否为空来判断。如果处理程序,默认children为空来判断是否为最后一个节点,则isEnd字段可以省略。
前缀prefix和suffix可以在数据处理的时候,方便拿到当前节点前缀和后缀信息,如果不需要可以去除。

3 Trie树在脏话过滤中的应用

3.1 脏话关键词Keyword定义

public class KeyWord implements Serializable {
    /**
     * 关键词内容
     */
    private String word;
//其他省略
}

3.2 关键词查询器

public class KWSeeker {

    /**
     * 所有的关键词
     */
    private Set<KeyWord> sensitiveWords;

    /**
     * 关键词树
     */
    private Map<String, Map> wordsTree = new ConcurrentHashMap<String, Map>();

    /**
     * 最短的关键词长度。用于对短于这个长度的文本不处理的判断,以节省一定的效率
     */
    private int wordLeastLen = 0;

//其他处理方法,省略
}

3.3 字符串构造一棵树

/**
    * 将指定的词构造到一棵树中。
    * 
    * @param tree 构造出来的树
    * @param word 指定的词
    * @param KeyWord 对应的词
    * @return
    */
public static Map<String, Map> makeTreeByWord(Map<String, Map> tree, String word,
        KeyWord KeyWord) {
    if (StringUtils.isEmpty(word)) {
        tree.putAll(EndTagUtil.buind(KeyWord));
        return tree;
    }
    String next = word.substring(0, 1);
    Map<String, Map> nextTree = tree.get(next);
    if (nextTree == null) {
        nextTree = new HashMap<String, Map>();
    }
    // 递归构造树结构
    tree.put(next, makeTreeByWord(nextTree, word.substring(1), KeyWord));
    return tree;
}

对关键词字符串,逐个字符进行构建。

3.4 词库树的生成

/**
    * 构造、生成词库树。并返回所有敏感词中最短的词的长度。
    * 
    * @param sensitiveWords 词库
    * @param wordsTree 聚合词库的树
    * @return 返回所有敏感词中最短的词的长度。
    */
public int generalTree(Set<KeyWord> sensitiveWords, Map<String, Map> wordsTree) {
    if (sensitiveWords == null || sensitiveWords.isEmpty() || wordsTree == null) {
        return 0;
    }

    wordsTreeTmp.clear();
    int len = 0;
    for (KeyWord kw : sensitiveWords) {
        if (len == 0) {
            len = kw.getWordLength();
        } else if (kw.getWordLength() < len) {
            len = kw.getWordLength();
        }
        AnalysisUtil
                .makeTreeByWord(wordsTreeTmp, StringUtils.trimToEmpty(kw.getWord()), kw);
    }
    wordsTree.clear();
    wordsTree.putAll(wordsTreeTmp);
    return len;
}

3.5 关键词提取

/**
 * 将文本中的关键词提取出来。
 */
public List<SensitiveWordResult> process(Map<String, Map> wordsTree, String text,
        AbstractFragment fragment, int minLen) {
    // 词的前面一个字
    String pre = null;
    // 词匹配的开始位置
    int startPosition = 0;
    // 返回结果
    List<SensitiveWordResult> rs = new ArrayList<SensitiveWordResult>();

    while (true) {
        try {
            if (wordsTree == null || wordsTree.isEmpty() || StringUtils.isEmpty(text)) {
                return rs;
            }
            if (text.length() < minLen) {
                return rs;
            }
            String chr = text.substring(0, 1);
            text = text.substring(1);
            Map<String, Map> nextWord = wordsTree.get(chr);
            // 没有对应的下一个字,表示这不是关键词的开头,进行下一个循环
            if (nextWord == null) {
                pre = chr;
                continue;
            }

            List<KeyWord> keywords = Lists.newArrayList();
            KeyWord kw = AnalysisUtil.getSensitiveWord(chr, pre, nextWord, text, keywords);
            if (keywords == null || keywords.size() == 0) {
                // 没有匹配到完整关键字,下一个循环
                pre = chr;
                continue;
            }
            for (KeyWord tmp : keywords) {
                // 同一个word多次出现记录在一起
                SensitiveWordResult result = new SensitiveWordResult(startPosition, tmp.getWord());
                int index = rs.indexOf(result);
                if (index > -1) {
                    rs.get(index).addPosition(startPosition, tmp.getWord());
                } else {
                    rs.add(result);
                }
            }

            // 从text中去除当前已经匹配的内容,进行下一个循环匹配
            // 这行注释了,避免"中国人",导致"国人"。搜索不出来,逐个字符遍历
            // text = text.substring(kw.getWordLength() - 1);
            pre = kw.getWord().substring(kw.getWordLength() - 1, kw.getWordLength());
            continue;
        } finally {
            if (pre != null) {
                startPosition = startPosition + pre.length();
            }
        }

    }
}

/**
 * 查询文本开头的词是否在词库树中,如果在,则返回对应的词,如果不在,则返回null。return 返回找到的最长关键词
 * 
 * @param append 追加的词
 * @param pre 词的前一个字,如果为空,则表示前面没有内容
 * @param nextWordsTree 下一层树
 * @param text 剩余的文本内容
 * @param keywords 返回的keywords,可能多个
 * @return 返回找到的最长关键词
 */
public static KeyWord getSensitiveWord(String append, String pre,
                Map<String, Map> nextWordsTree, String text, List<KeyWord> keywords) {
    if (nextWordsTree == null || nextWordsTree.isEmpty()) {
        return null;
    }

    Map<String, Object> endTag = nextWordsTree.get(EndTagUtil.TREE_END_TAG);
    // 原始文本已到末尾
    if (StringUtils.isEmpty(text)) {
        // 如果有结束符,则表示匹配成功,没有,则返回null
        if (endTag != null) {
            keywords.add(checkPattern(getKeyWord(append, endTag), pre, null));
            return checkPattern(getKeyWord(append, endTag), pre, null);
        } else {
            return null;
        }
    }

    String next = text.substring(0, 1);
    String suffix = text.substring(0, 1);
    Map<String, Map> nextTree = nextWordsTree.get(next);

    // 没有遇到endTag,继续匹配
    if (endTag == null) {
        if (nextTree != null && nextTree.size() > 0) {
            // 没有结束标志,则表示关键词没有结束,继续往下走。
            return getSensitiveWord(append + next, pre, nextTree, text.substring(1), keywords);
        }

        // 如果没有下一个匹配的字,表示匹配结束!
        return null;
    } else { // endTag , 添加关键字
        KeyWord tmp = getKeyWord(append, endTag);
        keywords.add(checkPattern(tmp, pre, suffix));
    }

    // 有下一个匹配的词则继续匹配,一直取到最大的匹配关键字
    KeyWord tmp = null;
    if (nextTree != null && nextTree.size() > 0) {
        // 如果大于0,则表示还有更长的词,继续往下找
        tmp = getSensitiveWord(append + next, pre, nextTree, text.substring(1), keywords);
        if (tmp == null) {
            // 没有更长的词,则就返回这个词。在返回之前,先判断它是模糊的,还是精确的
            tmp = getKeyWord(append, endTag);
        }
        return checkPattern(tmp, pre, suffix);
    }

    // 没有往下的词了,返回该关键词。
    return checkPattern(getKeyWord(append, endTag), pre, suffix);

}

思路是对某个字符串text,逐个字符ch,获取ch对应的词库树的children,然后获取匹配到的单个或多个结果,将匹配到的关键词在text中的开始和结束下标进行记录,如后续需要html标记,或者字符替换可直接使用。如果未能在词库树中找到对应的ch的children,或者词库树的children未能匹配到去除ch的子字符串,则继续循环。具体可再详细读一下代码。

4 Radix Tree的应用

4.1 RAX - Redis Tree

Redis实现了不定长压缩前缀的radix tree,用在集群模式下存储slot对应的的所有key信息。

/* Representation of a radix tree as implemented in this file, that contains
 * the strings "foo", "foobar" and "footer" after the insertion of each
 * word. When the node represents a key inside the radix tree, we write it
 * between [], otherwise it is written between ().
 *
 * This is the vanilla representation:
 *
 *              (f) ""
 *                \
 *                (o) "f"
 *                  \
 *                  (o) "fo"
 *                    \
 *                  [t   b] "foo"
 *                  /     \
 *         "foot" (e)     (a) "foob"
 *                /         \
 *      "foote" (r)         (r) "fooba"
 *              /             \
 *    "footer" []             [] "foobar"
 *
 * However, this implementation implements a very common optimization where
 * successive nodes having a single child are "compressed" into the node
 * itself as a string of characters, each representing a next-level child,
 * and only the link to the node representing the last character node is
 * provided inside the representation. So the above representation is turned
 * into:
 *
 *                  ["foo"] ""
 *                     |
 *                  [t   b] "foo"
 *                  /     \
 *        "foot" ("er")    ("ar") "foob"
 *                 /          \
 *       "footer" []          [] "foobar"
 *
 * However this optimization makes the implementation a bit more complex.
 * For instance if a key "first" is added in the above radix tree, a
 * "node splitting" operation is needed, since the "foo" prefix is no longer
 * composed of nodes having a single child one after the other. This is the
 * above tree and the resulting node splitting after this event happens:
 *
 *
 *                    (f) ""
 *                    /
 *                 (i o) "f"
 *                 /   \
 *    "firs"  ("rst")  (o) "fo"
 *              /        \
 *    "first" []       [t   b] "foo"
 *                     /     \
 *           "foot" ("er")    ("ar") "foob"
 *                    /          \
 *          "footer" []          [] "foobar"
 *
 * Similarly after deletion, if a new chain of nodes having a single child
 * is created (the chain must also not include nodes that represent keys),
 * it must be compressed back into a single node.
 *
 */
#define RAX_NODE_MAX_SIZE ((1<<29)-1)
typedef struct raxNode {
    uint32_t iskey:1;     /* Does this node contain a key? */
    uint32_t isnull:1;    /* Associated value is NULL (don't store it). */
    uint32_t iscompr:1;   /* Node is compressed. */
    uint32_t size:29;     /* Number of children, or compressed string len. */
    unsigned char data[];
} raxNode;

typedef struct rax {
    raxNode *head;
    uint64_t numele;
    uint64_t numnodes;
} rax;

typedef struct raxStack {
    void **stack; /* Points to static_items or an heap allocated array. */
    size_t items, maxitems; /* Number of items contained and total space. */
    void *static_items[RAX_STACK_STATIC_ITEMS];
    int oom; /* True if pushing into this stack failed for OOM at some point. */
} raxStack;

如Redis源码中的注释所写,RAX进行了一些优化,并不会将一个字符串直接按照每个字符进行树的构建,而是在Insert有冲突时节点分割处理,在Delete时如果子节点和父节点都只有一个,则需要进行合并操作。
对于RAX有兴趣的同学,可以看一下rax.h、rax.c的相关代码。

4.2 Linux内核

Linux radix树最广泛的用途是用于内存管理,结构address_space通过radix树跟踪绑定到地址映射上的核心页,该radix树允许内存管理代码快速查找标识为dirty或writeback的页。Linux radix树的API函数在lib/radix-tree.c中实现。
Linux基数树(radix tree)是将指针与long整数键值相关联的机制,它存储有效率,并且可快速查询,用于指针与整数值的映射(如:IDR机制)、内存管理等。

struct radix_tree_node {
        unsigned int    path;
        unsigned int    count;
        union {
                struct {
                        struct radix_tree_node *parent;
                        void *private_data;
                };
                struct rcu_head rcu_head;
        };
        /* For tree user */
        struct list_head private_list;
        void __rcu      *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

关于Linux内核使用Radix Tree的具体代码,有兴趣的同学可以继续深入。

5 总结

Trie树在单词搜索、统计、排序等领域有大量的应用。文章从基础概念到具体的脏话过滤的应用、Redis的RAX和Linux内核的Radix Tree对Trie树做了介绍。数据结构和算法是程序高性能的基础,本文抛砖引玉,希望大家对Trie树有所了解,并在未来开发过程实践和应用Trie树解决中类似情景的问题。

点赞
收藏
评论区
推荐文章
九路 九路
3年前
前端学数据结构与算法:二叉树的四种遍历方式及其应用
前言上一章我们从0到1的实现了一颗二叉搜索树,以及理解了二叉搜索树的特性与基本操作,这一章介绍关于二叉树的更多操作,也就是树的遍历,对树的每个节点进行访问。主要包括前序遍历、中序遍历、后序遍历、层序遍历,前面三种也叫深度优先遍历(DFS),最后的层序遍历也叫广度优先遍历(BFS),理解这四种遍历方式的不同,再遇到树相关的算法问题时,也就能更加游刃有余。这
22 22
2年前
二叉树创建后,如何使用递归和栈遍历二叉树?
0.前言前文主要介绍了树的相关概念和原理,本文主要内容为二叉树的创建及遍历的代码实现,其中包括递归遍历和栈遍历。1.二叉树的实现思路1.0.顺序存储——数组实现前面介绍了满二叉树和完全二叉树,我们对其进行了编号——从0到n的不中断顺序编号,而恰好,数组也有一个这样的编号——数组下标,只要我们把二者联合起来,数组就能存储二叉树了。那么非满
高级java面试题,附答案+考点
蚂蚁金服一面1.两分钟的自我介绍2.二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL树)和弱平衡二叉树(红黑树)有什么区别3.B树和B树的区别,为什么MySQL要使用B树4.HashMap如何解决Hash冲突5.epoll和poll的区别,及其应用场景6.简述线程池原理,FixedThreadPoo
深入理解跳表及其在Redis中的应用
跳表可以达到和红黑树一样的时间复杂度O(logN),且实现简单,Redis中的有序集合对象的底层数据结构就使用了跳表。其作者威廉·普评价:跳跃链表是在很多应用中有可能替代平衡树的一种数据结构。本篇文章将对跳表的实现及在Redis中的应用进行学习。
Stella981 Stella981
2年前
DAT (Double Array Trie) 多模式匹配算法
一、简介:1.1、字典树trie:  字典树trie搜索关键码的时间和关键码自身及其长度有关,最快是0(1),,即在第一层即可判断是否搜索到,最坏的情况是0(n),n为Trie树的层数。由于很多时候Trie树的大多数结点分支很少,因此Trie树结构空间浪费比较多。  关键码检索策略可以根据关键码是否可以动态变化
Easter79 Easter79
2年前
Trie 的原理和实现 (python 实现)
原理:(fromwiki)Incomputerscience(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fen.wikipedia.org%2Fwiki%2FComputer_science),atrie,orprefixtree,isano
Wesley13 Wesley13
2年前
MySQL面试(二)
1、为什么索引遵循最左匹配原则?  当B树的数据项是符合的数据结构,比如(name,age,sex)的时候,B树是按照从左到右的顺序建立搜索树的。比如当(张三,20,F)这样的数据来检索的时候,b树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据;但当(20,F)这样的没有name的数据来的时候
Wesley13 Wesley13
2年前
MySQL知识体系——索引
    本文直切主题,针对InnoDB引擎描述索引及优化策略。在开始之前,需要读者了解:1)二叉查找树(包括23查找树、红黑树等数据结构)2)MySQL的InnoDB引擎基础知识索引初探要了解索引,当然要了解其数据结构。树有很多应用,流行的用法之一是包括UNIX和DOS在内的许多常用操作系统中的目录结构,二叉查找树又是Java中两种集合
Wesley13 Wesley13
2年前
Java数据结构和算法(十五)——无权无向图
前面我们介绍了树这种数据结构,树是由n(n0)个有限节点通过连接它们的边组成一个具有层次关系的集合,把它叫做“树”是因为它看起来像一棵倒挂的树,包括二叉树、红黑树、234树、堆等各种不同的树,有对这几种树不了解的可以参考我前面几篇博客。而本篇博客我们将介绍另外一种数据结构——图,图也是计算机程序设计中最常用的数据结构之一,从数学意义上讲
京东云开发者 京东云开发者
1个月前
深入理解经典红黑树 | 京东物流技术团队
本篇我们讲红黑树的经典实现,Java中对红黑树的实现便采用的是经典红黑树。前一篇文章我们介绍过左倾红黑树,它相对来说比较简单,需要大家看完上篇再来看这一篇,因为旋转等基础知识不会再本篇文章中赘述。本篇的大部分内容参考《算法导论》和Java实现红黑树的源码,