搜索引擎开发实践第四讲查词典的方法

《搜索引擎开发实践第四讲查词典的方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、搜索引擎开发实践第四讲查词典的方法主讲人：罗刚luogang@gmail.com概述作业讲解：统计单词频率数字搜索树Trie树构建平衡的Trie树作业：遍历Trie树作业讲解：统计单词频率//单词和对应的次数HashMapwordcount=newHashMap();StringTokenizerst=newStringTokenizer(inputStr);while(st.hasMoreTokens())//按空格切分输入串{Stringword=st.nextTo

2、ken();//检查单词是否在HashMap中if(wordcount.containsKey(word)){//取得单词出现次数，加1后放回去wordcount.put(word,wordcount.get(word)+1);}else{//第一次看到这个单词，设置次数为1次wordcount.put(word,1);}}散列与最长词匹配散列是一种常见的高效查找方法，它根据数组下标查询，所以速度快。首先根据词表构造散列表，具体来说就是用给定的散列函数构造词典到数组下标的映射，如果存在冲突，则根据选择的冲突处理方法解决地址冲突。然后

3、可以在散列表的基础上执行散列查找。不存在冲突的散列表叫做完美散列(perfecthash)。整词散列不适合分词的最长匹配查找方式。标准Trie树第5页rootabhitsteyenstoasatbebyheinisitto采用了逐字散列的方法，可以看成是一种逐字的完美散列dreddpkcotlleylll标准Trie树把单词中的每个字符逐字散列，整个词典组织成一个标准Trie树：除了根节点外的每个节点用一个字符标记，叫做splitChar类似有限状态机特别标记可以结束的状态，特别标记可以结束的节点例子：一个词典的标准Trie树S={

4、bear,bell,bid,bull,buy,sell,stock,stop}rlsuaeib使用数字搜索Trie树切分电话号码问题：输入电话号码，返回区位编号例如输入：037163949884返回：河南:郑州电话区位号码文件0701:江西:鹰潭0998:新疆:泽普县0851:贵州:贵阳0999:新疆:伊犁哈萨克自治州0852:贵州:遵义0853:贵州:安顺0994:新疆:奇台县0855:贵州:黔东南苗族侗族自治州数字搜索Trie树类似按字做散列区号有多长就有多少个节点对应每个节点对应一个TrieNode每个TrieNode包含一个

5、分隔字符splitChar例如：0371这个区号有四个节点对应也就是说四个TrieNode对象第一个对象中的splitChar属性是0第二个对象中的splitChar属性是3第三个对象中的splitChar属性是7第四个对象中的splitChar属性是1每个对象有10个孩子节点分别对应splitChar为0到90children3children7children1children叶节点存值信息根节点Trie树的特点多路树三叉Trie树是三路数字搜索Trie树是10路压缩同样的前缀字符共享同样的存储单元，例如：北京、北京市两个词。北

6、和京两个字的存储单元相同。使用逆Trie树来让后缀字符共享同样的存储单元，例如：复印机、打印机、传真机。共享“机”、“印”的存储单元。适合存储静态的数据词典不经常变化实现数字搜索树-Trie节点publicstaticfinalclassTrieNode{protectedTrieNode[]children;//孩子节点protectedcharsplitChar;//分隔字符protectedStringarea;//存储区位信息，类似HashMap中的Value/***构造方法**@paramsplitchar分隔字符*/pr

7、otectedTrieNode(charsplitchar){children=newTrieNode[10];area=null;this.splitChar=splitchar;}}实现数字搜索树-生成树privateTrieNoderoot;//树的根节点//把词加入词典privatevoidaddWord(Stringword,TrieNoderoot,Stringarea)throwsException{TrieNodecurrentNode=root;for(inti=1;i

8、rc0=word.charAt(i);intind=Integer.parseInt(word.substring(i,i+1));if(null==currentNode.children[ind]){currentNode.chi