热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

双数组TRIE树原理

原文名称:AnEfficientDigitalSearchAlgorithmbyUsingaDouble-ArrayStructure作者:JUN-IC

 



原文名称:

An Efficient Digital Search Algorithm by Using a Double-Array Structure

作者:

JUN-ICHI AOE

译文:

使用双数组结构的一个高效的Digital Search算法



摘要:

本文介绍了一种新的内部(内部排序的内部,也就是在内存里)数组结构的digital search算法,叫做双数组,结合了数组存取的快速和链式存储的压缩。Digital search树的每一条弧在双数组中都可以以O(1)的时间复杂度计算得到;也就是说,查找一个key值最坏的时间复杂度是O(k),k是这个key值的长度。本文给出了同时具有速度和空间双重性能的双数组的查找,插入,删除算法。假设双数组的长度是n+cm,n是ds树中节点的数量,m是输入符号的数量,c是一个依赖于实现的常数;那么理论上可以证明插入和删除的最坏时间复杂度分别是cm2(插入要解决冲突,所以慢)和cm,与n没有关系。从实验的结果来看,建立双数组的时间随n增长,并且c是一个相当小的常数,从0.17到1.13。



关键词:数据库系统,数据结构,词典,digital search,动态内部存储,关键词查询算法。 ---





1.       导论

在很多信息检索算法中,很需要采用一种快速的digital search算法,或者叫做trie搜索,因为它一个字符(digital)一 个字符地查看输入。使用这种数据结构的例子有一种词法分析器,和一种编译器的本地代码优化器,一种图书搜索,拼写检查,常用单词过滤器,一种自然语言处理 中的形态学分析器等等。词典能够动态增长在自然语言处理中尤为重要,因为经常需要对词汇表添加新词(这其实是双数组的弱项- -)。本文展示的这一算法适合插入远远多于删除的情况,这样删除带来的空间浪费就可以由插入来填补。



       关键词查询策略可以被大致分为两类,按照关键词集合是否可变可以将这些算法分为“动态方法”(允许查询表被修改)和“静态方法”(显然相反)两种。广为人知的“动态方法”有:hashing,二叉树,B+树,扩展hashing,和trie hashing。而“静态方法”有:完美hashing,稀疏表,以及压缩trie。 当使用静态方法的时候我们能专注于提高查询速度和压缩数据结构,而当使用动态方法的时候我们会使用额外的空间以达到更快的更新速度。本文提出的查询方法正 好介于这两者之间,所以我称之为“弱静态方法”。将静态方法扩展到弱静态方法,同时保持前者有用的特性是十分困难的。完美hashing的扩展已经有了,但不能确定插入的时间复杂度上限。本文的目标是建立一种digital search算法,它同时具有静态方法的速度和压缩特性,以及动态方法的快速更新的能力。



       不同于基于key值的搜索方法,digital search采用一连串的字符(digit)来表示一个key。每个h层的DS树的节点表示所有以一定的h个字符开始的关键词;这个节点根据第(h+1)个字符定义它的分支。本文的基本观念是压缩trie树,使用两个一维数组base和check来表示trie树,成为双数组,并且给出更新(插入、删除)算法。Trie的每个节点使用指针指向下一个元素,每个索引元素是一个结束标志加上一个指向新节点的指针(或者null)。查询,插入,删除都非常快,但是它会占用很多空间,因为很多trie树节点是空的;也就是说,trie树是稀疏的。所以我们必须尝试映射节点r到check数组,这种映射关系由base[r]指定。



       在接下来的章节,我们会详细描述我们的想法。在第二节,我们把DS树形式化为模式匹配机器并定义双数组使用O(1)时间计算一条弧。为了将双数组应用于大的关键词集合,双数组做出了一些修改。最主要的创新是仅将足以分辨不通关键词的前缀存储到双数组,将其他部分存储在单独的string里面。插入删除算法在第三章讨论。当插入一个新的非空位置r的时候遇到另一个节点k已经占用这个位置,插入算法通过重新调整base[r]或者base[k]来解决冲突。在本文中,为减少占用的时间和空间占用组少非空未知的k或r有优先权(就是移动占用少的,占用多的不变)。第四节讨论了每个算法的最坏时间复杂度的理论值,并且通过实验验证了。双数组的部分匹配和key-order查询也做出了讨论。最后第五节做出了结论总结。



双数组trie树的基本构造及简单优化



一、 基本构造



Trie树是搜索树的一种,来自英文单词"Retrieval"的简写,可以建立有效的数据检索组织结构,是中文匹配分词算法中词典的一种常见实现。它本质上是一个确定的有限状态自动机(DFA),每个节点代表自动机的一个状态。在词典中这此状态包括"词前缀","已成词"等。

双数组Trie(Double-Array Trie)是trie树的一个简单而有效的实现,由两个整数数组构成,一个是base[],另一个是check[]。设数组下标为i ,如果base,check均为0,表示该位置为空。如果base为负值,表示该状态为词语。Check表示该状态的前一状态,t=base+a, check[t]=i 。



下面举例(源自<<双数组Trie&#xff08;Double-Array Trie&#xff09;的数据结构与具体实现>>)来说明用双数组Trie&#xff08;Double-Array Trie&#xff09;构造分词算法词典的过程。假定词表中只有“啊&#xff0c;阿根廷&#xff0c;阿胶&#xff0c;阿拉伯&#xff0c;阿拉伯人&#xff0c;埃及”这几个词&#xff0c;用Trie树可以表示为&#xff1a;

我们首先对词表中所有出现的10个汉字进行编码&#xff1a;啊-1&#xff0c;阿-2&#xff0c;唉-3&#xff0c;根-4&#xff0c;胶-5&#xff0c;拉-6&#xff0c;及-7&#xff0c;廷-8&#xff0c;伯-9&#xff0c;人-10。。对于每一个汉字&#xff0c;需要确定一个base值&#xff0c;使得对于所有以该汉字开头的词&#xff0c;在双数组中都能放下。例如&#xff0c;现在要确定“阿”字的base值&#xff0c;假设以“阿”开头的词的第二个字序列码依次为a1&#xff0c;a2&#xff0c;a3……an&#xff0c;我们必须找到一个值i&#xff0c;使得base[i&#43;a1]&#xff0c;check[i&#43;a1]&#xff0c;base[i&#43;a2]&#xff0c;check[i&#43;a2]……base[i&#43;an]&#xff0c;check[i&#43;an]均为0。一旦找到了这个i&#xff0c;“阿”的base值就确定为i。用这种方法构建双数组Trie&#xff08;Double-Array Trie&#xff09;&#xff0c;经过四次遍历&#xff0c;将所有的词语放入双数组中&#xff0c;然后还要遍历一遍词表&#xff0c;修改base值。因为我们用负的base值表示该位置为词语。如果状态i对应某一个词&#xff0c;而且Base&#61;0&#xff0c;那么令Base&#61;&#xff08;-1&#xff09;*i&#xff0c;如果Base的值不是0&#xff0c;那么令Base&#61;&#xff08;-1&#xff09;*Base。得到双数组如下&#xff1a;



下标 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Base -1 4 4 0 0 0 0 4 -9 4 -11 -12 -4 -14

Check 0 0 0 0 0 0 0 2 2 2 3 8 10 13

词缀 啊 阿 埃 阿根 阿胶 阿拉 埃及 阿根廷 阿拉伯 阿拉伯人

用上述方法生成的双数组&#xff0c;将“啊”&#xff0c;“阿”&#xff0c;“埃”&#xff0c;“阿根”&#xff0c;“阿拉”&#xff0c;“阿胶”&#xff0c;“埃及”&#xff0c;“阿拉伯”&#xff0c;“阿拉伯人”&#xff0c;“阿根廷”均视为状态。每个状态均对应于数组的一个下标。例如设“阿根”的下标为i&#61;8&#xff0c;那么check的内容是“阿”的下标&#xff0c;而base是“阿根廷”的下标的基值。“廷”的序列码为x&#61;8&#xff0c;那么“阿根廷”的下标为base&#43;x&#61;base[8]&#43;8&#61;12。



二、 基本操作与存在问题



1&#xff0c; 查询

trie树的查询过程其实就是一个DFA的状态转移过程&#xff0c;在双数组中实现起来比较简单&#xff1a;只需按照状态标志进行状态转移即可&#xff0e;例如查询“阿根廷”&#xff0c;先根据“阿”的序列码b&#61;2&#xff0c;找到状态“阿”的下标2&#xff0c;再根据“根”的序列码d&#61;4找到“阿根”的下标base&#43;d&#61;8&#xff0c;同时根据check[base&#43;d]&#61;b&#xff0c;表明“阿根”是某个词的一部分&#xff0c;可以继续查询。然后再找到状态“阿根廷”。它的下标为y&#61;12&#xff0c;此时base[y]<0&#xff0c;check[y]&#61;base&#43;d&#61;8&#xff0c;表明“阿根廷”在词表中&#xff0c;查询完毕。



查询过程中我们可以看到&#xff0c;对于一个词语的查询时间是只与它的长度相关的&#xff0c;也就是说它的时间复杂度为&#xff2f;(1)&#xff0e;在汉语中&#xff0c;词语以单字词&#xff0c;双字词居多&#xff0c;超过三字的词语少之又少&#xff0e;因此&#xff0c;用双数组构建的trie树词典查询是理论上中文机械分词中的最快实现。



2&#xff0c; 插入与删除

双数组的缺点在于&#xff1a;构造调整过程中&#xff0c;每个状态都依赖于其他状态&#xff0c;所以当在词典中插入或删除词语的时候&#xff0c;往往需要对双数组结构进行全局调整,灵活性能较差。



将一个词语插入原有的双数组trie树中&#xff0c;相当于对DFA增加一个状态。首先我们应根据查询方法找出该状态本应所处的位置&#xff0c;如果该位置为空&#xff0c;那好办&#xff0c;直接插入即可。如果该位置不为空。那么我们只好按照构造时一样的方法重新扫描得出该状态已存在的最大前缀状态的BASE值&#xff0c;并由此依次得出该状态后继结点的BASE值。在这其中还要注意CHECK值的相应变化。



例如说&#xff0c;如果&#xff02;阿拉根&#xff02;某一天也成为了一个词&#xff0c;我们要在trie树中插入这一状态。按计算它的位置应在&#xff18;&#xff0c;但8是一个已成状态&#xff0e;所以我们得重新确定&#xff02;阿拉&#xff02;这一最大已成前缀状态的BASE值&#xff0e;重新扫描得出BASE[10]&#61;11。这样状态&#xff11;&#xff15;为&#xff02;阿拉根&#xff02;&#xff0c;且BASE[15]为负&#xff08;成词&#xff09;&#xff0c;CHECK[15]&#61;10&#xff1b;状态&#xff12;&#xff10;为&#xff02;阿拉佰&#xff02;&#xff0c;且BASE[20]&#61;-4&#xff0c;CHECK&#61;10。



这样的处理其实是非常耗时间的&#xff0c;因为得依次对每一个可能BASE值进行扫描来进行确定最大已成前缀状态的BASE值。这个确定过程在构造时还是基本可以忍受的&#xff0c;毕竟你就算用上一&#xff0c;两天来构造也没有问题&#xff08;只要你构造完后可以在效运行即可&#xff09;。但在插入比较频繁时&#xff0c;如果每次都需要那么长的运行时间&#xff0c;那确实是无法忍受的。



双数组删除实现比较简单&#xff0c;只需要将删除词语的对应状态设为空即可――即BASE值&#xff0c;CHECK均为设0。但它存在存在一个空间效率的问题&#xff0e;例如&#xff0c;当我们在上面删除&#xff02;埃及&#xff02;这一词语时&#xff0c;状态11被设为空。而状态10则成了一个无用结点――它不成词&#xff0c;而且在插入新词时也不可重用。所以&#xff0c;随着删除的进行&#xff0c;空状态点和无用状态点不断增多&#xff0c;空间的利用率会不断的降低。



三、 简单优化



优化的基本思路是将双数组trie树构建为一种动态检索方法&#xff0c;从而解决插入和删除所存在的问题。



1&#xff0c; 插入优化

在插入需要确定新的BASE值时&#xff0c;我们是只需要遍历空状态的。非空状态的出现意味着某个BASE值尝试的打败&#xff0c;我们可以完全不必理会。所以&#xff0c;我们可以对所有的空状态构建一个序列&#xff0c;在确定BASE值时只需要扫描该序列即可。

对双数组中的空状态的递增结点r1,r2, …, rm&#xff0c;我们可以这样构建这一空序列&#xff1a;

CHECK[ri]&#61;−ri&#43;1 (1 i m−1),

CHECK[rm]&#61;−(DA_SIZE&#43;1)

其中r1&#61; E_HEAD&#xff0c;为第一个空值状态对应的索引点。这样我们在确定BASE值时只需扫描这一序列即可。这样就省去了对非空状态的访问时间。



这种方法在空状态并不太多的情况下可以很大程度的提高插入速度。



2&#xff0c; 删除优化

1) 无用结点

对于删除叶结点时产生的无用结点&#xff0c;可以通过依次判断将它们置为空&#xff0c;使得可在插入新词时得以重用。例如&#xff0c;如果我们删除了上例中的&#xff02;阿根廷&#xff02;&#xff0c;可以看到&#xff02;阿根&#xff02;这一状态没有子状态&#xff0c;因此也可将它置为空。而&#xff02;阿&#xff02;这一状态不能置空&#xff0c;因为它还有两个子状态。



2) 数组长度的压缩

在删除了一个状态后&#xff0c;数组末尾可能出现的连续空状态我们是可以直接删除的。另外我们还可以重新为最大非空索引点的状态重新确定BASE值&#xff0c;因为它有可能已经由于删除的进行而变小。这们我们可能又得以删除一些空值状态。
推荐阅读
  • 本文介绍了几种常用的图像相似度对比方法,包括直方图方法、图像模板匹配、PSNR峰值信噪比、SSIM结构相似性和感知哈希算法。每种方法都有其优缺点,适用于不同的应用场景。 ... [详细]
  • 本文详细介绍了 PHP 中对象的生命周期、内存管理和魔术方法的使用,包括对象的自动销毁、析构函数的作用以及各种魔术方法的具体应用场景。 ... [详细]
  • 在《数字图像处理及应用(MATLAB)第4章》中,详细探讨了“逢七必过”游戏规则的实现方法,并结合数字图像处理技术进行了深入分析。本章通过丰富的实例和代码示例,展示了如何利用MATLAB实现这一游戏规则,并介绍了数字图像处理的基本原理和技术应用。内容涵盖了图像增强、滤波、边缘检测等多个方面,为读者提供了全面的技术支持和实践指导。 ... [详细]
  • 在机器学习领域,深入探讨了概率论与数理统计的基础知识,特别是这些理论在数据挖掘中的应用。文章重点分析了偏差(Bias)与方差(Variance)之间的平衡问题,强调了方差反映了不同训练模型之间的差异,例如在K折交叉验证中,不同模型之间的性能差异显著。此外,还讨论了如何通过优化模型选择和参数调整来有效控制这一平衡,以提高模型的泛化能力。 ... [详细]
  • 本文对比了杜甫《喜晴》的两种英文翻译版本:a. Pleased with Sunny Weather 和 b. Rejoicing in Clearing Weather。a 版由 alexcwlin 翻译并经 Adam Lam 编辑,b 版则由哈佛大学的宇文所安教授 (Prof. Stephen Owen) 翻译。 ... [详细]
  • 在 Ubuntu 中遇到 Samba 服务器故障时,尝试卸载并重新安装 Samba 发现配置文件未重新生成。本文介绍了解决该问题的方法。 ... [详细]
  • 本文详细介绍了数据库并发控制的基本概念、重要性和具体实现方法。并发控制是确保多个事务在同时操作数据库时保持数据一致性的关键机制。文章涵盖了锁机制、多版本并发控制(MVCC)、乐观并发控制和悲观并发控制等内容。 ... [详细]
  • 全面升级的中文PubMed——Medreading
    Medreading 是一款由科研者之家(HOME for Researchers)推出的中文版PubMed,提供强大的文献检索和分析功能,支持AI辅助全文下载。 ... [详细]
  • Spark中使用map或flatMap将DataSet[A]转换为DataSet[B]时Schema变为Binary的问题及解决方案
    本文探讨了在使用Spark的map或flatMap算子将一个数据集转换为另一个数据集时,遇到的Schema变为Binary的问题,并提供了详细的解决方案。 ... [详细]
  • 本文详细介绍了MySQL数据库的基础语法与核心操作,涵盖从基础概念到具体应用的多个方面。首先,文章从基础知识入手,逐步深入到创建和修改数据表的操作。接着,详细讲解了如何进行数据的插入、更新与删除。在查询部分,不仅介绍了DISTINCT和LIMIT的使用方法,还探讨了排序、过滤和通配符的应用。此外,文章还涵盖了计算字段以及多种函数的使用,包括文本处理、日期和时间处理及数值处理等。通过这些内容,读者可以全面掌握MySQL数据库的核心操作技巧。 ... [详细]
  • 本文详细介绍了 InfluxDB、collectd 和 Grafana 的安装与配置流程。首先,按照启动顺序依次安装并配置 InfluxDB、collectd 和 Grafana。InfluxDB 作为时序数据库,用于存储时间序列数据;collectd 负责数据的采集与传输;Grafana 则用于数据的可视化展示。文中提供了 collectd 的官方文档链接,便于用户参考和进一步了解其配置选项。通过本指南,读者可以轻松搭建一个高效的数据监控系统。 ... [详细]
  • 在软件开发过程中,经常需要将多个项目或模块进行集成和调试,尤其是当项目依赖于第三方开源库(如Cordova、CocoaPods)时。本文介绍了如何在Xcode中高效地进行多项目联合调试,分享了一些实用的技巧和最佳实践,帮助开发者解决常见的调试难题,提高开发效率。 ... [详细]
  • 搜索引擎技术概论(上篇):核心原理与应用分析
    搜索引擎技术概论(上篇)探讨了搜索的基本概念及其核心原理。搜索的本质在于信息检索,即用户通过输入关键词,利用特定的算法从海量数据中快速定位并提供所需信息。本文详细分析了搜索引擎的工作机制及其在实际应用中的表现。 ... [详细]
  • 在尝试对 QQmlPropertyMap 类进行测试驱动开发时,发现其派生类中无法正常调用槽函数或 Q_INVOKABLE 方法。这可能是由于 QQmlPropertyMap 的内部实现机制导致的,需要进一步研究以找到解决方案。 ... [详细]
  • 浏览器作为我们日常不可或缺的软件工具,其背后的运作机制却鲜为人知。本文将深入探讨浏览器内核及其版本的演变历程,帮助读者更好地理解这一关键技术组件,揭示其内部运作的奥秘。 ... [详细]
author-avatar
书友62423539
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有