中英文字典树_字典树详解

中英文字典树_字典树详解英文字典树英文字典树的结构图是这样的。按照树型结构存储字符串,每个结点存一个字符,自顶向下做标记的就是词的词尾,比如,app,apple,application,abstract,absorb,block,black,blake…等等介绍一下英文字典树的结点数据结构:1.词频int型变量记录词频2.结点型数组,长度26下标对应0-25(也…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

英文字典树

    英文字典树的结构图是这样的。按照树型结构存储字符串,每个结点存一个字符,自顶向下做标记的就是词的词尾,比如,app,apple,application,abstract,absorb,block,black,blake… 等等

    介绍一下英文字典树的结点数据结构:

        1.词频 int型变量记录词频

        2.结点型数组,长度26下标对应0 – 25(也就是当前字符 ‘ ? ‘ –  ‘ a ‘ 用字符ASCII码做运算,值域 0 – 25)

        3.flag标记,当前结点是否构成单词        

        4.结点值        

    中英文字典树_字典树详解

中文字典树:

     结构和英文字典树相似,但是因为中文的原因,我们没有使用数组,用字符+-的方式来计算显然不行了。所以这里我用的hashmap存的下一位的孩子们。

      看一下中文字典树的图:

       中英文字典树_字典树详解

    数据结构:

        public Integer frequency;    //词频
        public Boolean isWords;      //是否是词
        public Character values;        //值
        public HashMap<String,TrieNode> childNodes ;    //孩子们

   插入:

          拿到一个词,拆开,从词的第一个字开始找,找到了就拿第二个字继续往下找,找不到拿当前做比较的字开辟结点。

          插入时注意好维护每个结点的词频,而且还要看是否是最后一个字,插入最后一个字的时候要标记当前字为词结点。

    查找:

          也就是拿词拆开,挨个比较,找到了就输出并返回true。

    删除词:

          在找词的过程中把孩子 > 1的结点压入栈,找到词后把栈顶元素和当前词相关的元素抹去就ok了。

中英文字典树_字典树详解  中英文字典树_字典树详解

中文字典树源代码:

package com.cccl.datastruct.Tree.tiretree;

import com.cccl.datastruct.queue.MyLinkedQueue;

import java.util.*;

public class Trie {

    private static Integer[] level = { 1,0,0,0, 0,0,0,0 }; //trie树 词应该不会超过8的长度   树也最高也就五六层  词语

    private TrieNode trieRoot;
    public Trie(){
        trieRoot = new TrieNode();
        trieRoot.frequency = 0;
    }

    /**
     * 插入中文词组
     * @param data
     * @return
     */
    public Boolean insert(String data){
        ArrayList<String> arrays =  toStringArrays(data);
        TrieNode point = trieRoot;
        TrieNode nextChild = null;
        String nowArraysStr = "";
        for (int i = 0; i < arrays.size(); i++) {
            point.frequency++;
            nowArraysStr = arrays.get(i);
            nextChild = point.childNodes.get(nowArraysStr);
            if (nextChild == null){
                TrieNode addTire = new TrieNode(nowArraysStr.charAt(0));
                if (i == arrays.size()-1){
                    addTire.isWords = true;
                    addTire.frequency = 1;
                    point.childNodes.put(nowArraysStr,addTire);
                    level[i+1]++;
                    break;
                }
                point.childNodes.put(nowArraysStr,addTire);
                level[i+1]++;
                point = addTire;
            }else {
                point = nextChild;
            }
        }
        return true;
    }

    /**
     * 查询词组
     * @param data
     * @return
     */
    public Boolean searchWords(String data){
        ArrayList<String> arrays =  toStringArrays(data);
        TrieNode point = trieRoot;
        TrieNode nextChild = null;
        String s = "";
        for (int i = 0; i < arrays.size(); i++) {
            nextChild = point.childNodes.get(arrays.get(i));
            if (nextChild == null){
                return false;
            }else {
                point = nextChild;
                showPointInfo(point);
                s += point.values;
            }
        }
        System.out.println(s);
        return true;
    }


    /**
     * 查询前缀词频
     * @param data
     * @return
     */
    public boolean searchPreWord(String data){
        ArrayList<String> arrays =  toStringArrays(data);
        TrieNode point = trieRoot;
        TrieNode nextChild = null;
        String s = "";
        for (int i = 0; i < arrays.size(); i++) {
            nextChild = point.childNodes.get(arrays.get(i));
            if (nextChild == null){
                System.out.println("没有此前缀!");
                return false;
            }else {
                point = nextChild;

            }
        }
        showPointInfo(point);
        return true;
    }

    /**
     * 层序遍历trie树
     */
    public void showTrieTree(){
        TrieNode point = trieRoot;
        MyLinkedQueue<TrieNode> queue = new MyLinkedQueue<TrieNode>();
        queue.enQueue(point);
        Integer lev = 0;
        Integer count = 0;
        while (queue.getCount()>0){
            TrieNode trieNode = queue.deQueue();
            Collection<TrieNode> childs = trieNode.childNodes.values();
            Iterator<TrieNode> iterator = childs.iterator();
            while (iterator.hasNext()){
                queue.enQueue(iterator.next());
            }
            System.out.print(trieNode.values + "  ");
            count++;
            if (count == level[lev]){
                System.out.println();
                lev++;
                count = 0;
            }
        }
    }

    /**
     * 主函数
     * @param args
     */
    public static void main(String[] args) {
        String[] strings = {"天天向上","天人合一","天天学习","我是大神","快马加鞭"};
        Trie trie = new Trie();
        for (String s:
                strings) {
            trie.insert(s);
        }
        //  trie.searchWords("天天向上");
        // trie.searchPreWord("天天");
        trie.showTrieTree();
    }

    public class TrieNode {

        public TrieNode(){
            childNodes = new HashMap<String,TrieNode>(8);
            isWords = false;
            frequency = 0;
            values = '根';
        }
        public TrieNode(Character data) {
            childNodes = new HashMap<String,TrieNode>(8);
            isWords = false;
            frequency = 0;
            values = data;
        }

        public Integer frequency;
        public Boolean isWords;
        public Character values;
        public HashMap<String,TrieNode> childNodes ;

        @Override
        public String toString() {
            return "TrieNode{" +
                    "frequency=" + frequency +
                    ", isWords=" + isWords +
                    ", values=" + values +
                    ", childNodes=" + childNodes.toString() +
                    '}'+'\n';
        }
    }

    private void showPointInfo(TrieNode point){
        System.out.println("当前  结点值:" + point.values);
        System.out.println("当前结点词频:" + point.frequency);
        System.out.print("当前结点孩子:");
        Set<String> chs = point.childNodes.keySet();
        Iterator<String> iterator = chs.iterator();
        while (iterator.hasNext()){
            System.out.print(" " + iterator.next());
        }
        System.out.println();
    }

    private static ArrayList<String> toStringArrays(String data){
        ArrayList<String> result = new ArrayList<String>(data.length());
        for (int i = 0; i < data.length(); i++) {
            result.add("" + data.charAt(i));
        }
        return result;
    }

    @Override
    public String toString() {
        return "Trie{" +
                "trieRoot=" + trieRoot.toString() +
                '}';
    }
}

因为层序遍历用到了队列,队列代码:

package com.cccl.datastruct.queue;

/**
 * Created by 小H on 2018/3/21.
 */
public class MyLinkedQueue<T> {


    public Node<T> front = null;
    public Node<T> rear = null;
    private Integer count = 0;
    public Integer getCount() {
        return count;
    }
    public MyLinkedQueue(){
        initQueue();
    }

    /**
     * 初始化队列
     */
    private void initQueue(){
        front = new Node<T>();
        rear = front;
    }

    /**
     * 销毁队列
     */
    public void destroyQueue(){
        front = null;
        rear = null;
    }

    /**
     * 入队
     * @param data
     * @return
     */
    public boolean enQueue(T data){
        try {
            Node<T> node = new Node<T>(data);
            node.pre = rear;
            rear.next = node;
            rear = rear.next;
            count++;
            return true;
        }catch (Exception e){
            e.printStackTrace();
            return false;
        }
    }

    /**
     * 出队
     * @return
     */
    public T deQueue(){
        try {
            if(front == rear) {
                System.out.println("没有元素了,不能出队了");
                return null;
            }
            front = front.next;
            count--;
            return front.data;
        }catch (Exception e){
            e.printStackTrace();
            return null;
        }
    }

    /**
     * 返回队头元素
     * @return
     */
    public T getQueue(){
        try {
            if(front == rear) {
                System.out.println("没有元素了,不能找到队头元素了");
                return null;
            }
            return front.next.data;
        }catch (Exception e){
            e.printStackTrace();
            return null;
        }
    }

    private static class Node<T>{
        public Node<T> pre = null;
        public Node<T> next = null;
        public T data = null;
        public Node(){}
        public Node(T d){
            data = d;
        }
    }



}

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/196549.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • Java回调机制详解[通俗易懂]

    Java回调机制详解[通俗易懂]网上关于Java回调的文章一抓一大把,但是看完总是云里雾里,不知所云,特别是看到抓取别人的代码走两步时,总是现眼。于是自己决定写一篇关于Java机制的文章,以方便大家和自己更深入的学习Java回调机制。

    2022年6月17日
    34
  • Django(42)DRF安装与使用

    Django(42)DRF安装与使用DRF介绍DRF是DjangoRestFramework单词的简写,是在Django框架中实现RestfulAPI的一个插件,使用他可以非常方便的实现接口数据的返回。Django中也可以使用J

    2022年7月31日
    6
  • 博客日记-澄清自己「建议收藏」

    博客日记-澄清自己「建议收藏」关于我的博客https://blog.csdn.net/csdnhsh/article/details/91410753#comments_17668907,这是一些csdn朋友对我的误解,说我的文章不是原创,我不得已出来澄清下:那个jt_sinlio说的其它文章,还有哪个账号已失效的留言,说要我拿出证据,我想了想,为了csdn的声誉,就简约证明下自己。哪个jt_sinlio说的其它网站的文章,打开一看发表时间是2013年8月29日19:28分,比我自己大号发表过的,现在设置私密的要晚几个

    2022年6月3日
    27
  • 开源报表工具 java_java生成报表

    开源报表工具 java_java生成报表BestOpenSourceReportingTools一文列出目前比较好的几种开源报表工具1.BIRTProjectBIRT是基于Eclipse的报表系统,很有竞争力。2.Pentaho侧重于从各种现有系统输出创建产生丰富复杂的报表内容。3.OpenRPTxTupleERPEditions的一部分,侧重ERP领域的报表4.OpenReports基于浏览器参数驱动动态报…

    2022年10月20日
    3
  • java中 +=和+的区别[通俗易懂]

    java中 +=和+的区别[通俗易懂]java中+=的意义包含两部分,一是"+",就是通常所说的直接相加,二是改变结果的类型,将计算结果的类型转换为"+=符号左边的类型。比如:shrots=1;s+=1这个语句其实就是s=(short)(s+1)…

    2022年7月8日
    16
  • Oracle数据库优化的经验总结建议收藏

    个人理解,数据库性能最关键的因素在于IO,因为操作内存是快速的,但是读写磁盘是速度很慢的,优化数据库最关键的问题在于减少磁盘的IO,就个人理解应该分为物理的和逻辑的优化,物理的是指oracle产品

    2021年12月20日
    37

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号