专利详情

专利名称	一种构造用于处理大规模词典的完美哈希函数的方法
申请号	CN200610171640.4	专利类型	发明专利
公开（公告）号	CN1996306	公开（授权）日	2007.07.11
申请（专利权）人	中国科学院计算技术研究所	发明（设计）人	龚才春
主分类号	G06F17/30(2006.01)	IPC主分类号	G06F17/30(2006.01)
专利有效期	一种构造用于处理大规模词典的完美哈希函数的方法至一种构造用于处理大规模词典的完美哈希函数的方法	法律状态	授权
说明书摘要	本发明涉及信息检索和自然语言处理技术领域，公开了一种构造用于处理大规模词典的完美哈希函数的方法，该方法包括：A、将待构造哈希函数的词典中的单词平滑；B、将平滑后词典按照单词长度分为n个子词典，对每个子词典构造相关图，n为自然数；C、对构造的每个子词典的相关图中的顶点进行排序，对排序后各顶点依次关联整数，将各单词映射到不同的哈希地址，得到词典的完美哈希函数。利用本发明，能够对包含上百万单词的词典成功构造完美哈希函数，并且能够处理中文等大字符集词典，填充因子接近1，提高了填充因子，缩短了构造时间，减少了哈希函数的工作空间。