文档章节

关于Trie树的学习--英文字典树的建立和获得前缀次数

小手冰凉丶
 小手冰凉丶
发布于 2016/10/28 17:08
字数 522
阅读 8
收藏 0

根节点为root

private Vertex root = new Vertex();

节点类:Vertex 

节点包含3个属性:

        protected int words; // 单词个数  到该节点为止,可以组合出单词的个数 
        protected int prefixes; // 前缀个数  到该节点位置,可以组合出符合该前缀单词的个数
        protected Vertex[] edges; // 子节点  

新建英文字典树:添加单词

root 节点:

先判定word的length 是否未0 ,0 代表解表截止 words++;不需要添加子节点,前缀个数也无需增加

至多可以有26个节点 0 25 第一个单词的第一位的char(不区分大小写)-a的hash就是就是该字符的index  edges[index]

    private void addWord(Vertex vertex, String word) { //添加单词到目录树,root , word
        if (word.length() == 0) { // if all characters of the word has been
                                    // added
            vertex.words++;
        } else {
            vertex.prefixes++;//前缀个数
            char c = word.charAt(0);
            c = Character.toLowerCase(c);//无视大小写
            int index = c - 'a';获得该节点的index
            if (vertex.edges[index] == null) { // if the edge does NOT exist  新建一个  
                vertex.edges[index] = new Vertex();
            }
 
            addWord(vertex.edges[index], word.substring(1)); // go the the next继续添加下个字符的节点
                                                                // character
        }
    }

添加完所有单词 字典树已经建好了

 

那么就是查找符合该前缀的单词数了!!

 
    /**
     * 计算指定前缀单词的个数
     * 
     * @param prefix
     * @return
     */
    public int countPrefixes(String prefix) {//输入要查找的单词
        return countPrefixes(root, prefix);  //从根节点开始查找
    }
 
    private int countPrefixes(Vertex vertex, String prefixSegment) {
        if (prefixSegment.length() == 0) { // 输入的单词未空的话直接返回所有的root下的单词数 

    //或者已经到这个单词的结尾时 可以返回该节点下的子节点个数 也就是符合该前缀的单词数
                                            
            return vertex.prefixes;
        }
 
        char c = prefixSegment.charAt(0); //获得第一个字符的hash
        int index = c - 'a';//获得第一个字符的index
        if (vertex.edges[index] == null) { // 如果该节点下无子节点 直接返回0
            return 0;   //第一执行这个方法会进入 
        } else {
 
            return countPrefixes(vertex.edges[index],
                    prefixSegment.substring(1)); //递归
 
        }
 
    }
 这样你就可以得到符合该前缀的所有单词的个数啦!!

 

 

 

© 著作权归作者所有

小手冰凉丶
粉丝 5
博文 60
码字总数 17316
作品 0
合肥
程序员
私信 提问
Python: Trie树实现字典排序

一般语言都提供了按字典排序的API,比如跟微信公众平台对接时就需要用到字典排序。按字典排序有很多种算法,最容易想到的就是字符串搜索的方式,但这种方式实现起来很麻烦,性能也不太好。T...

陈亦
2014/02/18
0
4
给一个字符串S和一个字符串数组T(T中的字符串要比S短许多),设计一个算法, 在字符串S中查找T中的字符串

给一个字符串S和一个字符串数组T(T中的字符串要比S短许多),设计一个算法, 在字符串S中查找T中的字符串。 解答 字符串的多模式匹配问题。 我们把S称为目标串,T中的字符串称为模式串。设目标...

一贱书生
2016/11/28
43
0
【从蛋壳到满天飞】JS 数据结构解析和算法实现-Trie字典树

前言 【从蛋壳到满天飞】JS 数据结构解析和算法实现,全部文章大概的内容如下: Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜...

哎哟迪奥
03/26
0
0
Trie(字典树)解析及其在编程竞赛中的典型应用举例

摘要:   本文主要讲解了Trie的基本思想和原理,实现了几种常见的Trie构造方法,着重讲解Trie在编程竞赛中的一些典型应用。 什么是Trie? 如何构建一个Trie? Trie在编程竞赛中的典型应用有...

Reqaw
2018/08/04
0
0
JavaScript: 实现简单的中文分词

中文分词在大数据横行的今天是越来越有用武之地了。它不仅被广泛用于专业的中文搜索引擎中,而且在关键词屏蔽、黑白名单以及文本相似度等方面也能大显身手。中文分词最简单也最常用的方式是基...

陈亦
2014/02/21
0
2

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud中Hystrix 线程隔离导致ThreadLocal数据丢失

在Spring Cloud中我们用Hystrix来实现断路器,Zuul中默认是用信号量(Hystrix默认是线程)来进行隔离的,我们可以通过配置使用线程方式隔离。 在使用线程隔离的时候,有个问题是必须要解决的...

xiaomin0322
39分钟前
2
0
使用 Jenkins + Ansible 实现 Spring Boot 自动化部署101

本文首发于:Jenkins 中文社区 本文要点: 设计一条 Spring Boot 最基本的流水线:包括构建、制品上传、部署。 使用 Docker 容器运行构建逻辑。 自动化整个实验环境:包括 Jenkins 的配置,J...

Jenkins中文社区
44分钟前
2
0
springcloud配置中心和消息总线,学习,记录其中的问题

改造配置中心的客户端,接入消息总线 1.增加pom文件的引用 <?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/20......

夜中孤影
57分钟前
3
0
gzip压缩

tar -zcvf gz包路径 被压缩的路径 tar -zcvf /home/xxx/test.tar.gz hello gz包的路径可以是 完整的也可以相对 , 被压缩的路径 不要全路径 不然压缩包里也会有全路径...

shzwork
今天
3
0
rancher-1

部署rancher 官方快速部署 https://www.cnrancher.com/quick-start/ 部署命令 mkdir /data/rancher -p# 建立存放rancher数据的目录sudo docker run -d --restart=unless-stopped -v /dat......

以谁为师
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部