https://zh.wikipedia.org/wiki/Trie
应用
trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。[4]
实现方式
trie树实际上是一个确定有限状态自动机(DFA)，通常用转移矩阵表示。行表示状态，列表示输入字符，（行，列）位置表示转移状态。这种方式的查询效率很高，但由于稀疏的现象严重，空间利用效率很低。也可以采用压缩的存储方式即链表来表示状态转移，但由于要线性查询，会造成效率低下。
于是人们提出了下面两种结构。[5]
- Black, Paul E. trie. Dictionary of Algorithms and Data Structures. 国家标准技术研究所. 2009-11-16. （原始内容存档于2010-05-19）.
- ^ 跳转至：2.0 2.1 Franklin Mark Liang. Word Hy-phen-a-tion By Com-put-er (PDF) (Doctor of Philosophy论文). Stanford University. 1983 [2010-03-28]. （原始内容 (PDF)存档于2010-05-19）.
- ^ Knuth, Donald. 6.3: Digital Searching. The Art of Computer Programming Volume 3: Sorting and Searching 2nd. Addison-Wesley. 1997: 492. ISBN 0-201-89685-0.
- ^ 米嘉. 大规模中文文本检索中的高性能索引研究 (硕士论文). [2005].
- ^ An Implementation of Double-Array Trie