- 单词
第一个问题是为文档中包含的单词生成一个列表。可以使用C++标准模版库中的sets和strings:
int main(void){ set <string> S; set <string>::iterator j; string t; while (cin >> t) S.insert(t); for (j = S.begin(); j != S.end(); ++j) cout << *j <<"\n"; return 0; }
完成上述过程后,用下面的C++程序完成对单词的计数:
int main(void){ map <string,int> M; map <string,int>::iterator j; string t; while (cin >> t) M[t]++; for (j = M.begin(); j != M.end(); ++j) cout << j->left << " " << j->second << "\n"; return 0; }
while语句将每个单词t插入映射M,并对相关的计数器(初始化为0)增1。for语句按排好的顺序遍历单词,并打印出每个单词(first)及其计数(second)。
为了减少处理时间,我们可以建立自己的散列表,散列表中的结点包含指向单词的指针、单词出现频率以及指向表中下一个结点的指针。实现散列表的数据结构:
typedef struct node * nodeptr; typedef struct node { char * word; int count; nodeptr next; }
据说即使在“宽松”的单词定义下(以空格分割的字符串),《圣经》中也只有29 131个单词。采用传统的办法,用跟29 131最接近的质数29989作为散列表大小(为什么?),定义乘数为31。
#define NHASH 29989 #define MULT 31 nodeptr bin[NHASH];
散列函数把每个字符串映射为一个小于NHASH的正整数:
unsigned int hash(char * p) unsigned int h = 0 for (; *p; p++) h = MULT * h + *p return h % NHASH
其中使用无符号数以确保h为正。
下面的main函数首先把每个箱都初始化为NULL,接着读取单词并增加计数值,然后迭代散列表输出(未排序的)单词和计数值:
int main(void) for i = [0, NHASH) bin[i] = NULL while scanf("%s", buf) != EOF incword(buf) for i = [0, NHASH) for (p = bin[i]; p != NULL; p = p->next) print p->word, p->count return 0
主要工作由incword完成,它负责增加与输入单词相关联的计数器的值:
void incword(char *s) h = hash(s) for (p = bin[h]; p != NULL; p = p->next) if strcmp(s, p->word) == 0 (p->count)++ return p = malloc(sizeof(hashnode)) p->count = 1 p->word = malloc(strlen(s)+1) strcpy(p->word, s) p->next = bin[h] bin[h] = p
前面主要涉及到表示单词集合的两种主要方法:平衡搜索树和散列方法。前者将字符串看作不可分割的对象进行操作,标准模版库的set和map中大部分实现都使用这种结构。平衡搜索树中的元素始终处于有序状态,从而很容易执行寻找前驱结点或者按顺序输出元素之类的操作。另一方面,散列则需要深入字符串的内部,计算散列函数并将关键字分散到一个较大的表中。散列方法的平均速度很快,但缺乏平衡树提供的最坏情况性能保证,也不能支持其他涉及顺序的操作。
- 短语
问题:给定一个文本文件作为输入,查找其中最长的重复子字符串。
利用全新的数据结构解决问题:后缀数组。
假设程序最多处理MAXN个字符,这些字符存储在数组c中:
#define MAXN 5000000 char c[MAXN], *a[MAXN];
其中的a就是后缀数组,其初始化代码为:
while (ch = getchar()) != EOF a[n] = &c[n] c[n++] = ch c[n] = 0;//字符串结束
可以看出,数组a中指针所指的对象包含了字符串的每一个后缀。
对后缀数组进行排序后比较相邻元素就可以找出最长重复字符串。例如利用qsort进行排序:
qsort(a, n, sizeof(char *), pstrcmp)
其中比较函数pstrcmp实际上是对strcmp库函数的一层间接调用。扫描数组时,使用comlen函数统计两个相邻单词共有的字母数:
for i = [0, n) if comlen(a[i], a[i+1]) > maxlen maxlen = comlen(a[i], a[i+1]) maxi = i printf(“%.*s\n”, maxlen, a[maxi])
printf语句使用“*”精度输出字符串中的maxlen个字符。
comlen定义如下:
int comlen(char *p, char *q) i = 0 while *p && (*p++ == *q++) i++ return i
- 生成文本
先读取一个样本,统计A之后每个字母出现的次数、B之后每个字母出现的次数,等等。在写随机样本的时候,我们用当前字母的一个随机函数生成下一个字母,这样就可以生成“1阶(Order-1)”文本。
将这一思想扩展到更长的字母序列上,2阶文本是通过把每个字母设置为其前面两个字母的函数得到的(一对字母通常称为二连字母),以此类推。到了4阶文本,大多数单词都是英文单词了。
这个过程可以视为一个马尔科夫链,每个状态表示一个k连字母,并且从一个状态到另一个状态的概率是不变的。因此这是一个“具有固定转换概率的有限状态马尔科夫链”。
这个生成文本的艰苦工作可以借助程序来自动完成。我们生成k阶马尔科夫链的的C程序最多在数组inputchars中存储5MB的文本:
int k = 2; char inputchars[5000000]; char *word[1000000]; int nword = 0;
为了加快程序运行的速度,我们把word作为一种指向字符的后缀数组,不同之处在于它仅从单词的边界开始。变量nword存储单词的数目。读取文件的代码为:
word[0] = inputchars while scanf(“%s”, word[nword]) != EOF word[nword+1] = word[nword] + strlen(word[nword]) + 1 nword ++
每个单词附加到inputchars的后面,并用scanf提供的空字符作为结束标志。
比较函数,以对word数组进行排序:
int wordncmp(char *p, char * q) n = k for (; *p == *q; p++, q++) if(*p == 0 && --n == 0) return 0 return *p - *q
该函数在字符相同时扫描两个字符串。每次遇到空字符时将计数器n减1,并在找到k个相同的单词后返回相同;当遇到不同字符时,返回差别。
读完输入后,先在word数组后面附加k个空字符(这样比较函数就不会运行到最后),并输出文档的前k个单词(启动随机输出),然后调用排序:
for i = [0, k) word[nword][i] = 0 for i = [0, k) print[word][i] qsort(word, nword, sizeof(word[0]), sortcmp)
sortcmp为它的指针参数增加了一层间接调用。
生成无意义文本的伪代码描述:
phrase = first phrase in input array loop perform a binary search for phrase in word[0..nword-1] for all phrases equal in the first k words select one at random, pointed by p phrase = word following p if k-th word of phrase is length 0 break print k-th word of phrase
实现上述想法的完整的伪代码:
phrase = inputchars for (wordsleft = 10000; wordsleft > 0; wordsleft --) l = -1 u = nword while l+1 != u m = (l+u)/2 if wordncmp(word[m], phrase) < 0 l = m else u = m for (i = 0; wordncmp(phrase, word[u+i]) == 0; i++) if rand() % (i+1) == 0 p = word[u+i] phrase = skip(p, 1)//从p开始的下1个word if strlen(skip(phrase, k-1)) == 0 break print skip(phrase, k-1)
- 原理总结
字符串的数据结构。
散列。 这一结构的平均速度很快,且易于实现。
平衡树。 这些结构在最坏情况下也有较好的性能,C++标准模版库的set和map的大部分实现都采用平衡树。
后缀数组。 初始化指向文本中每个字符(或每个单词)的指针数组,对其排序就得到一个后缀数组。然后可以遍历该数组以查找接近的字符串,也可以使用二分搜索查找单词或短语。
使用库组件还是定制的组件?C++标准模版库中的sets、maps和strings使用起来都很方便,但是它们通用而强大的接口也意味着它们的效率不如专用的散列函数高。另外一些库组件则非常高效:散列使用strcmp,后缀数组使用qsort。作者在写本章中的二分搜索和wordncmp函数时参考了bsearch和strcmp的库实现。