双数组Trie树算法优化及其应用研究

本文对双数组Trie树(Doub le-Array Trie)算法提出了一种优化策略,即在采用Trie树构造数组的过程中,优先处理分支结点数更多的结点。这种优化策略可以在保证该算法数据查找效率不变的同时,进一步减少数据稀疏,提高空间利用率。我们基于该优化算法实现了一个词典管理程序,并与利用其他索引机制的词典进行了实验对比。实验结果表明,利用优化的双数组Trie树算法的词典不仅在查询速度上优于用其他索引机制的词典,而且存储数据的空间占用也比较小。

基于哈希和双数组trie树的多层次地址匹配算法

针对目前地址匹配算法匹配速率低、空间开销大的不足,提出了一种基于哈希和双数组trie树的多层次地址匹配算法.利用中文地址的分类、分层及组合规则,改进了地址匹配词典的构建方式,减少了词典构建的时间和空间开销.通过哈希运算,将空间坐标存储在哈希表相应的位置上,加快了空间坐标的检索效率.同时,在地址匹配的过程中,采用双向扫描及哈希运算代替传统的数据库检索方式,提高了地址匹配速率.最后,通过实验对算法的有效性进行了验证.

基于双数组Trie树中文分词研究

对双数组Trie树(Double-Array Trie)分词算法进行了优化:在采用Trie树构造双数组Trie树的过程中,优先处理分支节点多的结点,以减少冲突;构造一个空状态序列;将冲突的结点放入Hash表中,不需要重新分配结点.然后,利用这些方法构造了一个中文分词系统,并与其他几种分词方法进行对比,结果表明,优化后的双数组Trie树插入速度和空间利用率得到了很大提高,且分词查询效率也得到了提高.

基于双数组Trie树的中文分词词典算法优化研究

基于双数组Trie树的中文分词词典具有较高的查找效率,但其插入时间复杂度较高。为此提出了一种基于双数组Trie树结构的改进算法iDAT,在原始词典初始化时优先处理分支多的节点,并在初始化之后对base数组中的空序列的下标值做Hash,Hash表中存放空序列之前的所有空序列个数之和,而后运用iDAT算法进行插入。本算法借鉴了单模式匹配的Sunday算法中的跳跃思想,在适当增加空间开销的基础上,降低了Trie树在动态插入过程中的平均时间复杂度,在实际操作过程中有着良好的性能。

基于遗传算法和舍伍德思想的双数组Trie树改进

对汉语信息处理中常常要涉及汉语词典查询,当所涉及的词典规模较为庞大时如何快速访问词典以获取词语知识便成为了一个需重点解决的问题。将阐述一种简单快捷的基于双数组Trie(Double-Array Trie)原理的词典查询机制。该算法的查询时间为O(n)的线性时间(n为查询词条的长度),由此可见双数组算法在时间上存在着明显优势,但在空间耗费上却存在着浪费现象。前人提出了一些解决方案,其中主要的有:在构造双数组时采用一种启发式排序策略,即每一次都先处理当前分支节点最多的活动节点。考虑到这种启发式思想为确定性算法,容易陷入局部最优陷阱之中,因此在这种思想的基础上引入了舍伍德随机思想和遗传算法中常常运用到的变异思想,在改进算法空间利用率的同时也使得算法跳出了局部最优解的陷阱。

一种基于双数组Trie的B2B规则串提取方法

针对B2B垂直搜索引擎中提取产品规格信息困难的问题,提出了一种基于双数组Trie(Double-Array Trie)的规则串提取方法。该方法针对B2B系统中"参数名:参数值"字符串的规则特征构建规则串,生成双数组Trie树;并优先处理分支结点最多的子树,来提高存储效率。该方法对搜索文本进行一次扫描就能得到所有规则串;通过在规则中加入约束条件,对候选串进行有效过滤,以提高规则串的提取准确率。实验表明,该方法能够降低传统规则串查找的算法复杂度,查找规则串的时间复杂度是O(n)。

网络安全态势感知中Trie树关键词高速匹配算法研究

海量数据中关键词高速检索对增强网络安全态势感知系统反应速度,提高系统整体效率和安全性具有重要意义。基于双数组Trie树的网络信息检索算法具有较高的查找效率,但其插入时间复杂度较高,同时叶子结点占用了大量存储空间。为此,文章提出一种基于叶子结点压缩存储的双数组Trie树构造方法,按层次遍历Trie树,将分枝结点存储在基本双数组中,对叶子结点进行压缩后以位图形式存储于压缩数组中。该方法在保留双数组Trie树查询性能的同时,一定程度上提高了插入效率,改善了存储空间利用效率。

基于双数组Trie树法的关键字预处理技术及其在CNC语法检验中的应用

语法检验在CNC系统中占有相当大的比重,尤其是在数控系统的自动或MDI方式下运行。NC代码的正确与否直接关系到能否正确完成数控加工,而现在国内自主开发CNC系统的语法检验功能还不够完善,并且检验方法也不尽科学。针对五轴联动高档数控机床,参照双数组Trie算法的原理,提出了基于双数组Trie算法的关键字预处理技术,并将其成功地应用在语法检验之中,从而使得对NC代码的语法检测更加准确。

基于Trie树的京剧术语语义词典

现有的中文分词系统缺少专业分词组件,难以满足特定领域术语分词的需求,导致专业领域分词精确度较低。为此,提出基于Trie树的京剧术语词典。扩展主流词库,通过定义语义代码的方式建立京剧专业术语之间的语义联系,并利用双数组算法实现Trie。实验结果表明,加入专业术语词典可以提高系统的分词准确率。

基于双数组Trie树的渔业领域分词研究

渔业信息分词对渔业信息系统处理的速度和效率有很大的影响。对汉语词典查询算法进行了分析,用基于双数组Trie树机制的汉语词典实现了渔业信息的分词,并与基于双字Hash机制词典的分词方法进行了试验对比,证明双数组Trie树机制的词典比基于双字Hash机制的词典有更高的查询速度。

基于双数组trie树的多模式复杂事件检测方法

制造物联网中海量实时数据流急需高效的事件检测与处理方法,高效意味着单位时间内使用较小的存储空间处理更多的输入事件。提出一种基于双数组trie树的多模式复杂事件检测方法,通过构建多模式匹配自动机模型减少查询过程中冗余的检测和计算,并利用双数组trie树充分压缩存储空间,从而提高了复杂事件处理的效率。仿真实验表明,提出的方案相比传统的单模式复杂事件检测,具有较小的空间和时间消耗。

基于改进Trie树的歧义消解方法

词典是汉语自动分词的基础,减少交集型歧义可以提高分词的准确率。在基于词典切分中,传统的Trie树每个节点存储一个字符,构建时产生了很多空指针。为了优化词典存储结构,在Trie树的基础上,采用双字Hash机制:把Trie索引树的深度限制为2,词的剩余字符串则按序组成类似"整词二分"的词典正文,并在每组词语的叶子节点上增加词频和词性的属性值,用于后序的交集型歧义识别。加载了搜狗实验室中文互联网语料统计出的15万条高频词,平均大小为60KB的5篇不同领域的测试语料作为测试样本。实验结果表明:相比其他词典而言,双字Hash分词速度得到显著提高,分词的正确率达到93.1%,基本可以满足实用型中文信息处理系统的需要。

基于双数组Trie树的嵌入式TTS系统研究

双数组Trie树是汉字分词的一种比较常用的方法。本文对双数组Trie树作了简要的回顾,设计实现了嵌入式TTS系统中利用双数组Trie进行分词的实现算法,提出了在服务器上构造、调整双数组,在嵌入式系统中使用双数组的方法,并对该方法进行了实验分析。

汉语词典的快速查询算法研究

汉语词典查询是中文信息处理系统的重要基础部分,对系统效率有重要的影响。本文对汉语词典查询算法研究作了简要回顾,设计实现了基于双数组TR IE机制的汉语词典查询算法,并提出了基于双编码机制的词典查询算法。最后以逐字二分法查询性能为基准,使用这两种词典询机制进行了词语直接查询和分词查询两种应用的性能测试。经过实验分析,双数组TR IE机制的词典查询算法在查询速度上提高明显,查询速度约是逐字二分法的5倍。双编码机制的的词典查询算法查询速度有一定提高,而且调整机制更加灵活。

CACDP:适用于云存储动态策略的密文访问控制方法

数据的机密性是云存储环境下的难点问题,基于密文的访问控制技术是解决该问题的重要思路,在目前的基于密文的访问控制技术中,数据的高安全需求和频繁的策略更新使得数据拥有者(data owner,DO)端的权限更新代价过高,进而严重制约了系统的整体效率.针对此问题,提出一种适用于云存储动态策略的密文访问控制方法(cryptographic access control strategy for dynamic policy,CACDP),该方法提出了一种基于二叉Trie树的密钥管理机制,在此基础之上利用基于ELGamal的代理重加密机制和双层加密策略,将密钥和数据更新的部分开销转移到云端以减少DO权限管理负担,提高DO的处理效率.最后通过实验验证了该方案有效降低了策略更新为DO带来的性能开销.

基于存储优化的多模式串匹配算法

多模式串匹配算法是网络内容过滤系统的核心技术之一.自动机的存储空间大小和Cache性能是影响多模式串匹配算法速度的关键因素.随着模式串规模的扩大,自动机的巨大存储开销导致现有的串匹配算法性能大幅度下降.从压缩存储空间以提高Cache命中率的思想出发,提出了一种对经典SBOM算法的优化策略,它用Suffix Tree代替SBOM算法中的Factor Oracle结构,同时用剪枝的方法将Suffix Tree降低为近似线性的空间复杂度,然后用双数组Trie表示之,以压缩存储空间.与SBOM算法相比,改进算法不仅能够有效地节省存储空间,而且显著地提高了串匹配的速度,非常适合于在线高速匹配的应用环境.

一种基于Aho-Corasick算法改进的多模式匹配算法

目前互联网中以文本存在的数据非常庞大,针对在如此庞大的文本中如何准确、快速地找到多个不同的目标字符串的问题,在介绍常见的模式匹配算法的优点和缺点基础上,结合Trie速多模式匹配算法。根据对比性实验的结果分析得出,改进AC且匹配速度大约是AC算法的5倍。

一种双哈希IP数据包分类算法研究

本文在无冲突哈希算法和异或哈希算法的基础上,提出了一种双哈希的IP分类算法,该算法的核心有三点:一是基于目的/源端口和协议域构造无冲突哈希,由于该三域的组合数目非常少,避免了空间爆炸;二是在异或哈希算法的基础上,将目的/源IP连成比特串后分为四块后进行异或,为了降低冲突率,将异或后的关键值再与一个随机数进行异或,获得分类索引值,并用此值生成多比特Trie树,一般情况下减小了空间和时间复杂度;三是在Trie树终点存放最终分类规则的索引值,为了保证查找到的规则的正确性,对每一个索引值的源/目的IP地址均匹配一次。通过以上三点改进一般要降低算法的时间复杂度和空间复杂度,通过仿真,当对1万务分类规则进行包分类时,该算法的包分类速度可以达到2MPps,所消耗的最大内存为4MB。

混合信息双数组的未登录词动态识别模型

未登录词是影响命名实体识别效果的重要因素,现有分词工具在处理未登录词时不仅识别效果欠佳,且存在识别时间较长等问题。为提高分词效果,在现有分词器基础上结合未登录词识别模型,提出了一种基于改进双数组Trie的混合信息未登录词动态识别模型MIDAT,将双数组Trie扩展为字符双数组与概率双数组,利用字符双数组存储字符串词段信息,概率双数组存储字符串节点间的成词概率信息,通过不断识别未登录词,动态更新两个双数组Trie。实验结果表明,在相同的数据集下,结合MIDAT的分词器后对于未登录词的分词效果要优于结巴等常用分词器,同时在时间效率上相比传统的未登录词识别模型提升约8倍。

利用频率特征的Trie树索引快速构造算法

随着物联网技术的日益成熟和云计算标准的确立以及各种智能终端的大规模出现,互联网数据呈指数增加,为数据建立索引至关重要,为此提出一种基于词频的Trie树索引快速构造算法,首先对索引字符串进行排序,然后对排序文件进行预处理,预处理生成一个三元组,分别由相同字符横向偏移、纵向偏移及字符组成.快速算法依次扫描预处理数据的每一列,根据三元组的偏移跳过相同的字符前缀.实验结果显示,本算法的时间明显少于传统构造算法,优于Aoe的双数组Trie构造算法.