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(); } }
。
相关推荐
ACM Trie树 模板,字典树模板,数据结构
hash trie树 字典树,完整的sdk开发包 具有说明文档
散列索引多分支Trie树快速路由查找算法路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址,首先建立前 缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度...
Java实现字典树TrieTree,可用于计算出四六级试题的高频词.
字典树,Trie树,查找插入效率都很高的一种高级数据结构。
NULL 博文链接:https://auauau.iteye.com/blog/675645
数据结构与算法 课程设计说明书 拼写检查器 trie树 字典树.doc
从Trie树(字典树)谈到后缀树 -- 程序员面试必备
Trie树,又称字典树或前缀树,关于它的结构就不详细介绍了。Trie树在单词统计、前缀匹配等很多方面有很大用处。下面这篇文章主要介绍了Trie树,以及Java实现如何Trie树,有需要的朋友可以参考借鉴,下面来一起看看吧...
用C实现的数据结构Trie树算法 实验的函数的trie树的插入 搜索和删除
基于Java链表实现的字典树(trie),实现了增删改查等功能,它说摘要必须大于50字我还能说啥啥啥啥
对双数纽Trie 树(Double-Array Trie)分词算法进行了优化:在采用Trie 树构造 双数纽Trie 树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列; 将冲突的结点放入Hash表中,不需要重新分配...
傻傻分不清楚Trie树,又称字典树,是一种树形数据结构被广泛用于字符串的统计Trie树的构造Trie树节点的每个儿子都代表一个字母那么就可以用某节点到根的路径来
字典树,java语言 字典树,trie 每个节点26个子节点
在trie.c中,关于查找定义了两个函数,一个是find(),一个是search(),二者的区别是,前者仅判断一个字符串是否在树中出现,而后者除了判断字符串是否出现,还会判断待查找的字符串是否是一个合法的单词。
很容易上手的Trie树入门,特别适合于acm初学者
一个简单的C语言程序:用Trie树实现词频统计和单词查询
为了解决路由器报文转发中路由查找速度慢的瓶颈问题,在分析了路由器中广泛使用的各种典型IP路由算法的基础上,提出一种基于多分枝trie树的改进路由查找算法。在多分枝trie树中取消前缀查找,组成一个大的中间结点。...
字典树:又称为Trie,是一种用于快速检索的多叉树结构。Trie把要查找的关键词看作一个字符序列,并根据构成关键词字符的先后顺序构造用于检索的树结构;一棵m度的Trie树或者为空,或者由m棵m度的Trie树构成。
有时,我们会碰到对字符串的排序,若采用一些经典的排序算法,则时间复杂度一般为O(n*lgn),但若采用Trie树,则时间复杂度仅为O(n)