【摘要】 本发明公开了一种基于比特映射的压缩键树的单词检索方法，它涉及到一种电子词典中单词检索的技术。它定义了非完全的压缩规则，可以将关键字为单字符的键树的结点进行压缩，形成关键字为多字符的结点。关键字为单字符的结点和关键字为多字符的结点不会为兄弟结点，并且使用了比特映射的方法表示了键树结构中是否存在对应的子结点且不需要经过比较，而是通过计算直接定位到该子结点的位置，虽然牺牲了一定的存储空间，但是检索速度将可以得到大大的提高。 【专利类型】发明授权 【申请人】中山大学; 广州中珩电子科技有限公司 【申请人类型】企业,学校 【申请人地址】510275 广东省广州市新港西路135号中山大学园南路415栋401室 【申请人地区】中国 【申请人城市】广州市 【申请人区县】海珠区 【申请号】CN200810028907.3 【申请日】2008-06-20 【申请年份】2008 【公开公告号】CN101299212B 【公开公告日】2010-12-08 【公开公告年份】2010 【授权公告号】CN101299212B 【授权公告日】2010-12-08 【授权公告年份】2010.0 【IPC分类号】G06F17/30 【发明人】罗笑南; 麦章灿 【主权项内容】一种基于比特映射的压缩键树的单词检索方法，其特征在于包括以下步骤：(1)根据单词分布和压缩规则生成非完全压缩的键树，所述压缩规则包括关键字为单字符的结点和关键字为多字符的结点不为兄弟结点，如果某结点的子结点个数大于1，则该结点的所有子结点均为关键字为单字符的结点，如果关键字为Value[i]的树结点TreePoint[i]和关键字为Value[k]的子结点TreePoint[k]可以进行非完全压缩合并，形成新的关键字为STRCAT(Value[i]，Value[k])的子树结点TreePoint[i，k]，定义其压缩规则如下：TreePoint[i]没有兄弟结点，即TreePoint[i]的父亲结点只有唯一的子结点；TreePoint[i]没有对应的单词，即根结点到TreePoint[i]的路径对应的字符串在词典中没有对应的单词存在，TreePoint[i]没有单词记录指针；TreePoint[k]没有兄弟结点，即TreePoint[i]只有唯一的儿子结点TreePoint[k]；(2)在非完全压缩的键树上采用包括关键字、长子结点的指针、单词记录指针和具有比特映射关系的比特映射码的数据结构；(3)在基于比特映射关系的键树中进行单词检索，包括根据比特映射码确定下一字符对应的键树节点的指针，根据所述指针进行检索。 【当前权利人】中山大学; 广州中珩电子科技有限公司 【当前专利权人地址】广东省广州市海珠区新港西路135号; 广东省广州市番禺区大学城中一路60号数字家庭孵化基地B301 【专利权人类型】; 有限责任公司 【统一社会信用代码】121000004558631445; 91440101MA9WHU7Q49 【家族被引证次数】6
