利用多叉树(字典树)实现简单的快速搜索
今晚在公众号上看到一条题:
看到题目第一时间想到树,而且是多叉树。为什么呢?
首先说说为何不选择顺序表,我们来试想想,如果500万个单词放在顺序表上,不加索引而且乱序,那么搜索一个关键词为开头的单词的时间按最差算要500万次比较,简直疯狂。但是如果先按首字母a~z排序一次,并记住每个首字母的第一个单词在表格第几个位置,效率又要好些,如果第二个字母再排序一些再做索引,又好些。可是这样插入单词的效率就太低了,所以顺序表无论如何并不是一个好的选择。
然后我们换个想法,我们可以先把单词按照字母为单位分割,然后第1个字母在树的第一层搜索,若不存在该字母则添加该字母为本层的兄弟节点,存在该字母就选择第2个字母,跳到下一层的首节点,再逐个搜索,若不存在该字母则添加该字母为本层的兄弟节点,存在该字母就选择第3个字母,跳到下一层的首节点,再逐个搜索……,如此类推,直到搜索或添加最后一个字母时,把该节点标记为“单词最后字母”,即完成添加一个单词的任务。然后每个单词均进行一次这个行为,就完成了单词树,不仅不需要存储单词中同样的部分,而且在搜索时,最差情况仅 =(该语言字母数 * 单词长度),例如搜索一个10个字母构成的英文单词,最差只需要搜索26*10=260次,无论增加多少个单词也只需要这么多次,效率比搜索一个乱序表高好几个数量级了,也使得单词表的排序变得十分简单。
具体C语言实现代码如下:
字母单元定义:
typedef struct vocalUnit VocalUnit;
struct vocalUnit {
char isWord; //如果深搜的时候发现是单词的时候根据这个标记进行显示
char c; //同一层的邻居字母
struct vocalUnit *nextLayerHead; //以本节点开始的下一层的首节点
struct vocalUnit *nextBrother; //保存的字母
};
全部实现代码:
#include "stdio.h"
#include "stdlib.h"
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
/**************ChenJieZhu created at 20181030 18:00***********************/
typedef struct vocalUnit VocalUnit;
struct vocalUnit {
char isWord; //如果深搜的时候发现是单词的时候根据这个标记进行显示
char c; //同一层的邻居字母
struct vocalUnit *nextLayerHead; //以本节点开始的下一层的首节点
struct vocalUnit *nextBrother; //保存的字母
};
/**初始化节点**/
void initDictTrees(VocalUnit* unit) {
unit->isWord = 0;
unit->nextBrother = NULL;
unit->nextLayerHead = NULL;
unit->c = NULL;
}
/**添加单词到多叉树**/
void addWord(VocalUnit* vHead, char* word){
int len = strlen(word);
int i;
VocalUnit* cursor = vHead;
for(i = 0; i < len; i++) {
char c = word[i];
char nextBrotherisEmpty = 0;
while(cursor != NULL) {
if(cursor->c == NULL) { //如果结点内容为空,即为以下情况之一:1、该字母与该层所有兄弟都对比过之后发现不存在,需要在本层添加 2、在该分支中该字母到此层未出现过,需要保存
VocalUnit* newLayerHead = (VocalUnit*) malloc(sizeof(VocalUnit));
initDictTrees(newLayerHead);
cursor->c = c;
if(i == len - 1) {
cursor->isWord = 1;
} else { //创建下一层为新字母保存做准备
cursor->nextLayerHead = newLayerHead;
cursor = cursor->nextLayerHead;
}
break;
} else {
if(cursor->c == c) {
if(i == len - 1) { //如果最后一个字母与该层已存在的其中一个字母一样,标记为到此为一个单词
cursor->isWord = 1;
}
else if(cursor->nextLayerHead == NULL) { //如果需要遍历下一层,可是不存在下一层,就新建一层
VocalUnit* newLayerHead = (VocalUnit*) malloc(sizeof(VocalUnit));
initDictTrees(newLayerHead);
cursor->nextLayerHead = newLayerHead;
}
cursor = cursor->nextLayerHead; //预备遍历下一个字母,对应就是多叉树的下一层
break;
} else { //如果该字母与该层当前兄弟不一致,移动到下一个兄弟进行比较
if(cursor->nextBrother == NULL) { //如果没有下一个兄弟就创建下一个兄弟
VocalUnit* nextBrother = (VocalUnit*) malloc(sizeof(VocalUnit));
initDictTrees(nextBrother);
cursor->nextBrother = nextBrother;
}
cursor = cursor->nextBrother;
}
}
}
}
}
int layer = 0;
char content[100];
/**读取树中所有的单词**/
void readVolcalProc(VocalUnit* cursor){
if(cursor != NULL) {
layer++;
//printf("layer:%d:%c\n", layer, cursor->c);
content[layer - 1] = cursor->c;
if(cursor->isWord) {
printf("word:%s\n", content);
}
readVolcalProc(cursor->nextLayerHead);
content[layer - 1] = 0;
layer--;
readVolcalProc(cursor->nextBrother);
}
}
void readVolcal(VocalUnit* cursor) {
layer = 0;
memset(content, 0, 100);
readVolcalProc(cursor);
}
/**搜索某开头的所有内容**/
void searchProc(VocalUnit* cursor, char* key, int keyLen) {
while(cursor != NULL) {
if(key[layer] != cursor->c) {
cursor = cursor->nextBrother;
} else {
content[layer++] = cursor->c;
if(layer == keyLen && cursor->isWord) { //如果被搜索词发现本身也是一个单词,也显示一下
if(cursor->isWord) {
printf("word:%s\n", content);
}
}
cursor = cursor->nextLayerHead;
if(layer == keyLen) {
break;
}
}
}
readVolcalProc(cursor);
}
/**搜索某关键字开头的条目**/
void search(VocalUnit* cursor, char* key, int keyLen) {
layer = 0;
memset(content, 0, 100);
searchProc(cursor, key, keyLen);
}
int main(){
int in = open("dict.txt", O_RDONLY,S_IRUSR);
int i = 0;
char p;
char input[100];
int flag;
//init///
VocalUnit *vHead = (VocalUnit*) malloc(sizeof(VocalUnit));
char *str = malloc(100);
memset(str, 0, 100);
initDictTrees(vHead);
while((flag = read(in, &p, 1)) > 0) {
if(p == '\n') {
addWord(vHead, str);
memset(str, 0, 100);
i = 0;
}
else{
str[i] = p;
i++;
}
}
/**someTest:**/
addWord(vHead, "a");
addWord(vHead, "apple");
addWord(vHead, "app");
addWord(vHead, "banana");
addWord(vHead, "ash");
addWord(vHead, "123456789");
printf("Loading finished.\n");
//readVolcal(vHead);
do{
printf("\nplease input what you want to search:");
scanf("%s", input);
search(vHead, input, strlen(input));
} while(strcmp(input, "!") > 0);
return 0;
}
具体运行效果: