检索结果-南通市图书馆

维普期刊数据库博看期刊

在线全文

学校读者我要写书评

暂无评论

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

中文信息学报 2006年第5期20卷 24-30页

作者：王思力张华平王斌中国科学院计算技术研究所

本文对双数组Trie树(Doub le-Array Trie)算法提出了一种优化策略,即在采用Trie树构造数组的过程中,优先处理分支结点数更多的结点。这种优化策略可以在保证该算法数据查找效率不变的同时,进一步减少数据稀疏,提高空间利用率。我们基于... 详细信息

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

关键词：计算机应用中文信息处理双数组 Trie树词典分词

在线全文

学校读者我要写书评

暂无评论

基于双数组有限状态机的URL访问控制算法

计算机工程与应用 2007年第36期43卷 129-131,140页

作者：丁振国赵大勇西安电子科技大学计算机学院西安710071

业务选择网关(SSG)中的访问控制模块从用户请求数据包中解析出URL,并且根据用户的URL访问权限进行访问控制和路由选择。首先提出了改进的有限状态机模型,然后用双数组表示该有限状态机,并提出了优先处理分支结点较多的结点的优化策略。... 详细信息

业务选择网关(SSG)中的访问控制模块从用户请求数据包中解析出URL,并且根据用户的URL访问权限进行访问控制和路由选择。首先提出了改进的有限状态机模型,然后用双数组表示该有限状态机,并提出了优先处理分支结点较多的结点的优化策略。实验证明该算法不仅提高了查询速度,而且占用的存储空间也较少,进一步减少了数据的稀疏。最后将该算法应用在访问控制模块上,实践证明此算法可行、高效。

关键词：业务选择网关 URL 访问控制有限状态机双数组

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

在线全文

学校读者我要写书评

暂无评论

计算机工程与科学 2013年第9期35卷 127-131页

作者：杨文川刘健于淼北京邮电大学计算机学院北京100876

基于双数组Trie树的中文分词词典具有较高的查找效率,但其插入时间复杂度较高。为此提出了一种基于双数组Trie树结构的改进算法iDAT,在原始词典初始化时优先处理分支多的节点,并在初始化之后对base数组中的空序列的下标值做Hash,Hash表... 详细信息

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

关键词：双数组 Trie树时间复杂度分词词典

在线全文

学校读者我要写书评

暂无评论

并行分区双数组索引结构的研究

并行分区双数组索引结构的研究

作者：张崇德昆明理工大学

学位级别：硕士

随着信息量的急剧增长,大量的数据需要以字符串的形式存储,例如文档,网页,基因组数据等等,提高字符串的存储和检索效率具有非常重要的意义。Trie是字符串存储和查询最为常见的结构,是一种有序树,其可将字符串的公共前缀表示为一条公共... 详细信息

随着信息量的急剧增长,大量的数据需要以字符串的形式存储,例如文档,网页,基因组数据等等,提高字符串的存储和检索效率具有非常重要的意义。Trie是字符串存储和查询最为常见的结构,是一种有序树,其可将字符串的公共前缀表示为一条公共的路径,有较高的存储和查询效率,但对目前常见的Trie的矩阵存储或链式存储来说,均难以兼顾查询性能和存储空间开销之间的矛盾。双数组结构很好的解决这一矛盾,其查询性能和存储空间之间取得了较好的平衡,但因其在索引创建时产生大量冲突导致冲突处理冲突代价增加,因此其创建效率较低。首先为降低双数组的构造代价,设计两级分区框架(TLP),先将数据集划分为较小的下层分区,然后提出一种基于小根堆的贪心合并算法(MHG-Merge)将下层分区合并为相对均衡的上层分区,在此基础上实现了分区双数组索引结构。实验结果表明,相对传统的DA而言,具有较高的构造效率;相对FST而言,具有较高的查询效率。其次,在TLP基础上结合高效的并行框架Open MP,并行实现了两种分区DA索引结构UP-DA和LP-DA及对应的并行查询算法。从而进一步有效提高了双数组的构造效率和查询效率。TLP具有的一个重要的特性是:其可以和其它双数组或字符串索引无缝集成,因此具有较好的可扩展性。

关键词：双数组 Trie TLP 负载均衡 UP-DA LP-DA 并行

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于双数组的分词词典研究与实现

基于双数组的分词词典研究与实现

作者：姜鹏大连理工大学

学位级别：硕士

分词词典是汉语自动分词系统的一个基本组成部分,词典的查询速度直接影响到分词系统的处理速度。在因特网上的中文文本检索、汉字与汉语语音识别系统的后处理以及中文文语转换系统的前处理等,均对分词速度提出了更高要求,因此建立高效... 详细信息

分词词典是汉语自动分词系统的一个基本组成部分,词典的查询速度直接影响到分词系统的处理速度。在因特网上的中文文本检索、汉字与汉语语音识别系统的后处理以及中文文语转换系统的前处理等,均对分词速度提出了更高要求,因此建立高效快速的分词词典具有显著的现实意义。目前信息处理用的词典机制主要有整词二分、TRIE索引树、逐字二分等几种方法,其中TRIE索引树和逐字二分机制查询效率较高。这几种词典机制都是以排序的线性表来提高查询效率,数据结构比较复杂且查询速度较慢。本文主要工作是分析了几种常用词典构造方法的优缺点,针对分词中特定的查询条件,设计并实现了基于双数组的分词词典,同时分析了基于双数组的分词词典的性能。本文将双数组方法与其它几种词典构造方法进行了对比分析。在双数组词典构造方法与PAT树方法的对比实验中,可以看出双数组方法的查询速度要好于PAT树及其变型树的查询性能。本文最后给出了分词词典实现的数据存储模型,并详细分析了该模型的优缺点。该模型的主要特点是将存储的数据分为两种不同长度信息进行存储,这样可以大大减少对文本的读取操作,能够加快分词的执行速度。对于文中提到的未登录词问题,本文也做了简单的尝试,利用PAT树的动态性特点以及统计模型的优点,从大规模文本中查找词频高于一定阈值的高频词,从而识别出一部分的未登录词,进而部分解决分词过程中未登录词过多的切分问题。PAT算法和Double-Array算法具有不同的有缺点,可以满足不同场合的需要,也可以组合起来使用,解决词典查询的速度和动态性这两个较困难的问题。

关键词：分词词典双数组 PAT 词典机制

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

双数组穷举法挖掘医药销售数据库频繁集

现代电子技术 2010年第18期33卷 66-68页

作者：薛向阳渭南职业技术学院陕西渭南714000

为了挖掘医药销售数据库频繁集,采用双数组穷举算法DAEA。该算法主要使用两个数组和穷举算法,实现挖掘医药销售数据库的频繁集功能。该算法的优点是只需对医药销售数据库进行数据预处理就可以直接挖掘该数据库的频繁集,无需把医药销售... 详细信息

为了挖掘医药销售数据库频繁集,采用双数组穷举算法DAEA。该算法主要使用两个数组和穷举算法,实现挖掘医药销售数据库的频繁集功能。该算法的优点是只需对医药销售数据库进行数据预处理就可以直接挖掘该数据库的频繁集,无需把医药销售数据库转换成相应的事务数据库。根据DAEA算法,开发了医药销售数据库频繁集挖掘系统,使用该系统挖掘医药销售数据库的频繁集,挖掘的结果与实际相吻合,说明该算法是可行的和有效的。

关键词：数据挖掘关联规则频繁集双数组穷举法

在线全文

学校读者我要写书评

暂无评论

双数组Trie树索引的可操作性研究

计算机系统应用 2009年第10期18卷 53-56,52页

作者：廖敏褚颖娜宋继华北京师范大学信息科学与技术学院北京100875

双数组是组织和实现Trie树的一种数据结构。双数组Trie树索引实现的是一种线性时间复杂度的搜索机制,因此被广泛的应用于信息检索和中文分词等领域。然而双数组Trie树索引建立后不易于更新,限制了这种索引的现实应用。在前人的双数组Tri... 详细信息

双数组是组织和实现Trie树的一种数据结构。双数组Trie树索引实现的是一种线性时间复杂度的搜索机制,因此被广泛的应用于信息检索和中文分词等领域。然而双数组Trie树索引建立后不易于更新,限制了这种索引的现实应用。在前人的双数组Trie树优化索引构造的基础上,分析了插入和删除操作的所有可能情况,提出了对双数组Trie树索引进行相关操作的算法。最后分析了其时间和空间开支,并用实验结果证明了其可行性。

关键词：信息检索 Trie树双数组稳定词空间开支

在线全文

学校读者我要写书评

暂无评论

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

软件导刊 2012年第7期11卷 17-19页

作者：戴耿毅佘静涛浙江工业大学信息学院浙江杭州310032 浙江工业大学图书馆浙江杭州310032

从汉字编码和构造过程两个方面对双数组Trie树算法进行改进和实现。在编码过程中,按照汉字的深度由浅入深依次编码;构造字典时,按照首字节点词条数目由大到小顺序构造。改进后的算法查找效率不变,但缩短了构造字典的时间;减少了数据稀疏... 详细信息

从汉字编码和构造过程两个方面对双数组Trie树算法进行改进和实现。在编码过程中,按照汉字的深度由浅入深依次编码;构造字典时,按照首字节点词条数目由大到小顺序构造。改进后的算法查找效率不变,但缩短了构造字典的时间;减少了数据稀疏,提高了空间利用率。针对改进前后的算法,从时间开支和空间开支两个角度分别进行对比,实验结果证明算法改进可行。

关键词：双数组 TRIE字典信息检索

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

在线全文

学校读者我要写书评

暂无评论

信息网络安全 2019年第4期 55-62页

作者：徐国天张铭中国刑事警察学院网络犯罪侦查系辽宁沈阳110854 哈尔滨医科大学附属第二医院黑龙江哈尔滨150086

海量数据中关键词高速检索对增强网络安全态势感知系统反应速度,提高系统整体效率和安全性具有重要意义。基于双数组Trie树的网络信息检索算法具有较高的查找效率,但其插入时间复杂度较高,同时叶子结点占用了大量存储空间。为此,文章提... 详细信息

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

关键词：态势感知双数组 Trie树压缩信息检索