内容简介:1、基本概念
1、基本概念
字典树 ,又称为单词查找树, Tire数 ,是一种树形结构,它是一种哈希树的变种。
时间复杂度分析:
假设建立了有N个单词的每个单词的最大长度是L的字典Trie树,那么插入一个单词的最坏时间复杂度是O(L),所以 建树的总的时间复杂度是O(NL)
查询一个单词前缀的单词个数最坏时间复杂度是O(L).
2、基本性质
根节点不包含字符,除根节点外的每一个子节点都包含一个字符
从根节点到某一节点。路径上经过的字符连接起来,就是该节点对应的字符串
每个节点的所有子节点包含的字符都不相同
3、应用场景
典型应用是用于统计,排序和保存大量的字符串(不仅限于字符串),经常被搜索引擎系统用于文本词频统计。
4、优点
利用字符串的公共前缀来减少查询时间,最大限度的减少无谓的字符串比较,查询效率比哈希树高。
二、构建过程
1、节点定义
class TrieNode // 字典树节点 { private int num;// 有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数 private TrieNode[] son;// 所有的儿子节点 private boolean isEnd;// 是不是最后一个节点 private char val;// 节点的值 TrieNode() { num = 1; son = new TrieNode[SIZE]; isEnd = false; } }
2、构造函数
Trie() // 初始化字典树 { root = new TrieNode(); }
3、建立字典树
// 建立字典树 public void insert(String str) // 在字典树中插入一个单词 { if (str == null || str.length() == 0) { return; } TrieNode node = root; char[] letters = str.toCharArray();//将目标单词转换为字符数组 for (int i = 0, len = str.length(); i < len; i++) { int pos = letters[i] - 'a'; if (node.son[pos] == null) //如果当前节点的儿子节点中没有该字符,则构建一个TrieNode并复值该字符 { node.son[pos] = new TrieNode(); node.son[pos].val = letters[i]; } else //如果已经存在,则将由根至该儿子节点组成的字符串模式出现的次数+1 { node.son[pos].num++; } node = node.son[pos]; } node.isEnd = true; }
4、 查找是否完全匹配一个指定的字符串
// 在字典树中查找一个完全匹配的单词. public boolean has(String str) { if(str==null||str.length()==0) { return false; } TrieNode node=root; char[]letters=str.toCharArray(); for(int i=0,len=str.length(); i<len; i++) { int pos=letters[i]-'a'; if(node.son[pos]!=null) { node=node.son[pos]; } else { return false; } } //走到这一步,表明可能完全匹配,也可能部分匹配,如果最后一个字符节点为末端节点,则是完全匹配,否则是部分匹配 return node.isEnd; }
5、前序遍历字典树
// 前序遍历字典树. public void preTraverse(TrieNode node) { if(node!=null) { System.out.print(node.val+"-"); for(TrieNode child:node.son) { preTraverse(child); } } }
6、计算单词前缀的数量
// 计算单词前缀的数量 public int countPrefix(String prefix) { if(prefix==null||prefix.length()==0) { return-1; } TrieNode node=root; char[]letters=prefix.toCharArray(); for(int i=0,len=prefix.length(); i<len; i++) { int pos=letters[i]-'a'; if(node.son[pos]==null) { return 0; } else { node=node.son[pos]; } } return node.num; }
结果:
三、应用
(问题1)请你选择合适的数据结构,将所有的英文单词生成一个字典Dictionary?
(问题2)给定一个单词,判断这个单词是否在字典Dictionary中,如果在单词库中,输出这个单词出现总共出现的次数,否则输出NO?
package com.xj.test; import java.io.BufferedReader; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; public class Trie { private int SIZE = 26; private TrieNode root;// 字典树的根 class TrieNode // 字典树节点 { private int num;// 有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数 private TrieNode[] son;// 所有的儿子节点 private boolean isEnd;// 是不是最后一个节点 private char val;// 节点的值 TrieNode() { num = 1; son = new TrieNode[SIZE]; isEnd = false; } } Trie() // 初始化字典树 { root = new TrieNode(); } // 建立字典树 public void insert(String str) // 在字典树中插入一个单词 { if (str == null || str.length() == 0) { return; } TrieNode node = root; char[] letters = str.toCharArray();//将目标单词转换为字符数组 for (int i = 0, len = str.length(); i < len; i++) { int pos = letters[i] - 'a'; if (node.son[pos] == null) //如果当前节点的儿子节点中没有该字符,则构建一个TrieNode并复值该字符 { node.son[pos] = new TrieNode(); node.son[pos].val = letters[i]; } else //如果已经存在,则将由根至该儿子节点组成的字符串模式出现的次数+1 { node.son[pos].num++; } node = node.son[pos]; } node.isEnd = true; } // 计算单词前缀的数量 public int countPrefix(String prefix) { if(prefix==null||prefix.length()==0) { return-1; } TrieNode node=root; char[]letters=prefix.toCharArray(); for(int i=0,len=prefix.length(); i<len; i++) { int pos=letters[i]-'a'; if(node.son[pos]==null) { return 0; } else { node=node.son[pos]; } } return node.num; } // 打印指定前缀的单词 public String hasPrefix(String prefix) { if (prefix == null || prefix.length() == 0) { return null; } TrieNode node = root; char[] letters = prefix.toCharArray(); for (int i = 0, len = prefix.length(); i < len; i++) { int pos = letters[i] - 'a'; if (node.son[pos] == null) { return null; } else { node = node.son[pos]; } } preTraverse(node, prefix); return null; } // 遍历经过此节点的单词. public void preTraverse(TrieNode node, String prefix) { if (!node.isEnd) { for (TrieNode child : node.son) { if (child != null) { preTraverse(child, prefix + child.val); } } return; } System.out.println(prefix); } // 在字典树中查找一个完全匹配的单词. public boolean has(String str) { if(str==null||str.length()==0) { return false; } TrieNode node=root; char[]letters=str.toCharArray(); for(int i=0,len=str.length(); i<len; i++) { int pos=letters[i]-'a'; if(node.son[pos]!=null) { node=node.son[pos]; } else { return false; } } //走到这一步,表明可能完全匹配,可能部分匹配,如果最后一个字符节点为末端节点,则是完全匹配,否则是部分匹配 return node.isEnd; } // 前序遍历字典树. public void preTraverse(TrieNode node) { if(node!=null) { System.out.print(node.val+"-"); for(TrieNode child:node.son) { preTraverse(child); } } } public TrieNode getRoot() { return this.root; } public static void main(String[]args) throws IOException { Trie tree=new Trie(); String[] dictionaryData= {"hello","student","computer","sorry","acm","people","experienced","who","reminds","everyday","almost"}; //构建字典 for(String str:dictionaryData) { tree.insert(str); } String filePath="C:\\Users\\Administrator\\Desktop\\sourceFile.txt"; File file=new File(filePath); if(file.isFile() && file.exists()) { InputStreamReader read = new InputStreamReader(new FileInputStream(file)); BufferedReader bufferedReader = new BufferedReader(read); String lineTxt = null; Map<String,Integer> countMap=new HashMap<String,Integer>(); while((lineTxt = bufferedReader.readLine())!= null) { if(tree.has(lineTxt)) { if(countMap.containsKey(lineTxt)) { countMap.put(lineTxt, countMap.get(lineTxt)+1); } else { countMap.put(lineTxt, 1); } } else { System.out.println(lineTxt+"不在字典中!"); } } for(String s:countMap.keySet()) { System.out.println(s+"出现的次数"+countMap.get(s)); } read.close(); } } }
text文件内容:
结果:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。