双数组Trie树(DoubleArrayTrie)Java实现

2024-06-16 13:48

本文主要是介绍双数组Trie树(DoubleArrayTrie)Java实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原文地址:

http://www.hankcs.com/program/java/%E5%8F%8C%E6%95%B0%E7%BB%84trie%E6%A0%91doublearraytriejava%E5%AE%9E%E7%8E%B0.html

双数组Trie树(DoubleArrayTrie)是一种空间复杂度低的Trie树,应用于字符区间大的语言(如中文、日文等)分词领域。

双数组Trie (Double-Array Trie)结构由日本人JUN-ICHI AOE于1989年提出的,是Trie结构的压缩形式,仅用两个线性数组来表示Trie树,该结构有效结合了数字搜索树(Digital Search Tree)检索时间高效的特点和链式表示的Trie空间结构紧凑的特点。双数组Trie的本质是一个确定有限状态自动机(DFA),每个节点代表自动机的一个状态,根据变量不同,进行状态转移,当到达结束状态或无法转移时,完成一次查询操作。在双数组所有键中包含的字符之间的联系都是通过简单的数学加法运算表示,不仅提高了检索速度,而且省去了链式结构中使用的大量指针,节省了存储空间。

——《基于双数组Trie树算法的字典改进和实现》

我看了几篇论文,发现中文里也就上面这篇质量最好,英文当属这篇双数组Trie的一种实现。不过我并不打算按论文的腔调摘抄理论,而是准备借助开源的 darts-java 写点代码分析与笔记,如果能帮到你,实属意外。

darts-java 是对 Taku Kudo 桑的 C++ 版 Double Array Trie 的 Java 移植,代码精简,只有一个Java文件,十分优美。

写一段测试代码

package com.hankcs;import darts.DoubleArrayTrie;import java.io.*;
import java.util.*;/*** @author hankcs*/
public class Main
{public static void main(String[] args) throws IOException{BufferedReader reader = new BufferedReader(new FileReader("./data/small.dic"));String line;List<String> words = new ArrayList<String>();Set<Character> charset = new HashSet<Character>();while ((line = reader.readLine()) != null){words.add(line);// 制作一份码表debugfor (char c : line.toCharArray()){charset.add(c);}}reader.close();// 这个字典如果要加入新词必须按字典序,参考下面的代码
//        Collections.sort(words);
//        BufferedWriter writer = new BufferedWriter(new FileWriter("./data/sorted.dic", false));
//        for (String w : words)
//        {
//            writer.write(w);
//            writer.newLine();
//        }System.out.println("字典词条:" + words.size());{String infoCharsetValue = "";String infoCharsetCode = "";for (Character c : charset){infoCharsetValue += c.charValue() + "    ";infoCharsetCode += (int)c.charValue() + " ";}infoCharsetValue += '\n';infoCharsetCode += '\n';System.out.print(infoCharsetValue);System.out.print(infoCharsetCode);}DoubleArrayTrie dat = new DoubleArrayTrie();System.out.println("是否错误: " + dat.build(words));System.out.println(dat);List<Integer> integerList = dat.commonPrefixSearch("一举成名天下知");for (int index : integerList){System.out.println(words.get(index));}}
}


其中small.dic是一个微型的词典:

一举
一举一动
一举成名
一举成名天下知
万能
万能胶

输出:

字典词条:6
胶    名    动    知    下    成    举    一    能    天    万    
33014 21517 21160 30693 19979 25104 20030 19968 33021 22825 19975 
是否错误: 0
一举
一举成名
一举成名天下知

Trie树的构造与双数组的构造

双数组Trie树归根结底还是属于Trie树,所以免不了有一颗树的构造过程。不过这棵树并没有保存下来,而是边构造树边维护双数组,双数组的信息足以表示整棵树。比如对于上面的例子,首先建立一个空的root节点:

Node{code=0, depth=0, left=0, right=6}

其中code指的是字符的编码,在Java中是双字节,depth是深度,left及right表示这个节点在字典中的索引范围。

比如:

然后按照字典序插入所有的字串节点:

其中绿色节点为空字符,代表从根节点到此节点的路径上的所有节点构成一个词,整个的构建顺序是:

在darts-java中,使用了两个数组base和check来维护Trie树,它们的下标以及值都代表着一个确定的状态。base储存当前的状态以供状态转移使用,check验证字串是否由同一个状态转移而来并且当check为负的时候代表字串结束。(PS 双数组Tire树的具体实现有多种,有的实现将base为负作为状态的结束,大同小异。)

假定有字符串状态s,当前字符串状态为t,假定t加了一个字符c就等于状态tc,加了一个字符x等于状态tx,那么有

base[t] + c = base[tc]

base[t] + x = base[tx]

check[tc] = check[tx]

可见,在单词“一举一动”中,虽然有两个“一”,但它们的前一个状态不同,所以对应的状态分别为“”和“一举”,在base数组中的下标不一样。

在每个节点插入的过程中会修改这两个数组,具体说来:

1、初始化root节点base[0] = 1; check[0] = 0;

2、对于每一群兄弟节点,寻找一个begin值使得check[begin + a1…an]  == 0,也就是找到了n个空闲空间,a1…an是siblings中的n个节点对应的code。

      int pos = siblings.get(0).code;while (true){pos++;begin = pos - siblings.get(0).code; // 当前位置离第一个兄弟节点的距离……}

3、然后将这群兄弟节点的check设为check[begin + a1…an] = begin;很显然,叶子节点i的check[i]的值一定等于i,因为它是兄弟节点中的第一个,并且它的code为0。

check[begin + siblings.get(i).code] = begin;

4、接着对每个兄弟节点,如果它没有孩子,也就是上图除root外的绿色节点(叶子节点),令其base为负值;否则为该节点的子节点的插入位置(也就是begin值),同时插入子节点(迭代跳转到步骤2)

    if (fetch(siblings.get(i), new_siblings) == 0)  // 无子节点,也就是叶子节点,代表一个词的终止且不为其他词的前缀{base[begin + siblings.get(i).code] = -siblings.get(i).left - 1;……}else{int h = insert(new_siblings);   // dfsbase[begin + siblings.get(i).code] = h;}

这里给出这个例子的base check值以及码表,下表中×代表空

码表:胶    名    动    知    下    成    举    一    能    天    万    
33014 21517 21160 30693 19979 25104 20030 19968 33021 22825 19975 DoubleArrayTrie{
char =      ×    一    万     ×    举     ×    动     ×     下    名    ×    知      ×     ×    能    一    天    成    胶
i    =      0 19970 19977 20032 20033 21162 21164 21519 21520 21522 30695 30699 33023 33024 33028 40001 44345 45137 66038
base =      1     2     6    -1 20032    -2 21162    -3     5 21519    -4 30695    -5    -6 33023     3  1540     4 33024
check=      0     1     1 20032     2 21162     3 21519  1540     4 30695     5 33023 33024     6 20032 21519 20032 33023
size=66039, allocSize=2097152, key=[一举, 一举一动, 一举成名, 一举成名天下知, 万能, 万能胶], keySize=6, progress=6, nextCheckPos=33024, error_=0}

前缀查询

定义当前状态p = base[0] = 1。按照字符串char的顺序walk:

如果base[p] == check[base[p]] && base[base[p]] < 0则查到一个词;

然后状态转移,增加一个字符  p = base[char[i-1]] + char[i] + 1 。加1是为了与null节点区分开。

如果转移后base[char[i-1]] == check[base[char[i-1]] + char[i] + 1],那么下次p就从base[base[char[i-1]] + char[i] + 1]开始。

结合例子看可能更清楚:

字典词条:6
胶    名    动    知    下    成    举    一    能    天    万    
33014 21517 21160 30693 19979 25104 20030 19968 33021 22825 19975 
是否错误: 0
DoubleArrayTrie{
char =     ×    一    万    ×    举    ×    动    ×    下    名    ×    知    ×    ×    能    一    天    成    胶
i    =      0 19970 19977 20032 20033 21162 21164 21519 21520 21522 30695 30699 33023 33024 33028 40001 44345 45137 66038
base =      1     2     6    -1 20032    -2 21162    -3     5 21519    -4 30695    -5    -6 33023     3  1540     4 33024
check=      0     1     1 20032     2 21162     3 21519  1540     4 30695     5 33023 33024     6 20032 21519 20032 33023
size=66039, allocSize=2097152, key=null, keySize=6, progress=6, nextCheckPos=33024, error_=0}i       =      0     0     1     1     2     2     3     3     4     4     5     5     6     6    循环退出
b       =      1     1     2     2 20032 20032     4     4 21519 21519  1540  1540     5     5    30695p       =      1 19970     2 20033 20032 45137     4 21522 21519 44345  1540 21520     5 30699    30695
base[p] =      1     2     0 20032    -1     4     0 21519    -3  1540     0     5     0 30695    -4
check[p]=      0     1     0     2 20032 20032     0     4 21519 21519     0  1540     0     5    30695
一举
一举成名
一举成名天下知


稍微解释下

初始空 base[0] = 1, p = 1;

转移 p = base[0] + {char[一] = 19968} + 1 = 1 + 19968 + 1 = 19970,                检查base[19970]!=0说明有“一”这个字符。

 而  base[base[19970]] = base[2] = 0 说明没遇到词尾

转移 p = base[19970] + {char[举] = 20030} + 1 = 2 + 20030 + 1 = 20033,            检查base[20033]!=0说明有“举”这个字符。

 而  base[base[20033]] = base[20032] = -1 && base[20033] == check[20032] 说明遇到一个词尾,即查出“一举”

转移 p = base[20033] + {char[成] = 25104} + 1 = 20032 + 25104+ 1 = 45137,         检查base[45137]!=0说明有“成”这个字符。

……

基于双数组Trie树的Aho Corasick自动机

双数组Trie树能高速O(n)完成单串匹配,并且内存消耗可控,然而软肋在于多模式匹配,如果要匹配多个模式串,必须先实现前缀查询,然后频繁截取文本后缀才可多匹配,这样一份文本要回退扫描多遍,性能极低。

AC自动机能高速完成多模式匹配,然而具体实现聪明与否决定最终性能高低。大部分实现都是一个Map<Character, State>了事,无论是TreeMap的对数复杂度,还是HashMap的巨额空间复杂度与哈希函数的性能消耗,都会降低整体性能。

如果能用双数组Trie树表达AC自动机,就能集合两者的优点,得到一种近乎完美的数据结构。具体实现请参考《Aho Corasick自动机结合DoubleArrayTrie极速多模式匹配》。

这篇关于双数组Trie树(DoubleArrayTrie)Java实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1066620

相关文章

java使用protobuf-maven-plugin的插件编译proto文件详解

《java使用protobuf-maven-plugin的插件编译proto文件详解》:本文主要介绍java使用protobuf-maven-plugin的插件编译proto文件,具有很好的参考价... 目录protobuf文件作为数据传输和存储的协议主要介绍在Java使用maven编译proto文件的插件

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

Javaee多线程之进程和线程之间的区别和联系(最新整理)

《Javaee多线程之进程和线程之间的区别和联系(最新整理)》进程是资源分配单位,线程是调度执行单位,共享资源更高效,创建线程五种方式:继承Thread、Runnable接口、匿名类、lambda,r... 目录进程和线程进程线程进程和线程的区别创建线程的五种写法继承Thread,重写run实现Runnab

Java 方法重载Overload常见误区及注意事项

《Java方法重载Overload常见误区及注意事项》Java方法重载允许同一类中同名方法通过参数类型、数量、顺序差异实现功能扩展,提升代码灵活性,核心条件为参数列表不同,不涉及返回类型、访问修饰符... 目录Java 方法重载(Overload)详解一、方法重载的核心条件二、构成方法重载的具体情况三、不构

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys

SpringBoot线程池配置使用示例详解

《SpringBoot线程池配置使用示例详解》SpringBoot集成@Async注解,支持线程池参数配置(核心数、队列容量、拒绝策略等)及生命周期管理,结合监控与任务装饰器,提升异步处理效率与系统... 目录一、核心特性二、添加依赖三、参数详解四、配置线程池五、应用实践代码说明拒绝策略(Rejected

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注