搜索引擎的那些事（中文分词）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】 

    前面，我们在介绍搜索引擎的时候也谈到过中文分词。和英文不一样，中文上所有的汉字都是连在一起的，所以我们的一项工作就是把这些词语拆分成一个一个词组。因为只有这样才能构建索引数据库、才能查找索引，我们构建搜索引擎的工作才能继续进行下去。

    现在关于中分分词有好多的分词方法，什么从左向右最大长度法、从右向左最大长度法、最少词组法、贝叶斯概率处理法等等。但是说了这么多，我们分词的标准是什么，关键还在于有一个好的分词字典。中国汉字那么多，但是数量上估计几万个足够了。但是如果汉字与汉字组合起来构成词组，那数量就多了去了，比如说文学词语、口语、人名、地名、诗词、专业术语等等。说到这里，可以给大家举个例子看一下。大家都喜欢搜狗输入法，一方面它的设计比较人性化，另外一方面不正是因为它词库很多、使用方便吗？

    关于分词的算法，有的人觉得很玄乎，其实写一个也不复杂，我们就可以写一个最大长度遍历的分词算法。当然这里只是考虑了汉字分词，如果是英文、数字、繁体字或者符号，那就要另外考虑了。这也验证了我们之前反复说的一句话，简单做一件事不难，关键是怎么做好了、干漂亮了、高效又能节省成本。

#include <stdio.h>
#include <string.h>
#include <memory.h>
#include <malloc.h>

#define LENGTH 256
static char* dic[] = {"北京", "大学", "北京大学"};

#define NUMBER (sizeof(dic) / sizeof(char*))
static char* buffer[LENGTH] = {0};
static int max_len = 0;
static int min_len = 0;

static int  find_max_length()
{
	int index;
	unsigned int len;

	len = 0;
	for(index = 0; index < NUMBER; index ++)
	{
		if(len < strlen(dic[index]))
		{
			len = strlen(dic[index]);
		}
	}
	
	return len;
}

static int find_min_length()
{
	int index;
	unsigned int len;

	len = strlen(dic[0]);

	for(index = 1; index < NUMBER; index++)
	{
		if(strlen(dic[index]) < len)
		{
			len = strlen(dic[index]);
		}
	}

	return len;
}

static void show_buffer(int end)
{
	int start;

	for(start = 0; start < end; start ++)
	{
		printf("%s ", buffer[start]);
	}
		
	printf("\n");
}

static void _process_segment(char* str, int index)
{
	int start;
	int len ;
	int  found;
	char* data;
	char* label;
	
	if('\0' == *str)
	{
        show_buffer(index);
		return;
	}
	
	label = str + strlen(str);

retry:	
	len = strlen(str);
	if(len > LENGTH)
	{
		len = LENGTH;
	}
	
	if(len > max_len)
	{
		len = max_len;
	}

	found = 0;
	while(len >= min_len)
	{
		for(start = 0; start < NUMBER; start ++)
		{
			if(0 == strncmp(str, dic[start], len))
			{
				found = 1;
				break;
			}
		}
		
		if(found)
		{
			break;
		}
		
		len --;
	}
	
	/* if no str was found, just step forward, but cannot beyond label */
	if(len < min_len && str < label)
	{
		str ++;
		goto retry;
	}
	
	/* if no str was left, show all the str */
	if(str >= label)
	{
		show_buffer(index);
		return;
	}
	
	data = (char*) malloc(len + 1);
	if(NULL == data)
	{
		return;
	}
	
	data[len] = '\0';
	memmove(data, str, len);
	buffer[index] = data;
	
	_process_segment(str + len, index + 1);
	free(data);
	buffer[index] = NULL;
}

void process_segment(char* str)
{
	int length;

	if(NULL == str)
	{
		return;
	}
	
	length = strlen(str);
	if(length > LENGTH)
	{
		return;
	}
	
	_process_segment(str, 0);
}

void segment_init()
{
	min_len = find_min_length();
	max_len = find_max_length();
	memset(buffer, 0,  sizeof(buffer));
}

int main(int argc, char* argv[])
{
	segment_init();
	process_segment("北京 大学 日本");
	return 1;
}  

    代码中最复杂的函数其实就是_segment_process这个函数，中间涉及的情况比较多，可以简单介绍一下：

    （1）分词的时候建议考虑一下当前词库的最小长度和最大长度，可以避免不必要的比较；

    （2）分词如果查找失败，跳过从下一个字节开始继续查找；

    （3）函数采用了递归的方法，注意函数出口；

    （4）函数编写的时候注意buffer堆栈的浮动处理；

    （5）注意函数中判断条件的依据和原因。

    （6）这里dic的词库数量太少，要想利用process_segment进行分词处理，词库数量必须足够多。