原创：自定义三叉树（二）

wuliws

　　之前写的三叉树，有点儿简单，并不能满足实际项目的需要。先简单分析一下solr中搜索推荐系统的核心算法。
　　wiki中有关于solr的搜索推荐的详细描述，但是核心算法需要自己查看源代码。关于wiki上的解读，之前做了一次简单的翻译，根据此文档，详细研读了源代码，先把核心思想呈现出来。
　　基本流程如下：当用户输入搜索词语前缀时，通过前端调用solr的suggest，找到Suggeser对象，Suggester根据匹配的field从主索引库中读取field下面的terms，来构建dictionry,由于主索引库中的terms是经过合并和排序的，索引在构建三叉树的时候，省去了用pinyin4j组件进行排序的过程。接下来，就是通过对字典的折中处理，来实现自平衡的三叉树，以提高检索效率。三叉树构建完之后，进行前缀匹配查询，搜索出所有符合要求的词元，然后加入到优先级队列中，构建有限容量的堆，调整堆顶的值为最小。之所以Lucene自己写了PriorityQueue<T>,而不用jdk自身的，是因为jdk的PriorityQueue<T>,容量可以扩展的，他会把所有匹配出来的词元都加进去，然后输出top N词元，这明显是内存浪费。之前的一篇关于从海量数据中，查找出top N数据的博客中，已经阐述了堆排序的思想，不赘述。最后通过优先级队列输出结果。
　　Suggester---Lookup----LookupImpl(TSTLookup、JaSpellLookup、FSTLookup),之前研读的是TSTLookup。排序的核心思想是：构建完字典之后，得到Dictionry对象，由Dictionary对象得到InputIterator，对字典进行扫描读取，能读取到两个变量：一个为term，另一个为term的权重，排序用的。对字典扫描结束后，把terms和weight分别加载到两个list中，以便插入三叉树中。那么，三叉树节点对象的设计，就很重要了。封装以下属性：storedChar、val（weight）、token（最后节点存储的term成词）。插入的具体逻辑，自己对上次的写的三叉树，进行了改进，代码如下：
　　package chinese.utility.ternaryTree;
　　/**
　　* 三叉树节点
　　* @author TongXueQiang
　　* @date 2016/03/12
　　* @since JDK 1.7
　　*/

　　public>　　public char storedChar;//节点存储的单个字符
　　public String token;//最后一个节点存储的term（成词）
　　public TernaryNode leftNode,centerNode,rightNode;//子节点
　　public TernaryNode (char storedChar)  {
　　this.storedChar = storedChar;
　　}
　　}
　　package chinese.utility.ternaryTree;
　　import java.util.ArrayList;
　　import java.util.List;
　　import java.util.Stack;
　　/**
　　* 自定义三叉树
　　*
　　* @author TongXueQiang
　　* @date 2016/03/12
　　* @since JDK 1.7
　　*/

　　public>　　// 根节点,不存储字符
　　private static TernaryNode root = new TernaryNode('\0');
　　/**
　　* 向树中插入字符
　　*
　　* @param TernaryNode
　　* @param word
　　* @return
　　*/
　　public void insert(String word) {
　　root = insert(root, word, 0);
　　}
　　public TernaryNode insert(TernaryNode currentTernaryNode, String word, int index) {
　　if (word == null || word.length() < index) {
　　return currentTernaryNode;
　　}
　　char[] charArray = word.toCharArray();
　　if (currentTernaryNode == null) {
　　currentTernaryNode = new TernaryNode(charArray[index]);
　　}
　　if (currentTernaryNode.storedChar > charArray[index]) {
　　currentTernaryNode.leftNode = insert(currentTernaryNode.leftNode, word, index);
　　} else if (currentTernaryNode.storedChar < charArray[index]) {
　　currentTernaryNode.rightNode = insert(currentTernaryNode.rightNode, word, index);
　　} else {
　　if (index != word.length() - 1) {
　　currentTernaryNode.centerNode = insert(currentTernaryNode.centerNode, word, index + 1);
　　} else {
　　currentTernaryNode.token = word;
　　}
　　}
　　return currentTernaryNode;
　　}
　　/**
　　* 查找以指定前缀开头的所有字符串
　　*
　　* @param prefix
　　* @return
　　*/
　　public List<TernaryNode> prefixCompletion(String prefix) {
　　// 首先查找前缀的最后一个节点
　　TernaryNode TernaryNode = findNode(prefix);
　　return prefixCompletion(TernaryNode);
　　}
　　public List<TernaryNode> prefixCompletion(TernaryNode p) {
　　List<TernaryNode> suggest = new ArrayList<TernaryNode>();
　　if (p == null) return suggest;
　　if ((p.centerNode == null) && (p.token == null)) return suggest;
　　if ((p.centerNode == null) && (p.token != null)) {
　　suggest.add(p);
　　return suggest;
　　}
　　if (p.token != null) {
　　suggest.add(p);
　　}
　　p = p.centerNode;
　　Stack<TernaryNode> s = new Stack<TernaryNode>();
　　s.push(p);
　　while (!s.isEmpty()) {
　　TernaryNode top = s.pop();
　　if (top.token != null) {
　　suggest.add(top);
　　}
　　if (top.centerNode != null) {
　　s.push(top.centerNode);
　　}
　　if (top.leftNode != null) {
　　s.push(top.leftNode);
　　}
　　if (top.rightNode != null) {
　　s.push(top.rightNode);
　　}
　　}
　　return suggest;
　　}
　　/**
　　* 查找前缀的下一个centerTernaryNode,作为searchPrefix的开始节点
　　*
　　* @param prefix
　　* @return
　　*/
　　public TernaryNode findNode(String prefix) {
　　return findNode(root, prefix, 0);
　　}
　　private TernaryNode findNode(TernaryNode TernaryNode, String prefix, int index) {
　　if (prefix == null || prefix.equals("")) {
　　return null;
　　}
　　if (TernaryNode == null) {
　　return null;
　　}
　　char[] charArray = prefix.toCharArray();
　　// 如果当前字符小于当前节点存储的字符，查找左节点
　　if (charArray[index] < TernaryNode.storedChar) {
　　return findNode(TernaryNode.leftNode, prefix, index);
　　}
　　// 如果当前字符大于当前节点存储的字符，查找右节点
　　else if (charArray[index] > TernaryNode.storedChar) {
　　return findNode(TernaryNode.rightNode, prefix, index);
　　} else {// 相等
　　// 递归终止条件
　　if (index !=charArray.length - 1) {
　　return findNode(TernaryNode.centerNode, prefix, ++index);
　　}
　　}
　　return TernaryNode;
　　}
　　}
　　改进后的三叉树，前缀匹配查找后得到结果不再是简单的字符串，而是节点对象，里面封装了匹配的term和weight值。接下来，把得到的suggest加入得到优先级队列中，得到升序的结果。测试代码如下：
　　package chinese.utility.test;
　　import java.util.Stack;
　　import chinese.utility.utils.PriorityQueue;
　　/**
　　* 输出topN，用Lucene的PriorityQueue,思路和之前写过的堆排序类似,队列中容量为N，
　　* 当向队列中插入的时候，调整堆，让堆顶元素最小，当超过容量的时候，在插入的时候，如果插入
　　* 的元素比堆顶元素大，则替换之，如果小，废弃之。最后按升序排列输出topN.要实现lessThan
　　* 方法,确定比较的项目，比如输入token的权重weight.
　　* @author hadoop
　　* @date 2016/03/11
　　*/

　　public>　　public MyPriorityQueue(int num) {
　　super(num);
　　}
　　@Override
　　protected boolean lessThan(Object a, Object b) {
　　return (Integer)a < (Integer)b;
　　}
　　public static void main(String[] f) {
　　MyPriorityQueue priQueue = new MyPriorityQueue(3);            
　　priQueue.insertWithOverflow(100);
　　priQueue.insertWithOverflow(98);
　　priQueue.insertWithOverflow(84);
　　priQueue.insertWithOverflow(78);
　　// 打印结果,输出前三个最大值，按降序排列
　　Stack<Integer> stack = new Stack<Integer>();        
　　Integer v = (Integer) priQueue.pop();
　　while (v != null) {
　　stack.push(v);
　　v = (Integer) priQueue.pop();
　　}
　　Integer num = stack.pop();
　　while (num != null) {
　　System.out.println(num);
　　if (stack.isEmpty()) break;
　　num = stack.pop();
　　}
　　}
　　}
　　结果是：
　　100
　　98
　　84
　　然而，上述排序是根据term的词库频率，并不是根据用户的搜索频率，没有实现热搜。要想实现热搜，需要用另一个方案。之前的一篇博客中，有这么一道题目：用户在进行搜索时，搜索引擎的日志，会记录下用户的搜索轨迹。比如有一篇文档，里面有千万级的数量，去除重复后可能就有300万行，如何从中找出top 10的搜索字符串？之前只是写了思路，没有给出具体实现。实际项目中，需要借鉴这个思路，重新整理一下：
　　第一步：对文本进行排序和折中处理，更新文本，要要用到pinyin4j项目包；
　　第二步：把更新后的字典，加载到三叉树中，实现平衡的三叉树，自定义的三叉树要增加节点字符出现次数的变量，以便实现词频统计；
　　第三步：遍历字典，每次读到的词语，用三叉树查询，得到频率，然后把读到的词语和频率写到另一个文件中，用空格分开，类似于Key-value键值对形式；
　　第四步：和从海量数据中查找出前k个最小或最大值的算法（java）问题雷同，从海量数据中查找出前10个最小值；
　　第五步：得到最小频率值的堆后，从新的文本中找到对应的词语，加入到set中，统一频率的词语会有很多，而不是一个。
　　在实际项目中，如何记录用户的搜索频率？上述思路只能作为借鉴，看一下美团是如何做的：
　　考虑专门为关键字建立一个索引collection，利用solr前缀查询实现。solr中的copyField能很好解决我们同时索引多个字段(汉字、pinyin, abbre)的需求，且field的multiValued属性设置为true时能解决同一个关键字的多音字组合问题。配置如下：
　　

schema.xml:　　

　　
<field name="kw" type="string" indexed="true" stored="true" />  
　　
<field name="pinyin" type="string" indexed="true" stored="false" multiValued="true"/>
　　
<field name="abbre" type="string" indexed="true" stored="false" multiValued="true"/>
　　
<field name="kwfreq" type="int" indexed="true" stored="true" />
　　
<field name="_version_" type="long" indexed="true" stored="true"/>
　　
<field name="suggest" type="suggest_text" indexed="true" stored="false" multiValued="true" />
　　
------------------multiValued表示字段是多值的-------------------------------------
　　
<uniqueKey>kw</uniqueKey>
　　
<defaultSearchField>suggest</defaultSearchField>
　　

　　
说明：
　　
kw为原始关键字
　　
pinyin和abbre的multiValued=true,在使用solrj建此索引时，定义成集合类型即可：如关键字“重庆”的pinyin字段为{chongqing,zhongqing}, abbre字段为{cq, zq}
　　
kwfreq为用户搜索关键的频率，用于查询的时候排序
　　

　　
-------------------------------------------------------
　　

　　
<copyField source="kw" dest="suggest" />
　　
<copyField source="pinyin" dest="suggest" />
　　
<copyField source="abbre" dest="suggest" />
　　

　　
------------------suggest_text----------------------------------
　　

　　
<fieldType name="suggest_text" positionIncrementGap="100" autoGeneratePhraseQueries="true">
　　
<analyzer type="index">
　　
<tokenizer />
　　
&lt;filter
　　
synonyms="synonyms.txt"
　　
ignoreCase="true"
　　
expand="true" />
　　
<filter
　　
ignoreCase="true"
　　
words="stopwords.txt"
　　
enablePositionIncrements="true" />
　　
<filter />
　　
<filter protected="protwords.txt" />
　　
</analyzer>
　　
<analyzer type="query">
　　
<tokenizer />
　　
<filter
　　
ignoreCase="true"
　　
words="stopwords.txt"
　　
enablePositionIncrements="true" />
　　
<filter />
　　
<filter protected="protwords.txt" />
　　
</analyzer>
　　
</fieldType>
　　

　　

　　KeywordTokenizerFactory：这个分词器不进行任何分词！整个字符流变为单个词元。String域类型也有类似的效果，但是它不能配置文本分析的其它处理组件，比如大小写转换。任何用于排序和大部分Faceting功能的索引域，这个索引域只有能一个原始域值中的一个词元。
　　前缀查询构造:
　　

private SolrQuery getSuggestQuery(String prefix, Integer limit) {　　
SolrQuery solrQuery = new SolrQuery();
　　
StringBuilder sb = new StringBuilder();
　　
sb.append(“suggest:").append(prefix).append("*");
　　
solrQuery.setQuery(sb.toString());
　　
solrQuery.addField("kw");
　　
solrQuery.addField("kwfreq");
　　
solrQuery.addSort("kwfreq", SolrQuery.ORDER.desc);
　　
solrQuery.setStart(0);
　　
solrQuery.setRows(limit);
　　
return solrQuery;
　　
}