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

中英文字典树_字典树详解英文字典树英文字典树的结构图是这样的。按照树型结构存储字符串,每个结点存一个字符,自顶向下做标记的就是词的词尾,比如,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)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • linux视频教程哪个最好_最好的Linux教程[通俗易懂]

    linux视频教程哪个最好_最好的Linux教程[通俗易懂]linux视频教程哪个最好Linuxisanamewhichbroadlydenotesafamilyoffreeandopen-sourcesoftwareoperatingsystemdistributionsbuiltaroundtheLinuxkernel.Linux的名称广泛地表示围绕Linux内核构建的一系列免费和开源软件操作系统发行版。…

    2022年6月5日
    38
  • KETTLE 使用教程

    KETTLE 使用教程Kettle的建立数据库连接、使用kettle进行简单的全量对比插入更新:kettle会自动对比用户设置的对比字段,若目标表不存在该字段,则新插入该条记录。若存在,则更新。Kettle简介:Kettle是一款国外开源的ETL工具,纯java编写,可以在Window、Linux、Unix上运行,数据抽取高效稳定。Kettle中文名称叫水壶,该项目的主程序员MATT希望把各种数据放到一个…

    2022年5月10日
    48
  • ios越狱教程14.3_ios14.4.2越狱工具

    ios越狱教程14.3_ios14.4.2越狱工具4.2.1完全越狱图文教程 . 如何用Cydia安装程序   Cydia“源安装”方式安装程序   Cydia“搜索安装”方式安装程序   Cydia“分类安装”方式安装程序   如何卸载用Cydia安装的程序   如何更新用Cydia安装的程序

    2022年9月20日
    2
  • 目前还存活的多个电驴下载站点!电驴达人收藏[通俗易懂]

    目前还存活的多个电驴下载站点!电驴达人收藏[通俗易懂]目前还存活的多个电驴下载站点!电驴达人收藏(2011更新) 0、http://www.emule-project.net/这个不用说了,emule官方,没有它就没有下面的所有一切,德国人开的。只提供官方版emule软件,没有资源下载。秉承理念“eMule是完全免费的,它也决不包含广告软件、间谍和流氓软件。我们之所以创造eMule是为了快乐和知识,而不…

    2022年7月15日
    55
  • redis可视化客户端工具TreeNMS

    redis可视化客户端工具TreeNMS

    2021年11月3日
    58
  • 【J2EE】13个规范

    【J2EE】13个规范【J2EE】13个规范

    2022年4月24日
    42

发表回复

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

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