字典树的实现和介绍

cheukyin 发布于2019-07-01 12:42 / 566人阅读

摘要：优化老代码的时候，用到了字典树。我用写了一个字典树。因为是多叉树结构，可能这两个单词，，需要一个结束的标识位。但是应该有相关的文本搜索算法和字典树相结合。如果字典树更新不频繁，比如地名，字典树是可以化，保存到中。

优化老代码的时候，用到了字典树。我用Java写了一个字典树。分享一下。

先说一下常见的引用场景，单词匹配，统计（敏感词检测，单词检测），还有输入提示等等。

下面是代码了
node节点代码

public class Node{
    private List nodeList = new ArrayList<>();
    private char word; //这里保存的一个字符
    private int isEnd = 0; //这里是一个结束标识

    public Node(char w){
        this.word = w;
    }

    public Node(){ }

    public List getNodeList() {
        return nodeList;
    }

    public void setNodeList(List nodeList) {
        this.nodeList = nodeList;
    }

    public char getWord() {
        return word;
    }

    public void setWord(char word) {
        this.word = word;
    }

    public int getIsEnd() {
        return isEnd;
    }

    public void setIsEnd(int isEnd) {
        this.isEnd = isEnd;
    }
}

Node节点重点就是保存的char和isEnd这个两个属性，这里我保存的是字符串，其实可以保存成utf8的编码，防止一些编码问题。
因为是多叉树结构，可能这两个单词 sad，saddy，需要一个结束的标识位。

添加节点代码

    public void addNode(List nodeList,char[] word){
        List temp = new ArrayList<>();
        //遍历单词
        for (int i=0;i < word.length; i++ ){
            //查看子节点
            for (int j = nodeList.size(); j >= 0; j--) {
                //有子节点并且字相同，则更新nodeList并且跳出循环，检查下一个字
                if (j > 0 && nodeList.get(j-1).getWord() == word[i]) {
                    nodeList = nodeList.get(j-1).getNodeList();
                    break;
                //如果子节点为零，则说明需要添加新节点    
                }else if(j == 0 ){
                    Node n = new Node(word[i]);
                    //判断是否达到单词结尾，添加标志位
                    if( nodeList.size() == 0 && (i == word.length -1)){
                        n.setIsEnd(1);
                    }
                    temp = n.getNodeList();
                    nodeList.add(n);
                    //nodeList赋值给新节点，结束循环
                    nodeList = temp;
                }
            }
        }
    }

这一段需要注意的一点是，我是用了List这个数据结构，这个地方可以优化为Map结构，Hash表的时间复杂度是O(1)。

搜索单词

public boolean searchNode(List nodeList,char[] word){
    for (int i=0;i < word.length; i++ ){
        for (int j = nodeList.size() - 1; j >= 0; j--) {
            if (nodeList.get(j).getWord() == word[i]) {
                //单词处于结尾，和有标志位，则直接返回
                if( (i == word.length -1) && nodeList.get(j).getIsEnd() == 1){
                    return true;
                }
                nodeList = nodeList.get(j).getNodeList();
                break;
            }
        }
    }

    return false;
}

搜索文本

  
public boolean searchText(List nodeList,char[] word){
    //记录头节点
    List head = nodeList;
    for (int i=0;i < word.length; i++ ){
        for (int j = nodeList.size() - 1; j >= 0; j--) {
            if (nodeList.get(j).getWord() == word[i]) {
            //搜索文本就不要判断单词是否处于结尾了，查到直接就返回结果
                if( nodeList.get(j).getIsEnd() == 1){
                    return true;
                }
                nodeList = nodeList.get(j).getNodeList();
                break;
            }
            //当节点没有子节点，并且程序运行到此，将nodeList复位到头节点
            if(j == 0){
                nodeList = head;
            }
        }
    }
    return false;
}

处理敏感词部分，或者相似功能应该做分词的处理。如果不做分词处理的，会出现错误，比如玛丽露A。往后再推一个单词。
我这里是一个字一个字去进行顺序查找的。但是应该有相关的文本搜索算法和字典树相结合。可以提高效率。

我这里实现的是O（m*n）上面也提到了可以优化到O（n），但是也比之前快了不少了。比如输入提示，比每一次查询数据库之类的要快很多。如果字典树更新不频繁，比如地名，字典树是可以json化，保存到Redis中。这样可以给其他语言去使用，而且比一次性查询数据库，之后再结构化，也是要快一点的。

如果还哪里写错了，或者有什么更好的优化建议，欢迎讨论。

云服务器 GPU云服务器 java菜单树的实现 c语言树的深度和节点 j2ee 数据字典实现介绍腾讯云服务器注册和配置流程

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31298.html

字典树的实现和介绍

摘要：优化老代码的时候，用到了字典树。我用写了一个字典树。因为是多叉树结构，可能这两个单词，，需要一个结束的标识位。但是应该有相关的文本搜索算法和字典树相结合。如果字典树更新不频繁，比如地名，字典树是可以化，保存到中。优化老代码的时候，用到了字典树。我用Java写了一个字典树。分享一下。先说一下常见的引用场景，单词匹配，统计（敏感词检测，单词检测），还有输入提示等等。下面是代码了nod...

EddieChan 2019-08-16 16:56 评论0 收藏0
简单字典树实现

摘要：查找操作查询指定单词是否在字典树中。将单词标记为当前单词，将根节点标记为当前节点，执行操作当前单词为空，那么返回，即字典树中存在该单词。字典树的简单实现插入操作查找操作删除操作具体实现放在上，可以在这里找到。原文地址字典树介绍我们经常会在网上输入一些单词，一般情况下，当我们输入几个字母时，输入框中会自动弹出以这些字母开头的单词供我们选择，用户体验非常好。不过这种自动提示功能到底...

MonoLog 2019-07-31 11:32 评论0 收藏0
大展身手的字典树

摘要：原文地址在简单字典树的实现一文中，我们以单词输入自动提示为引子，简单介绍了字典树的实现。前缀匹配本文讲述前缀匹配的字典树实现方案。在简单字典树的实现一文中，我们已经实现了字典树的基本操作，这里只需要再加上一个前缀匹配方法即可。原文地址在简单字典树(Trie)的实现一文中，我们以单词输入自动提示为引子，简单介绍了字典树的实现。那么，字典树到底可以用于哪些场合呢？前缀匹配：给定字典...

Anchorer 2019-07-24 17:36 评论0 收藏0
最小生成树原理及Kruskal算法的js实现

摘要：生成树和最小生成树的概念设图连通，则生成树包含图中的所有节点，及条边的连通图，一个图的生成树可以有多颗最小生成树最小权重生成树，在生成树的概念上加一个限制条件，即生成树的所有边的权值总和最小的树，最小生成树也可以有多颗求解最小生成树的通用 1. 生成树和最小生成树的概念设图G(V,E)连通，则生成树：包含图G(V,E)中的所有节点，及|V|-1条边的连通图，一个图的生成树可以有多颗最...

scq000 2019-08-21 18:30 评论0 收藏0
一种字典树结构的高效实现

摘要：另一种高效实现下面介绍另一种实现，它将字典树用数组存储起来，不仅压缩了数组，而且不降低查找效率。这就是双数组字典树。字典树的心得体会常见的字典树实现方法 class Node{ uint node ; uint[] next; }; 或者类似如下结构 class Node{ uint node; map n...

kycool 2019-08-14 17:44 评论0 收藏0