[原创]Trie树--挑战自然语言单词识别

原文地址:http://www.pandaos.net/?id=42
利用了Trie树，这种算法非常高效，加上hash算法查找速度就更快了。
从70万条记录中查找数据都是瞬间的事情！
仅适用于英文单词！但中文原理也差不多！
[图片:201502031422959168106985.jpg]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <Windows.h>
typedef struct Word_Trie_
{
	bool IsEnd;
	struct Word_Trie_ *child[26]; //26个英文字符
}Word_Trie;
int count = 0;
int hash(char ch)
{
	return (ch-'a');
}
Word_Trie* SearchWord(Word_Trie *Root,char word)
{
	if (Root)
		return Root->child[hash(word)];
	return NULL;
}
Word_Trie* InsertWord(Word_Trie *parent,char word)
{
	Word_Trie *newNode;
	int t;
	newNode = (Word_Trie *)malloc(sizeof(Word_Trie));
	memset(newNode,0,sizeof(Word_Trie));
	parent->child[hash(word)]=newNode;
	count++;
	return newNode;
}
bool IsWord(Word_Trie *root,char *word)
{
	Word_Trie *subRoot;
	subRoot = root;
	if(!word)
		return false;
	for (int i=0;i<strlen(word);i++)
	{
		subRoot = SearchWord(subRoot,word[i]);
		if (!subRoot)
		{
			return false;
		}
	}
	return true;
}
void InsertStr(Word_Trie *root,char *str)
{
	int len = 0;
	Word_Trie *sub_root,*node1;
	sub_root = root;
	if (!sub_root)
		return ;
	len = strlen(str);
	for (int i=0;i<len;i++)
	{
		node1 = SearchWord(sub_root,str[i]);
		if(node1)
			sub_root = node1;
		else
			sub_root = InsertWord(sub_root,str[i]);
	}
	sub_root->IsEnd = true;
}
Word_Trie * Trie_init(FILE *dic)
{
	char buffer[64]={0};
	Word_Trie *Root,*word1=NULL;
	int len;
	if(dic==NULL) return NULL;
	Root = (Word_Trie*)malloc(sizeof(Word_Trie));
	memset(Root,0,sizeof(Word_Trie));
	while(!feof(dic))
	{
		Word_Trie *Sub_Root;
		fgets(buffer,32,dic);
		len = strlen(buffer)-1;
		Sub_Root = Root;
		for (int i=0;i<len;i++)
		{
			word1 = SearchWord(Sub_Root,buffer[i]);
			if(!word1)
			{
				Sub_Root=InsertWord(Sub_Root,buffer[i]);
			}else  //
			{
				Sub_Root = word1;
			}
		}
		Sub_Root->IsEnd = true; //最后一个节点.
	}
	return Root;
}
void main()
{
	FILE *dic;
	DWORD StartTime=0,endTime=0;
	Word_Trie *root = NULL,*w1,*w2;
	printf("Trie 树\n");
	printf("查询时请输入小写字符串!\n");
	dic = fopen("dict1.txt","r");
	if (!dic)
		printf("不能打开词库:dict.txt!");
	StartTime = GetTickCount();
	root=Trie_init(dic);
	endTime = GetTickCount();
	printf("载入词库用时:%d ms\n词条数:%d\n",endTime-StartTime,count);
	fclose(dic);
	while (true)
	{
		char buffer[32]={0};
		scanf("%s",buffer);
		StartTime = GetTickCount();
		if (IsWord(root,buffer))
		{
			endTime = GetTickCount();
			printf("在Trie树中查询到:%s  用时:%d ms\n",buffer,endTime-StartTime);
		}else
		{
			endTime = GetTickCount();
			printf("在Trie树中【没有】查询到:%s  用时:%d ms\n",buffer,endTime-StartTime);
		}
	};
	return;
}