Trie树的简单实现

2018-09-18.jpg

Trie树:
(来自百度百科)：
在计算机科学中，Trie，又称字典树、单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

package com.lhsjohn.spider.trietest;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

/**
 * Trie树,这里用来统计、排序和保存大量的字符串
 * 
 * @author lihuashuo
 *
 */
public class Trie {
    private final 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 countPrefic(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';
            char tmp =letters[i];
            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 Exception {
        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="F:\\Study\\newRecom\\test.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();
          
          
      
      }
        
    }
    
    
}

作者:lhsjohn 转载请注明出处.