文档介绍：数据结构设计是程序构造过程的中心环节。一旦数据结构安排好了，算法就像 是瓜熟蒂落，编码也比较容易。
这种观点虽然有点过于简单化，但也有一定道理。在数据结构中有关各种基本 数据结构，是许多程序的基本构件。在这一章中，我们将组合这些结构，要完此我们需要准备对付输入规模 n=100000 个词甚至更多的情况。输出将 包括几百甚至几千个词，而程序的运行应该在若干秒内完成，而不是几分钟。假定 输入文本有100000个词，n已经相当大了，因此，如果还要求程序运行得足够快， 这个算法就不会太简单。
马尔可夫算法必须在看到了所有输入之后才能开始产生输出。所以它必须以某 种形式存储整个输入。一个可能的方式是读完整个输入，将它存为一个长长的字符 串。情况的另一方面也很明显，输入必须被分解成词。如果另用一个指向文本中各
词的指针数组，输出的生成将很简单：产生一个词，扫描输入中的词，看看刚输出 的前缀有哪些可能的后缀，然后随机选取一个。但是，这个方法意味着生成每个词 都需要扫描100000 个输入词。1000个输出就意味着上亿次字符串比较。这样做肯 定快不了。
另一种可能性是存储单个的词，给每个词关联一个链表，指出该词在文本中的 位置。这样就可以对词进行快速定位。在这里可以使用第 2章提出的散列表。但是， 这种方式并没有直接触及到马尔可夫算法的需要。在这里最需要的是能够由前缀出 发快速地确定对应的后缀。
我们需要有一种数据结构，它能较好地表示前缀以及与之相关联的后缀。程序 将分两部分，第一部分是输入，它构造表示短语的整个数据结构；第二部分是随后 的输出，它使用这个数据结构，生成随机的输出。这两部分都需要（快速地）查询前 缀：输入过程中需要更新与前缀相关的后缀；输出时需要对可能后缀做随机选择。 这些分析提醒我们使用一种散列结构，其关键码是前缀，其值是对应于该前缀的所 有可能后缀的集合。
为了描述的方便，我们将假定采用二词前缀，在这种情况下，每个输出词都是 根据它前面的一对词得到的。前缀中词的个数对设计本身并没有影响，程序应该能 对付任意的前缀长度，但给定一个数能使下面的讨论更具体些。我们把一个前缀和 它所有可能后缀的集合放在一起，称其为一个状态，这是马尔可夫算法的标准术语。
对于一个特定前缀，我们需要存储所有能跟随它的后缀，以便将来取用。这些 后缀是无序的，一次一个地加进去。我们不知道后缀将会有多少，因此，需要一种 能容易且高效地增长的数据结构，例如链表或者动态数组。在产生输出的时候，我 们要能从关联于特定前缀的后缀集合中随机地选出一个后缀。还有，数据项绝不会 被删除。
如果一个短语出现多次，那么又该怎么办？例如，短语“ might appear twice” 可能在文本里出现两次，而“ might appear once ”只出现了一次。这个情况有两 种可能的表示方式：或者在“
might appear ”的后缀表里放两个“ twice” ；或者
是只放一个，但还要给它附带一个计数值为2的计数器。我们对用或不用计数器的 方式都做过试验。不用计数器的情况处理起来比较简单，因为在加入后缀时不必检 查它是否已经存在。试验说明这两种方式在执行时间上的差别是微不足道的。
总结一下：每个状态由一个前缀和一个后缀链表组成。所有这些信息存在一个 散列表里，以前缀作为关键码。每个前缀是一个固定大小的词集合。如果一个后缀 在给定前缀下的出现多于一次，则每个出现都单独包含在有关链表里。
下面的问题是如何表示词本身。最简单的方法是把它们存储为独立的字符串。 在一般文本里总是有许多反复出现的词，如果为单词另外建一个散列表有可能节约 存储，因为在这种情况下每个词只需要存储一次。此外，这样做还能加快前缀散列 的速度，因为这时每个词都只有一个惟一地址，可以直接比较指针而不是比较词里 的各个字符。我们把这种做法留做练****下面采用每个词都分开存放的方式。
3在C中构造数据结构
现在开始考虑c语言中的实现。首先是定义一些常数：
const int NPREF = 3;
const int NHASH = 4093;
const int MAXGEN = 10000;
const int MULTIPLIER = 5;
这个声明定义了前缀中词的个数(NPREF)，散列表数组的大小(NHASH)，生成 词数的上界(MAXGEN)。如果NPREF是个编译时的常数而不是运行时的变量，程序 里的存储管理将会更简单些。数组的规模设得相当大，因为我们预计程序可能处理 很大的输入文件，或许是整本书。
选择NHASH=4093,这样，即使输入里有10000个不同前缀(词对)，平均链长 仍然会很短，大约两个到三个前缀。数组越大，链的期望长度越短，查询进行得也 越快