Trie字典树、数字查找、键树

1，需要先将要被查找的文字通过structure方法按照拼音构建成一棵树，每个匹配节点上装有查找目标对象。

 

2，完成的功能：用户在输入框里输入拼音或者汉字，输入内容转化成拼音，然后按照拼音遍历树，找到结果。

 

3，用到了开元包pinyin4j

 

4，没有考虑多音字。可以按需要对多音字做多路径存储。子节点可以优化成map结构，优化遍历速度。

 

package com.test.common.utils;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

/**
 * Trie字典树类，节点用内部类Node表示，提供构建树、插入节点、搜索、等方法。
 * 需要优化的地方：1，多音字，2子节点的存储结构和查找
 * @author yfchenlei
 * @date 2012-9-12
 */
public class Trie<T> implements Serializable{
	private static final long serialVersionUID = 5694541776693908755L;
	/**
	 * 根节点
	 */
	private Node<T> root;
	/**
	 * 最大搜索结果个数
	 */
	private int maxResult = 10;
	/**
	 *  默认构造方法
	 */
	public Trie(){
		
	}
	/**
	 * 带参构造方法
	 * @param maxResult 最大搜索结果个数
	 */
	public Trie(int maxResult){
		this.maxResult = maxResult;
	}
	/**
	 * 根据传入数据集合构建一颗字典树
	 * @param words 数据集合
	 */
	public void structure(Map<String, T> items){
		root = new Node<T>('0');
		if(items == null){
			return;
		}
		Iterator<String> it = items.keySet().iterator();
		while(it.hasNext()){
			String key = it.next();
			T value= items.get(key);
			if(value != null){
				insert(key, value);
			}
		}
	}
	/**
	 * 向字典树插入一个数据，word。
	 * @author yfchenlei
	 * @date 2012-9-12
	 * @param word 要插入到字典树的数据
	 */
	public void insert(String word,T item){
		String pinyin = PinYin.cn2Pinyin(word);
		if(root == null){
			root = new Node<T>('0');
		}
		Node<T> curNode = root;
		int wordLength = pinyin.length();
		for(int i = 0; i< wordLength; i++){
			char value = pinyin.charAt(i);
			Node<T> nextNode = curNode.getChild(value);
			if(nextNode == null){
				nextNode = new Node<T>(value);
				curNode.addChild(nextNode);
			}
			curNode = nextNode;
		}
		curNode.addItem(item);
	}
	/**
	 * 根据输入的word的拼音，查找符合这个拼音前缀的所有集合，但不超过最大结果个数。
	 * @author yfchenlei
	 * @date 2012-9-12
	 * @param word 根据这个数据进行查找
	 * @return 符合条件的集合
	 */
	public List<T> find(String word){
		List<T> result = new ArrayList<T>(maxResult);
		if(root == null || word == null){
			return result;
		}
		String pinyin = PinYin.cn2Pinyin(word);
		Node<T> curNode = root;
		for(int i = 0; i < pinyin.length(); i++){
			Node<T> child = curNode.getChild(pinyin.charAt(i));
			if(child != null){
				curNode = child;
			}else{
				return result;
			}
		}
		result = traverse(curNode, result);
		return result;
	}
	/**
	 * 遍历字典树的递归方法，每次递归，将结果积累到result参数。
	 * @author yfchenlei
	 * @date 2012-9-12
	 * @param node 当前节点
	 * @param result 结果集合
	 * @return 返回最后的集合
	 */
	private List<T> traverse(Node<T> node, List<T> result){
		if(node == null || result.size() == maxResult){
			return result;
		}
		List<T> items = node.getItems();
		if(items != null){
			if(result.size() + items.size() > maxResult){
				for(int i = 0; i < maxResult - result.size(); i++){
					result.add(items.get(i));
				}
			}else{
				result.addAll(node.getItems());
			}
		}
		Node<T>[] children = node.getChildren();
		if(children != null){
			for(int i = 0; i < children.length; i++){
				if(result.size() == maxResult){
					break;
				}
				traverse(children[i], result);
			}
		}
		return result;
	}

	/**
	 * trie的子类，表示树节点
	 * @author yfchenlei
	 * @date 2012-9-12
	 */
	@SuppressWarnings("hiding")
	class Node<T> implements Serializable{
		private static final long serialVersionUID = -7145041421696945423L;
		/**
		 * 节点的路径值
		 */
		private char value;
		/**
		 * 子节点集合
		 */
		private Node<T>[] children;
		/**
		 * 节点中的值集合，因为拼音可能重复，所以是集合。
		 */
		private List<T> items;
	
		public Node(char value){
			this.value = value;
		}
		
		public void addItem(T item){
			if(items == null){
				items = new ArrayList<T>(1);
			}
			items.add(item);
		}
		
		public void addChild(Node<T> node){
			if(children == null){
				this.children = new Node[26];
			}
			children[node.getValue() - 'a'] = node;
		}
		
		public Node<T> getChild(char value){
			int pos = value - 'a';
			if(children == null){
				return null;
			}
			return children[pos];
		}
		
		public char getValue() {
			return value;
		}

		public Node<T>[] getChildren() {
			return children;
		}
		
		public List<T> getItems() {
			return items;
		}
	}
}

 用到的转化拼音工具：

 

package com.test.common.utils;

import net.sourceforge.pinyin4j.PinyinHelper;
import net.sourceforge.pinyin4j.format.HanyuPinyinCaseType;
import net.sourceforge.pinyin4j.format.HanyuPinyinOutputFormat;
import net.sourceforge.pinyin4j.format.HanyuPinyinToneType;
import net.sourceforge.pinyin4j.format.exception.BadHanyuPinyinOutputFormatCombination;
/**
 * 汉字转拼音支持工具
 * @author yfchenlei
 * @date 2012-9-13
 */
public class PinYin {
	private static HanyuPinyinOutputFormat defaultFormat;
	
	static{
		defaultFormat = new HanyuPinyinOutputFormat(); 
        defaultFormat.setCaseType(HanyuPinyinCaseType.LOWERCASE); 
        defaultFormat.setToneType(HanyuPinyinToneType.WITHOUT_TONE);
	}
	
	public static String cn2Pinyin(String cn){
		StringBuffer result = new StringBuffer();
		char[] chars = cn.toCharArray();
		try {
	        for(int i = 0; i < chars.length; i++){
	        	if(chars[i] > 128){
	        		String[] pinyin = PinyinHelper.toHanyuPinyinStringArray(chars[i], defaultFormat);
        			result.append(pinyin[0]);
	        	}else{
	        		char letter = Character.toLowerCase(chars[i]);
	        		if(letter >= 98 && letter <= 122)
	        		result.append(chars[i]);
        		}
	        }
		} catch (BadHanyuPinyinOutputFormatCombination e) {
			e.printStackTrace();
			return null;
		}
        return result.toString();
	}
}

 

。

 

评论

3 楼 leichenlei 2012-10-11  

wd_demon 写道

刚看了下 Trie树 ，终于看明白了。

然后你说 子节点 用map会提高效率，这个为什么啊？

ps:发现PinYin的这段代码有BUG啊,

if(chars[i] > 128){ 
                    String[] pinyin = PinyinHelper.toHanyuPinyinStringArray(chars[i], defaultFormat); 
                    result.append(pinyin[0]);    //这个会包空指针啊~
                }

嗯，是有bug。
用数组插入快啊，但是查找遍历浪费时间；用map查询比较快，hash取值相当快啊~~
这个树目的是快速查找，所以牺牲插入速度，优化查找速度是对的啊.

2 楼 wd_demon 2012-09-27  

刚看了下 Trie树 ，终于看明白了。

然后你说 子节点 用map会提高效率，这个为什么啊？

ps:发现PinYin的这段代码有BUG啊,

if(chars[i] > 128){ 
                    String[] pinyin = PinyinHelper.toHanyuPinyinStringArray(chars[i], defaultFormat); 
                    result.append(pinyin[0]);    //这个会包空指针啊~
                }

1 楼 wd_demon 2012-09-27  

拿这个代码跑了一下，只支持顺序搜索啊，比如 张三“zhangsan” 我打个san就搜不出来了~ 看了下Trie这个类 没看懂~