许多文档系统都提供了去除所有格式命令并查看输入的原始文本表示的方法。我在长文本上运行 15.2 节的字符串重复程序时发现，该程序对文本的格式非常敏感。程序处理詹姆斯一世钦定版《圣经》中的 4 460 056 个字符需要 36 秒，且最长的重复字符串为 269 个字符。如果删除每行的行号以标准化输入文本，那么长字符串就可以跨越行边界，从而最长的重复字符串达到了 563 个字符，但是程序找到它的时间几乎没有变。
3. 在 15.1 节的散列函数中采用答案 9.2 中的专用 malloc，能使速度提升多少？
由于该程序每次插入都需要执行很多次搜索，因此只有很少的时间用于内存分配。采用专用的存储分配器能使处理时间减少约 0.06 秒，能使插入程序的速度提高 10%，但是对整个程序的提速只有 2%。
4. 当散列表较大，且散列函数能够均匀分布数据时，表中每个链表的元素都不多。如果这两个条件都满足，那么查找所需的时间就会很多。如果 15.1 节的散列表中没有找到某个新的字符串，就将它放到链表的最前面。为了模拟散列存在的问题，将 NHASH 设置为 1，并用 15.1 节的链表策略和其他的链表策略（例如添加到链表的最后面，或者将最近找到的元素放置到链表的最前面）进行实验。
5. 在观察 15.1 节词频程序的输出时，将单词按频率递减的顺序输出是最合适的。如何修改 C 和 C++ 程序以完成这一任务？如何仅输出 M 个最常见的单词（其中 M 是常数，例如 10 或者 1000）？
可以在 C++ 程序中添加另一个映射，将一组单词跟它们的计数联系起来。在 C 程序中我们可以根据计数对数组排序，然后对其迭代（由于一些单词的计数会比较大，数组应该比输入文件小得多）。对于常见的文档，我们可以用关键字索引，并保存一个在一定范围（如 1~1 000）内计数的链表数组。
算法教材多次提醒我们注意类似于 "aaaaaaaa" 的输入。我发现对由换行符组成的文件计时要更容易一些。程序处理 5 000 个换行符需要 2.09 秒，处理 10 000 个换行符需要 8.90 秒，处理 20 000 个换行符需要 37.90 秒。这一增长速度要比平方快一些，也许正比于大约 n log2n 次比较，其中每次比较的平均开销都正比于 n。把一个大输入文件的两份拷贝拼接在一起产生的不良输入可能更接近实际生活。
子数组 a[i..i+M] 表示 M+1 个字符串。由于数组是有序的，我们可以通过调用在第一个和最后一个字符串上调用 comlen 函数来快速确定这 M+1 个字符串共有的字符数： comlen(a[i], a[i+M]) 本书网站提供了实现这一算法的代码。
把第一个字符串读入数组 c，记录其结束的位置并在其最后填入空字符；然后读入第二个字符串并进行同样的处理。跟以前一样进行排序。扫描数组时，使用"异或"操作来确保恰有一个字符串是从过滤点前面开始的。
下面的函数对 k 个单词组成的序列进行了散列，其中每个单词都以空字符结束：
unsigned int hash(char *p)
unsigned int h = 0
int n
for (n = k; n > 0; p++)
h = MULT * h + *p
if (*p == 0)
n-
return h % NHASH
本书网站上的一个程序使用这个散列函数取代了马尔可夫文本生成算法中的二分搜索，使平均运行时间从 O(n log n) 降到了 O(n)。该程序在散列表中为元素使用了链表表示法，只增加了 nwords 个 32 位整数的额外空间，其中 nwords 是输入中的单词个数。
15. 15.3 节中对香农的引用描述了他用来构建马尔可夫文本的算法，编写程序实现该算法。它给出了马尔可夫频率的很好的近似，但不是精确的形式。解释为什么不是精确的形式。编写程序从头开始扫描整个字符串（从而可以使用真实的频率）以生成每个单词。
假设我们正从一个有 100 万个单词的文档中生成 1 阶马尔可夫文本，该文档只在短语 "x y x z" 中包含单词 x、y 和 z。x 后面跟 y 的可能性应为 1/2，后面跟 z 的可能性也应为 1/2。在香农的算法中有什么差别？
如何利用 k 连字母或 k 连单词的计数？
一些商业语音识别器是基于三连统计的。