《编程珠玑》第 15 章──字符串

本章主要讨论字符串的各种操作,比如排序、统计、搜索以及分析。

单词

统计文档中每个单词出现的次数。最简单的方法就是使用 C++ 中 STL 自带的 map 将字符串和计数联系起来。为了减少处理时间,使用散列表。

采用如下结构实现散列表:

1
2
3
4
5
6
typedef struct node *nodeptr;
typedef struct node {
char * word;
int count;
nodeptr next;
} node;

短语

给定一个文本文件作为输入,查找其中最长的重复子字符串。需要使用一个称为「后缀数组」的简单数据结构。在后缀数组中,每个元素指向字符串的不同的位置。举个例子,输入字符串「banana」,那么第一个元素指向整个字符串,第二个元素从第二个字符开始,指向后面所有的字符。

1
2
3
4
5
6
a[0]: banana
a[1]: anana
a[2]: nana
a[3]: ana
a[4]: na
a[5]: a

因为如果一个子字符串出现了两次,那么它将出现在两个不同的后缀中。对数组 a 进行排序,接下来扫描数组,比较相邻元素来找到最长的重复字符串。

生成文本

在单词级别上生成随机文本,将 K 个连续单词做为一个状态,然后以一定的概率到达另外一个状态,这个过程可以看成是一个马尔可夫链。
具体的实现方法是:先找到一个初始短语,然后通过初始短语的最后一个(如果为空就停止)单词来找以该单词为开头的短语,然后在找到的一堆短语中随机选出一个即可,这里要使用蓄水池抽样算法。以此类推直到短语的最后一个为空。

习题

1

本章通篇对单词采用如下的简单定义:单词由空白字符隔开。但 HTML 或 RTF 等格式的许多实际文档包含格式命令。如何处理这种命令?是否还需要进行其他处理?

比如在 Python 中使用 lxml.html.document_fromstring() 就可以得到原文。

5

在观察 15.1 节词频程序的输出时,将单词按频率递减的顺序输出是最合适的。如何修改 C 和 C++ 程序以完成这一任务?如何仅输出 M 个最常见的单词(其中 M 是常数,例如 10 或者 1000 )?

先把计数排序,然后对排序后的数组逐一找到对应的单词,毕竟数组大小不是很大。

8

如何修改查找重复字符串的程序,以找出出现超过 M 次的最长的字符串?

对于已经排序后的后缀数组,每次逐次取 M+1 个相邻的字符串,然后取 M+1 个中的第一个和最后一个,取它们的最长的公共字符串。

9

给定两个输入文本,找出它们共有的最长字符串。

同样对两个文字进行后缀数组操作,但是扫描数组找最大子字符串时,需要采用「异或」操作保证每个数组出一个字符串。动态规划可以解决这个问题,LeetCode 上有相应的题目。

14

如何使用散列对马尔可夫程序提速?

NHASH 为最接近的质数来做为散列表的大小;MULT 为乘数。

1
2
3
4
5
6
7
8
9
10
11
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;
}