前缀树，又称字典树。常见的场景为大规模词库下做词匹配、词前缀匹配、词频统计等。目前唯一碰到的业务场景只有自建 UGC 风控的违禁词检测。

经典前缀树基于多叉树结构实现，组成字符串的字符全集数量决定了多叉树的阶。如下图为字符串集合 ab, abc, bc, d, da, dda 形成的前缀树。

前缀树的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销，相较于哈希等能够显著降低失配字符串的匹配耗时。

作为一个开放领域的知识社交平台，知乎为大家提供了「友善」、「理性」、「专业」的讨论氛围，吸引了大量用户参与，产生了很多优质内容。但同时也吸引了一些垃圾制造者，在知乎上生产了不少的垃圾内容，如「违法」、「广告」、「淫秽色情」、「人身攻击」等，严重影响了知乎用户的正常讨论交流，极大地影响了用户体验，同时也对社区管理造成了较大的干扰。

在本文中，我们将使用一种名为Double Array的数据结构在Python中构建Trie，并进行常见的前缀搜索。实现方式以德永的《日本输入法背后的技术》（德永，2012）一书为基础，对读过该书的人可能会有帮助。另外，我会介绍双数组的精髓，让没有参考书的人也能理解Trie使用双数组的实现。

Trie is a kind of digital search tree. (See [Knuth1972] for the detail of digital search tree.) [Fredkin1960] introduced the trie terminology, which is abbreviated from "Retrieval". Trie is an…

什么是Double Array Trie Double Array Trie是TRIE树的一种变形，它是在保证TRIE树检索速度的前提下，提高空间利用率而提出的一种数据结构，本质上是一个确定有限自动机(deterministic finite automaton，简称DFA)。 所谓的DFA就是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属&