Question

使用文本的一个普遍的问题就是它占用了许多RAM——但是如果我们想要测试一下我们是否在之前见到过字符串或对它们的频率进行计数，那么让它们在RAM中是方便的，而不是让它们从磁盘中来回换页。以自然的方式存储字符串是代价昂贵的，但是trie树和有向无环的单词图（DAWGs）能够被用来压缩表示它们，然而又允许进行快速的操作。

这些更高级的算法能够让你显著节约RAM的使用量，这意味着你可能不需要扩展到更多的服务器上，对于生产系统有巨大的节省。在本节中，我们将看看使用trie树来压缩一个字符串集，从耗费1.1GB下降到254MB，而仅让性能发生微小的变化。

对于这个例子，我们将从维基百科的部分转储上构建而来。这个集合包含了8545076个唯一的符号，来自于英语维基百科的一部分，在磁盘上占用了111707546（111MB）之多。

符号从它们原来的文章上以空格符来分割。它们是具有可变长度的，并且包含了Uncode字符和数字。它们看起来就像：

faddishness
'melanesians'
Kharálampos
PizzaInACup™
url="http://en.wikipedia.org/wiki?curid=363886"
VIIIa),
Superbagnères.

我们将使用这个文本例子来测试我们如何能快速地构建持有每个唯一单词实例的数据结构，然后我们将看看如何能快速地查询已知的单词（我们将使用不常见的“Zwiebel”，来自于画家Alfred Zwiebel）。这让我们发问，“我们以前曾讲过Zwiebel吗？”符号寻找是一个普遍的问题，要能够快速地做出来是重要的。

　备忘　

当你在你自己的问题上尝试这些容器时，要注意你可能会看到不同的表现。每种容器以不同的方式构建了自己内部的结构，传递不同类型的符号可能会影响结构的构建时间，而且不同长度的符号会影响查询时间。总是要以系统的方法来做测试。

在800万个符号上尝试这些方法

图11-1显示了使用一些容器存储了800万个符号的文本文件（111MB原始数据），这些容器就是我们在本节中将要讨论的。X轴显示了每个容器的RAM使用情况，Y轴跟踪了查询时间，每个点的大小与构建结构所花的时间有关（更大的点意味着花费更久）。

就如我们在这张图表中所能见到的那样，set和DAWG的例子使用了许多RAM。List的例子内存开销大而且又慢。Marisa trie树和HAT trie树的例子对于这个数据集是最有效的，它们使用了其他方法四分之一的RAM，而几乎没有改变查找速度。

图11-1　DAWG和tries树与内置容器的对比

图表没有显示对没有排序方法的简单list的查找时间，我们将马上介绍，因为它花费得太久了。datrie的例子没有在绘图中包含，因为它会产生一个段错误（我们已经在过去的另一项任务中有这个问题）。当它工作时，它是快速而紧凑的，但是它能够展现出无法控制的难以做出解释的构建时间。因为它能比其他方法更快，所以值得把它包括进来，但是显而易见，你将要在你的数据上彻底测试它。

请注意你必须要使用多种不同的容器来测试你的问题——每一个容器有不同的权衡之处，例如构建时间和API的灵活性。

接下来，我们将构建一个进程来测试每个容器的行为。

1．list

让我们从最简单的方法开始。我们会把我们的符号加载进一个list中，接着使用一个O(n)的线性搜索来查询它。我们不能在已经提到过的大型例子中这样做——搜索花费了太久的时间——所以我们将用一个小得多的例子（499048 个符号）来演示技巧。

在接下来的每一个例子中，我们都使用一个产生器text_example.readers，用来同时从输入文件中抽取出Unicode符号。这意味着读取进程只使用了很少量的RAM：

t1 = time.time()
words = [w for w in text_example.readers]
print "Loading {} words".format(len(words))
t2 = time.time()
print "RAM after creating list {:0.1f}MiB, took {:0.1f}s".
  format(memory_profiler.memory_usage()[0], t2 - t1)

我们对能够以多快的速度查询到这个列表感兴趣。理想情况下，我们想要找到一个容器来存储我们的文本并且允许我们没有任何代价地来查询和修改它。为了查询它，我们使用timeit来对已知的单词进行数次查找：

assert u'Zwiebel' in words
time_cost = sum(timeit.repeat(stmt="u'Zwiebel' in words",
                setup="from __main__ import words",
                number=1,
                repeat=10000))
print "Summed time to lookup word {:0.4f}s".format(time_cost)

我们的测试脚本报告大约59MB，被用来把原来5MB的文件作为一个列表来存储，查找时间是86秒：

RAM at start 10.3MiB
Loading 499048 words
RAM after creating list 59.4MiB, took 1.7s
Summed time to lookup word 86.1757s

把文本存储进一个没有排序的list明显是一个糟糕的主意。O(n)的查找时间是代价高昂的，内存使用也同样如此。这是所有情况中最糟糕的！

我们能够通过对list做排序以及通过bisect模块使用二分查找法来改进查找时间。对于将来的查询来说，这给了我们一个合理的下限。在例11-9中我们对排序列表所花费的时间进行计时。在这里我们切换到更大的有854506个符号的集合。

例11-9　对为了使用bisect而做准备的排序操作进行计时

  t1 = time.time()
  words = [w for w in text_example.readers]
  print "Loading {} words".format(len(words))
  t2 = time.time()
  print "RAM after creating list {:0.1f}MiB, took {:0.1f}s".
  format(memory_profiler.memory_usage()[0], t2 - t1)
  print "The list contains {} words".format(len(words))
  words.sort()
  t3 = time.time()
  print "Sorting list took {:0.1f}s".format(t3 - t2)

接下来我们像以前一样做相同的查找，但是使用额外的index方法，它使用了bisect:

import bisect
...
def index(a, x):
  'Locate the leftmost value exactly equal to x'
  i = bisect.bisect_left(a, x)
  if i != len(a) and a[i] == x:
    return i
  raise ValueError
...
  time_cost = sum(timeit.repeat(stmt="index(words, u'Zwiebel')",
                  setup="from __main__ import words, index",
                  number=1,
                  repeat=10000))

在例11-10中，我们看到RAM的使用比以前要大得多，因为我们明显装载进了更多的数据。排序进一步用去了16秒，而累计的查找时间却是0.02秒。

例11-10　对在一个排序列表上使用bisect进行计时

$ python text_example_list_bisect.py
RAM at start 10.3MiB
Loading 8545076 words
RAM after creating list 932.1MiB, took 31.0s
The list contains 8545076 words
Sorting list took 16.9s
Summed time to lookup word 0.0201s

现在我们有了一个对字符串查找计时的合理的基线：RAM使用必须要好于932MB，并且总共查找时间应该比0.02秒更少。

2．set

使用内置的set看起来或许是处理我们任务的最明显的方法了。在例11-11中，set在一个散列结构中存储了每一个字符串（如果你需要清醒一下，请看第4章）。检查成员是快速的，但是每一个字符串必须分开存储，在RAM上代价昂贵。

例11-11　使用一个set来存储数据

  words_set = set(text_example.readers)

就如我们在例11-12中所见的那样，set比list使用了更多的RAM；无论如何，它给了我们一个非常快速的查询时间，而不需要一个额外的index函数或者一个中间的排序操作。

例11-12　运行set的例子

$ python text_example_set.py
RAM at start 10.3MiB
RAM after creating set 1122.9MiB, took 31.6s
The set contains 8545076 words
Summed time to lookup word 0.0033s

如果RAM不昂贵，那么这可能是最合理的首选方法。

然而，我们现在已经丧失了原来数据的顺序。如果顺序对你是重要的，提示你可以把字符串作为键存储在字典里，每个值就是和原来的读取顺序相关的索引。这样，你就能向字典查询键是否存在，并请求它的索引。

3．更有效的树结构

让我们介绍一组更高效地使用RAM来表示字符串的算法。

来自维基共享资源的图11-2展示了4个单词在trie树和DAWG^[1]中的不同表示：“tap”、“taps”、“top”和“tops”。DAFSA是DAWG的另一个名称。使用一个list或者set，这些单词中的每一个都作为一个独立的字符串存储。DAWG和trie树共享了字符串的公共部分，所以用到的RAM更少。

DAWG和trie树的主要区别是trie树只共享公共前缀，然而DAWG共享公共前缀和后缀。在有很多公共单词前缀和后缀的语言中（就像英语），这样能减少很多重复。

精确的内存表现取决于你的数据结构。典型说来，一个DAWG不能分配一个值给键，这归因于从字符串的开始到结束之间的多条路径，但是展示在这里的版本能够接受一个值映射。Trie树也能接收一个值映射。有些结构不得不在开始扫描时构建，其他的则能在任何时候更新。

这些结构的一个巨大优势就是它们提供了一个公共前缀搜索，那就是你可以请求与你提供的前缀相同的所有单词。使用我们的4个单词列表，当搜索“ta”时，结果将是“tap”和“taps”。而且，既然这些结果是通过图结构所发现的，获取到它们是很快速的。例如，如果你正工作于DNA方面，使用trie树编辑数百万的短单词是减少RAM使用的一种有效方式。

图11-2　Trie树和DAWG结构（图片由Chkno提供【CC BY-SA 3.0】）

在下面的小节中，我们凑近看一看DAWGs、trie树和它们的用途。

4．有向无环单词图（DAWG）

有向无环图（MIT授权）企图高效地表示共享公共前缀和后缀的字符串。

在例11-13中，你会看到对DAWG的很简单的设置。对于这个实现，DAWG在创建后不能被修改，它读取了一个迭代器来立即创建自己。缺少创建之后的更新可能对你的使用场景来说是一个败笔。如果是这样，你可能需要研究用trie树来取代它。DAWG的确支持丰富的查询，包括前缀查找。它也允许持久化，并且支持把整数索引作为值与字节及记录值一起存储起来。

例11-13　使用DAWGl来存储数据

import dawg
...
  words_dawg = dawg.DAWG(text_example.readers)

就如你能够在例11-14中所看见的那样，对于相同组的字符串集，它比之前的set例子仅仅稍微少用了一些RAM。更类似的输入文本将会产生更强大的压缩。

例11-14　使用DAWG的例子

$ python text_example_dawg.py
RAM at start 10.3MiB
RAM after creating dawg 968.8MiB, took 63.1s
Summed time to lookup word 0.0049s

5．Marisa trie树

Marisa trie树（LGPL和BSD双授权）是一个使用Cython绑定外部库的静态trie树。因为它是静态的，它在创建之后就不能改动。它像DAWG一样支持把整数索引作为值与字符值及记录值一起存储。

一个键能被用来查询一个值，反之亦然。所有共享了相同前缀的键能被高效地找到。tries树的内容可以被持久化。例11-15图示了使用一个Marisa trie树来存储我们的样本数据。

例11-15　使用Marisa trie树来存储数据

import marisa_trie
...
  words_trie = marisa_trie.Trie(text_example.readers)

在例11-16中，我们可以看到相比DAWG的例子，在RAM存储方面有显著的提高，但是整体搜索时间更慢一点。

例11-16　运行Marisa trie树例子

$ python text_example_trie.py
RAM at start 11.0MiB
RAM after creating trie 304.7MiB, took 55.3s
The trie contains 8545076 words
Summed time to lookup word 0.0101s

6．Datrie树

双数组trie树，或者datrie（LGPL授权），使用了预先构建的字母表来高效地存储键。这种trie树能够在创建之后修改，但是只使用相同的字母表。它也能够寻找与所提供的键共享前缀的所有键，并且支持持久化。

它与HAT trie树一起提供了最快的查找时间之一。

　备忘　

当使用datrie树来做维基上的例子以及做以往的DNA表示的工作时，它有一个变态的构建时间。与其他用几秒完成构建的数据结构相比，它可能要花费几分钟或数小时来表示DNA字符串。

datre树需要一个字母表来呈现给构造函数，并且只有键才允许使用这个字母表。在我们的维基的例子中，这意味着我们需要对原始数据做两遍扫描。你可以在例11-17中看到这种情况。第一遍扫描把一个字母表的字符集构建成一个set，第二遍扫描构建trie树。这个更慢的构建过程允许更快的查找时间。

例11-17　使用一个双数组trie树来存储数据

import datrie
...
  chars = set()
  for word in text_example.readers:
    chars.update(word)
  trie = datrie.BaseTrie(chars)
...
  # having consumed our generator in the first chars pass,
    we need to make a new one
  readers = text_example.read_words(text_example.SUMMARIZED_FILE) # new generator
  for word in readers:
    trie[word] = 0

好悲伤，在这个例子数据集上，datrie树抛出了一个段错误，所以我们不能显示你的计时信息。我们选择把它包含进来，因为在其他的测试中，它要比下面的HAT Trie树倾向于更快一点（但是RAM使用要低效一点）。我们已经使用它成功地进行了DNA搜索，所以如果你有一个静态的问题并且它可以工作，你可以对它能很好地工作具有信心。如果你的问题具有可变化的输入，无论如何，这可能不是一个合适的选择。

7．HAT trie树

HAT trie树（MIT授权）使用了缓存友好的表达方式从而在现代CPU上达成非常快速的查找。它能够在创建后被修改，但是另一方面只有非常有限的API。

对于简单的使用场景，它具有很棒的性能，但是API的局限性（例如，缺少前缀查找）可能让它对你的应用来说用途更少。例11-18演示了在我们的例子数据集上使用HAT trie树。

例11-18　使用HAT trie树来存储数据

import hat_trie
...
  words_trie = hat_trie.Trie()
  for word in text_example.readers:
    words_trie[word] = 0

就如你能在例11-19中所见的那样，HAT trie树提供了我们的新数据结构中最快的查找时间，以及卓越的RAM使用。它在API上的局限意味着它的使用受到了限制，但是如果你只是需要在许多字符串中快速查找，那么这可能是你的解决方案。

例11-19　运行HAT trie例子

$ python text_example_hattrie.py
RAM at start 9.7MiB
RAM after creating trie 254.2MiB, took 44.7s
The trie contains 8545076 words
Summed time to lookup word 0.0051s

8．在生产系统中使用tries树 （和DAWGs）

trie树和DAWG数据结构提供了良好的收益，但是你还是必须在你的问题上对它们做基准测试，而不是盲目地采用它们。如果你的字符串上有重叠的序列，那么有可能你会看到对RAM使用的改进。

Tries树和DAWGs不是那么知名，但它们在生产系统上却提供了强大的收益。我们在12.4节中有一个令人印象深刻的成功故事。在DapApps（坐落在UK的一个Python软件工作室）的Jamie Matthews也有一个关于在客户系统中使用trie树来为客户做出更高效和更廉价的部署的故事：

在DabApps，我们经常设法处理复杂的技术架构问题，通过把复杂问题划分为小的、自包含的组件，一般使用HTTP在组件间进行网络通信来做到。这种方式（被称为“面向服务的”或者“微服务”架构）有各种益处，包括有可能在多个项目间复用或者共享单个组件的功能。

一个这样的任务就是做邮编的地理编码，这常常是我们面向客户的项目中的需求。这个任务把全部的UK邮编（例如：“BN11AG”）转变成一个经纬度的坐标对，从而使得应用可以执行诸如距离测量之类的地理空间计算。

在它的最底层，一个地理编码数据库是一个简单的字符串之间的映射，能够从概念上被表示成一个字典。字典的键是邮编，以一个规范的形式存储（“BN11AG”），值就是坐标的某种表示（我们使用了地理散列编码，但是简洁明了地来说，想象一下由逗号分隔的一对，例如：“50.822921，-0.142871”）。

在UK大约有170万个邮编。就如上面所描述的那样，简单地把全部数据集装载进一个Python字典要使用好几百兆字节的内存。使用Python的简单序列化（pickle）格式把这个数据结构在磁盘上做持久化需要一个不可接受的大量的存储空间。我们知道我们可以做得更好。

我们实验了几种不同的内存和磁盘存储以及序列化格式，包括把数据存储在诸如Redis和LevelDB之类的外部数据库中，而且还对键/值对做压缩。最终我们偶然想起使用trie树的主意。Trie树在表示内存中的大量字符串方面极其高效，而且可利用的开源库（我们选择了“marisa-trie树”）让它们变得非常易于使用。

最终的应用程序，包括了一个小型的由Flask框架所构建的web API使用了仅仅30MB的内存来表示完整的UK邮编数据库，并且能够令人愉快地处理大量的邮编查找请求。代码是简单的，服务很轻量化，而且无痛部署和运行在诸如Heroku一样的免费主机平台上，而且不需要或者不依赖于外部数据库。我们的实现是开源的，在https://github.com/j4mie/postcodeserver/上有提供。

——Jamie Matthews

DabApps.com技术总监（UK）