什么是基树?

属性: :CUSTOM_ID: what-are-radix-trees :CUSTOM_ID what-are-radix-trees

结束:

Rather than go into the implementation and detailed explanation of Radix trees check them out on Wikipedia or your favourite algorithms textbook . For the purposes of this post let's go with a super imprecise explanation. When you store a map of keys that are associated with some value there are a number of ways to represent that as a data structure. What Radix Trees offer is that when the key is a sequence of some kind (say a string of characters or a list of numbers) we can store the keys in a much abbreviated format, taking advantage of the shared prefixes amongst many keys. For example most Vancouver phone numbers begin with 778 or 604. Most of the numbers in a radix tree can be stored under one of those three digit prefixes rather than in three levels of tree (7,7,8...). If that's confusing never mind, it will become clear as we progress... 你可以在维基百科或你最喜欢的算法教科书中查看它们，而不是深入研究基数树的实现和详细解释。出于这篇文章的目的，我们来做一个超级不精确的解释。当您存储与某个值关联的键的映射时，有许多方法可以将其表示为数据结构。基数树所提供的是，当键是某种序列(比如一串字符或一串数字)时，我们可以以非常简短的格式存储键，利用许多键之间共享的前缀。例如，大多数温哥华的电话号码以778或604开头。基数树中的大多数数字都可以存储在其中一个三位前缀下，而不是存储在三层树中(7,7,8…)。如果这是令人困惑的，没关系，它会变得清楚，因为我们的进展…

**在Emacs中探索板蓝根树

属性: :CUSTOM_ID: exploring-radix-trees-in-emacs :CUSTOM_ID exploring-radix-trees-in-emacs

结束:

A small example... say we want to store the following keys in a key value store: application, appetizer, applicative, apple. 一个小例子…假设我们想要在密钥值存储中存储以下密钥:应用程序、开胃菜、应用程序、苹果。

To start with we need an empty radix tree, which is just defined as nil: 首先我们需要一个空的基数树，它被定义为nil:

(require 'radix-tree)

radix-tree-empty

You add key/values to the map like this: 你添加键/值到地图，像这样:

(setq tree-1 (radix-tree-insert radix-tree-empty "application" t))
;; (("application" . t))

Note that inserting returns a new tree that contains just the single key “application”. For the purposes of our program we don't need to store an actualy value, we're just interested in the keys which represent valid English words, so we just store `t' which is true in Emacs Lisp. 注意，插入将返回一个新树，其中只包含单个键“application”。出于程序的目的，我们不需要存储一个实际值，我们只对表示有效英语单词的键感兴趣，所以我们只存储“t”，这在Emacs Lisp中是正确的。

Next we'll make a new tree by inserting the next word into `tree-1': 接下来，我们将插入下一个单词到“tree-1”来创建一个新树:

(setq tree-2 (radix-tree-insert tree-1 "appetizer" t))

;; (("app" ("lication" . t) ("etizer" . t)))

As you can see the radix tree split the key up into the shared prefixes between the two words. We can query how many words the tree has in total like this: 可以看到，基数树将键分成两个单词之间的共享前缀。我们可以查询这个树总共有多少个这样的单词:

(radix-tree-count tree-2)

;; 2 (#o2, #x2, ?C-b)

**减少列表和Dash列表API

属性: :CUSTOM_ID: reducing-a-list-and-the-dash-list-api :CUSTOM_ID reducing-a-list-and-the-dash-list-api

结束:

We've seen how to add elements one at a time to the tree, but our goal is to take a list of words and add them to a dictionary. For that we will need to use the `seq-reduce' function; a functional programming construct for reducing a sequence to a single value using some function that accumulates results: 我们已经了解了如何一次向树中添加一个元素，但是我们的目标是获取单词列表并将它们添加到字典中。为此，我们需要使用“seq-reduce”函数;一种函数式编程结构，用于使用一些累积结果的函数将序列缩减为单个值:

(seq-reduce (lambda (acc it) (radix-tree-insert acc it t)) '("application" "appetizer" "applicative" "apple") radix-tree-empty)

;; (("app" ("l" ("icati" ... ...) ("e" . t)) ("etizer" . t)))

In the output you can see that the four words have been neatly split into their shared and non-shared parts. 在输出中，您可以看到这四个单词被整齐地划分为它们的共享部分和非共享部分。

seq-reduce is fine for our purposes, but when working with Emacs lisp lists I prefer to use Dash which is a package providing a more modern list API. All Dash functions begin with a dash hence the name. We can replace the code above using Dash as follows: =seq-reduce=对于我们的目的是好的，但是当使用Emacs lisp列表时，我更喜欢使用Dash，它是一个提供更现代的列表API的包。所有的短横线函数都以短横线开头，因此得名。我们可以用下面的Dash替换上面的代码:

(require 'dash)
(-reduce-from (lambda (tree word) (radix-tree-insert tree word t)) radix-tree-empty '("application" "appetizer" "applicative" "apple"))

;; (("app" ("l" ("icati" ... ...) ("e" . t)) ("etizer" . t)))

In English when you refer to a word used earlier in the conversation you will say “it” instead, and this is called anaphora. Dash provides “anaphoric” versions of many of its functions that begin with two dashes that let you abbreviate the lambda form we used above and refer to each item as it. In the case of the --reduce-from we get both it and acc (for the accumulated result): 在英语中，当你提到之前在对话中使用的一个单词时，你会说“it”，这被称为回指。Dash提供了许多函数的“回指”版本，它们以两个破折号开头，允许您缩写我们在上面使用的lambda形式，并将每个项目称为它。在=——reduce-from=的情况下，我们得到了它和acc(对于累积的结果):

(--reduce-from (radix-tree-insert acc it t) radix-tree-empty '("application" "appetizer" "applicative" "apple"))

;; (("app" ("l" ("icati" ... ...) ("e" . t)) ("etizer" . t)))

That's nicer! Now we need a function that takes a sequence of words and adds them to a radix tree: 这是更好的!现在我们需要一个函数，采取一个序列的单词，并将它们添加到一个基数树:

(defun list-to-radix-tree(l)
(--reduce-from (radix-tree-insert acc it t) radix-tree-empty l))

(setq small (list-to-radix-tree '("application" "appetizer" "applicative" "apple")))

;; (("app" ("l" ("icati" ... ...) ("e" . t)) ("etizer" . t)))

**从文件中读取单词并生成基数树

属性: :CUSTOM_ID: reading-words-from-a-file-and-making-a-radix-tree :CUSTOM_ID reading-words-from-a-file-and-making-a-radix-tree

结束:

Our next step is to load the words for our custom dictionary from a file. The one in the github repo dictionary.txt contains 172k words. We can load it and turn it into a list of words, and finally build a radix tree as follows: 我们的下一步是从一个文件中为我们的自定义字典加载单词。github repo =字典里的那个。txt=包含172k个单词。我们可以加载它，把它变成一个单词列表，最后建立一个基数树如下:

(defun radix-tree-from-file(file-path)
(->
(with-temp-buffer
(insert-file-contents-literally file-path)
(buffer-substring-no-properties (point-min) (point-max)))
split-string
list-to-radix-tree))

(radix-tree-from-file "dictionary.txt")

Note the use of “->” which is a threading macro from Dash. It lets us put a list of operations together and “threads” the result from one step to the next, making things a bit easier to read. You'll see a similar operator in Clojure. 注意“->”的使用，这是一个线程宏从短跑。它让我们把一个操作列表放在一起，然后“线程”从一个步骤到下一个步骤的结果，使事情更容易阅读。您将在Clojure中看到类似的操作符。

加快速度

属性: :CUSTOM_ID: speeding-it-up :CUSTOM_ID:加速

结束:

Hmm, that was kinda slow. When we start using the Company mode we need to load the file and we don't want a delay like that. Let's use the emacs benchmark facility to see just how slow it is: 嗯，有点慢。当我们开始使用公司模式时，我们需要加载文件，我们不希望出现那样的延迟。让我们使用emacs基准测试工具来看看它有多慢:

(require 'benchmark)
(benchmark-elapse (radix-tree-from-file "dictionary.txt"))

;; 6.021951

Six seconds is a bit too much. How about we just write the radix tree to a file instead, then load that? First we need to write the tree to a string using print1-to-string, then we can stick that in a buffer and write it to a file. 六秒钟有点太长了。不如直接把基数树写入文件，然后再载入?首先，我们需要使用=print1-to-string=将树写入字符串，然后我们可以将其放入缓冲区并将其写入文件。

(defun write-text-to-file(text file-path)
(save-excursion
(let ((buffer (find-file file-path)))
(switch-to-buffer buffer)
(erase-buffer)
(insert text)
(save-buffer)
(kill-buffer))))

(setq dictionary (radix-tree-from-file "dictionary.txt"))

(write-text-to-file (prin1-to-string dictionary) "dictionary.el")

;; (write-text-to-file (prin1-to-string small) "dictionary.el")

Now let's see how much faster it is to simply load the data structure rather than build it: 现在让我们看看加载数据结构比构建它要快多少:

(defun tree-from-file(file-path)
(save-excursion
(let* ((buffer (find-file file-path))
(tree (read buffer)))
(kill-buffer buffer)
tree)))

(benchmark-elapse
(progn
(setq loaded-dictionary (tree-from-file "dictionary.el"))
t))

;; 0.198365

Great! The first time we run the program it will take 6 seconds to build, but subsequently we can load the radix tree data from disk which takes 0.2 seconds. That means if we prepare the dictionary.el file we can simply load that when the system starts without a noticable slowdown. The next step is to be able to find all the keys given a prefix. radix-tree-subtree does the job, returning a subtree rooted at the given prefix. Given the relevant subtree we can then iterate all of the keys and values using the function radix-tree-iter-mappings. Here we use the destructive !cons (also from Dash) to build up a list of all the keys, which we then return. This is now all the functionality we need to return for our auto-complete functionality: 太棒了!第一次运行该程序将需要6秒的时间来构建，但随后我们可以从磁盘加载基数树数据，这需要0.2秒。这意味着如果我们准备=dictionary。我们可以简单地加载时，系统启动没有明显的放缓。下一步是能够找到给定前缀的所有键。=radix-tree-subtree=执行此工作，返回在给定前缀处扎根的子树。对于相关的子树，我们可以使用=radix-tree- mappings=函数来迭代所有的键和值。这里我们使用了毁灭性的=!cons=(也来自Dash)构建所有键的列表，然后返回这些键。这是现在所有的功能，我们需要返回我们的自动完成功能:

(defun radix-tree-keys(subtree prefix)
(let (keys '())
(radix-tree-iter-mappings (radix-tree-subtree subtree prefix)
(lambda (key val)
(!cons (concat prefix key) keys)))
keys))

(radix-tree-keys loaded-dictionary "antidi")

;; ("antidiscrimination" "antidilution" "antidiarrheal" "antidiabetic")