标签归档:哈希表

基于哈希表和二叉树的词典研究(一)

作者:王增才

邮箱:wzc@zencai.com

摘要 词典是许多中文分词系统的一个重要的组成部分。其查询速度直接影响到分词系统的处理速度。本文使用汇编语言设计了一种高效的基于哈希表和二叉树的分词词典。

关键词 中文分词 哈希表 二叉树 词典

Study on Chinese Word Segmentation Based on Hash Table and Binary Tree

Abstract The dictionary mechanism serves as one of the important components in a lot of Chinese word segmentation systems. Its perfomance influences the segmentation speed significantly. In this paper,we design a highly efficient dictionary mechanism in Assemble language, which is based on Hash table and binary tree.

Key words Chinese segmentation; Hash table; Binary tree; Dictionary

一 介绍

虽然有人提出了不需要词典的中文分词算法,如胥桂仙等人利用统计提出了基于“找最长字共现”原则的分词算法。[2] 但是,不管是基于规则方法还是统计方法,大部分中文分词算法都有自己的词典。词典的查询速度直接影响到分词系统的处理速度。本文使用汇编语言(编译器MASM32V10)设计了一种高效的基于哈希表和二叉树的分词词典。该算法为:将所有的汉字利用哈希表存储,即根据汉字机内码的编码规律,通过直接寻址哈希函数实现词语首字的快速查找,其查找时间为O(1);然后将首字相同的词语用二叉树存储;最后将二叉树的内存地址与哈希表进行绑定。 继续阅读