专栏首页java 成神之路Trie Tree 实现中文分词器

Trie Tree 实现中文分词器

前言

继上一篇HashMap实现中文分词器后,对Trie Tree的好奇,又使用Trie Tree实现了下中文分词器。效率比HashMap实现的分词器更高。

Trie Tree 简介

Trie Tree,又称单词字典树、查找树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

性质

它有3个基本性质:

  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

Trie Tree 结构

Trie Tree

Trie Tree分词原理:

(1) 从根结点开始一次搜索,比如搜索【北京】; (2) 取得要查找关键词的第一个字符【北】,并根据该字符选择对应的子树并转到该子树继续进行检索; (3) 在相应的子树上,取得要查找关键词的第二个字符【京】,并进一步选择对应的子树进行检索。 (4) 迭代过程…… (5) 在直到判断树节点的isEnd节点为true则查找结束(最小匹配原则),然后发现【京】isEnd=true,则结束查找。

示例

下面用java简单实现

package cn.com.infcn.algorithm;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

/**
 * jijs
 * 正向最大匹配
 */
public class TrieTreeDemo {
    static class Node {
        //记录当前节点的字
        char c;
        //判断该字是否词语的末尾,如果是则为false
        boolean isEnd;
        //子节点
        List<Node> childList;
        
        public Node(char c) {
            super();
            this.c = c;
            isEnd = false;
            childList = new LinkedList<Node>();
        }
        
        //查找当前子节点中是否保护c的节点
        public Node findNode(char c){
            for(Node node : childList){
                if(node.c == c){
                    return node;
                }
            }
            
            return null;
        }
    }
    
    static class TrieTree{
        Node root = new Node(' ');
        
        //构建Trie Tree
        public void insert(String words){
            char[] arr = words.toCharArray();
            Node currentNode = root;
            for (char c : arr) {
                Node node = currentNode.findNode(c);
                //如果不存在该节点则添加
                if(node == null){
                    Node n = new Node(c);
                    currentNode.childList.add(n);
                    currentNode = n;
                }else{
                    currentNode = node;
                }
            }
            //在词的最后一个字节点标记为true
            currentNode.isEnd = true;
        }
        
        //判断Trie Tree中是否包含该词
        public boolean search(String word){
            char[] arr = word.toCharArray();
            Node currentNode = root;
            for (int i=0; i<arr.length; i++) {
                Node n = currentNode.findNode(arr[i]);
                if(n != null){
                    currentNode = n;
                    //判断是否为词的尾节点节点
                    if(n.isEnd){
                        if(n.c == arr[arr.length-1]){
                            return true;
                        }
                    }
                }
            }
            return false;
        }
        
        //最大匹配优先原则
        public Map<String, Integer> tokenizer(String words){
            char[] arr = words.toCharArray();
            Node currentNode = root;
            Map<String, Integer> map = new HashMap<String, Integer>();
            //记录Trie Tree 从root开始匹配的所有字
            StringBuilder sb = new StringBuilder();;
            //最后一次匹配到的词,最大匹配原则,可能会匹配到多个字,以最长的那个为准
            String word="";
            //记录记录最后一次匹配坐标
            int idx = 0;
            for (int i=0; i<arr.length; i++) {
                Node n = currentNode.findNode(arr[i]);
                if(n != null){
                    sb.append(n.c);
                    currentNode = n;
                    //匹配到词
                    if(n.isEnd){
                        //记录最后一次匹配的词
                        word = sb.toString();
                        //记录最后一次匹配坐标
                        idx = i;
                    }
                }else{
                    //判断word是否有值
                    if(word!=null && word.length()>0){
                        Integer num = map.get(word);
                        if(num==null){
                            map.put(word, 1);
                        }else{
                            map.put(word, num+1);
                        }
                        //i回退到最后匹配的坐标
                        i=idx;
                        //从root的开始匹配
                        currentNode = root;
                        //清空匹配到的词
                        word = null;
                        //清空当前路径匹配到的所有字
                        sb = new StringBuilder();
                    }
                }
                //已匹配到最后一位
                if(i==arr.length-1){
                    if(word!=null && word.length()>0){
                        Integer num = map.get(word);
                        if(num==null){
                            map.put(word, 1);
                        }else{
                            map.put(word, num+1);
                        }
                    }
                }
            }
            
            return map;
        }
    }

    public static void main(String[] args) {
        TrieTree tree = new TrieTree();
        tree.insert("北京");
        tree.insert("海淀区");
        tree.insert("中国");
        tree.insert("中国人民");
        tree.insert("中关村");
        
        String word = "中国";
        //查找该词是否存在 Trid Tree 中
        boolean flag = tree.search(word);
        if(flag){
            System.out.println("Trie Tree 中已经存在【"+word+"】");
        }else{
            System.out.println("Trie Tree 不包含【"+word+"】");
        }
        
        //分词
        Map<String, Integer> map = tree.tokenizer("中国人民,中国首都是北京,中关村在海淀区,中国北京天安门。中国人");
        for (Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey()+":"+entry.getValue());
        }
        
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • AbstractQueuedSynchronizer 源码分析

    java404
  • ReentrantLock 源码解析(JDK1.8)

    java404
  • Netty 之 FileRegion 文件传输

    Netty 传输文件的时候没有使用 ByteBuf 进行向 Channel 中写入数据,而使用的 FileRegion。下面通过示例了解下 FileRegion...

    java404
  • 程序中减少使用if语句的方法集锦

    大约十年前,我听说了反if的活动,觉得这个概念非常荒谬。如果不用if语句,又怎么能写出有用的程序呢?这简直太荒谬了。

    哲洛不闹
  • 学习心得:C语言实现链表的操作超详细

    今天将给大家讲述链表的学习心得。学习数据结构,毋庸置疑链表必须学好,后面的栈、队列、树、图都是以链表为基础的;链表的种类很多,有单链表、双链表、循环链表、非循环...

    诸葛青云
  • 大数据HDFS技术干货分享

    关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 1 HDFS前言 设计思想 分而治之...

    昱良
  • 用python记录运行pid,并在需要时

      我在跑爬虫程序的时候,由于爬虫程序的等待目标服务器返回数据的时间很长,而cpu占用很低,所以经常挂着代理一跑就跑好几百个。但是爬虫程序通常是写了死循环,或直...

    用户2398817
  • Java企业微信开发_Exception_02_java.security.InvalidKeyException: Illegal key size

    今天换了重新装了一个jdk,然后运行昨天还好好的企业微信工程,结果启动的时候就给我报了这么个错:

    shirayner
  • 运行jar命令提示:没有主清单属性或者找不到或无法加载主类

    文章如题:在JAVA中将class文件编译成jar文件包,运行提示没有主清单属性。这是怎么回事?

    浩Coding
  • Hello Flutter,船长初体验

    前几天 Google 发布了 flutter.cn 以及 release 了 Flutter 1.9 ,今天船长没忍住,尝试了下 Flutter。

    程序亦非猿

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动