共查询到19条相似文献,搜索用时 125 毫秒
1.
2.
基于双数组Trie树的中文分词词典具有较高的查找效率,但其插入时间复杂度较高.为此提出了一种基于双数组Trie树结构的改进算法iDAT,在原始词典初始化时优先处理分支多的节点,并在初始化之后对base数组中的空序列的下标值做Hash,Hash表中存放空序列之前的所有空序列个数之和,而后运用iDAT算法进行插入.本算法借鉴了单模式匹配的Sunday算法中的跳跃思想,在适当增加空间开销的基础上,降低了Trie树在动态插入过程中的平均时间复杂度,在实际操作过程中有着良好的性能. 相似文献
3.
对汉语信息处理中常常要涉及汉语词典查询,当所涉及的词典规模较为庞大时如何快速访问词典以获取词语知识便成为了一个需重点解决的问题。将阐述一种简单快捷的基于双数组Trie(Double-Array Trie)原理的词典查询机制。该算法的查询时间为O(n)的线性时间(n为查询词条的长度),由此可见双数组算法在时间上存在着明显优势,但在空间耗费上却存在着浪费现象。前人提出了一些解决方案,其中主要的有:在构造双数组时采用一种启发式排序策略,即每一次都先处理当前分支节点最多的活动节点。考虑到这种启发式思想为确定性算法,容易陷入局部最优陷阱之中,因此在这种思想的基础上引入了舍伍德随机思想和遗传算法中常常运用到的变异思想,在改进算法空间利用率的同时也使得算法跳出了局部最优解的陷阱。 相似文献
4.
一种基于双数组Trie的B2B规则串提取方法 总被引:1,自引:1,他引:0
针对B2B垂直搜索引擎中提取产品规格信息困难的问题,提出了一种基于双数组Trie(Double-Array Trie)的规则串提取方法。该方法针对B2B系统中“参数名:参数值”字符串的规则特征构建规则串,生成双数组Trie树;并优先处理分支结点最多的子树,来提高存储效率。该方法对搜索文本进行一次扫描就能得到所有规则串;通过在规则中加入约束条件,对候选串进行有效过滤,以提高规则串的提取准确率。实验表明,该方法能够降低传统规则串查找的算法复杂度,查找规则串的时间复杂度是O(n)。 相似文献
5.
虚拟旅游中的3D点云数据特别庞大,批量索引成为了当今的研究热点。许多索引树存在兄弟结点空间区域重叠、不能实现细节层次索引、索引效率低等问题。为此,将点数据反射强度和细节层次技术引入R树,在改进R树的基础上提出LODR树。建树前,将点云数据进行排序、分组、去除空间重叠等预处理。树的每层设有不同反射强度阈值,把叶结点中满足阈值条件的索引记录沿父-祖父-曾祖父的家谱关系上移,并插入对应的非叶结点,利用该方法创建细节层次索引树。利用反射强度控制数据冗余,棱锥裁剪技术实现查询优化。实验结果表明,LODR树在细节层次索引、查询效率等方面具有明显优势。 相似文献
6.
现有地址输入提示方法涉及标准地址和POI的研究较少,地址字符串的索引,大多采用Trie(字典)树索引,Trie树建立时内存消耗巨大,面临海量数据,问题突出。针对以上问题,提出一种基于Key-Value数据库的快速地名地址输入提示方法,该方法基于Trie树结构进行改进,降低了地址索引的复杂度;基于Key-Value数据库构建Trie树,避免了内存消耗巨大的问题。实验结果表明,基于Key-Value数据库构建的Trie树索引较基于内存构建的Trie树索引在事务响应性能方面和内存消耗方面具有明显的优势和效率。 相似文献
7.
在分析原有查找算法的基础上,结合IPv6地址结构和骨干路由表特点,提出一种新的快速IPv6路由查找算法。基于Hash表和多分支Trie树结构,将最常用到的路由前缀按前缀长度放置在Hash表中,并按前缀值有序存放在表结点中,不仅可以进行最常用前缀的二分查找,同时又是其他前缀匹配的索引。对于其他的前缀匹配问题,根据Hash表中的索引到相应的多分支Trie树完成最长前缀匹配。分析及测试证明该算法具有很好的时间效率,更新速度很快。 相似文献
8.
9.
基于索引数组和复合频繁模式树的频繁闭项集挖掘算法 总被引:1,自引:0,他引:1
频繁闭项集惟一确定频繁项集且规模小得多.CROP是一种基于复合频繁模式树的、频繁闭项集高效挖掘算法,但存在着候选结点过多的问题.这些非闭合结点的生成、检查和剪裁带来了大量不必要的操作.提出了一种改进的频繁闭项集挖掘算法CROP_Index.该算法用"索引数组"来组织数据,找到频繁共同出现的项集.基于二进制位图,给出了一个包含索引的计算方法,并利用索引启发信息合并,得到复合型频繁模式树的初始结点;同时给出一些新的性质,使得改进的算法只生成闭合结点,从而节省了大量不必要的操作,缩小了搜索空间.实验结果表明该算法效率较高. 相似文献
10.
11.
业务选择网关(SSG)中的访问控制模块从用户请求数据包中解析出URL,并且根据用户的URL访问权限进行访问控制和路由选择。首先提出了改进的有限状态机模型,然后用双数组表示该有限状态机,并提出了优先处理分支结点较多的结点的优化策略。实验证明该算法不仅提高了查询速度,而且占用的存储空间也较少,进一步减少了数据的稀疏。最后将该算法应用在访问控制模块上,实践证明此算法可行、高效。 相似文献
12.
Trie结构是一种使用搜索关键字来组织信息的搜索树,可用于高效地存储和搜索字符串集合.T.Nipkow给出了实现Trie的Isabelle建模与验证,然而其Trie在存储和操作时存在大量的冗余,导致空间利用率不高,且仅考虑英文单模式下查找.为此,本文基于索引即键值的思想提出的Trie+结构,相较于传统的索引与键值分开存储的结构能减少50%的存储空间,大大提高了空间利用率.并且,对Trie+结构的查找、插入、删除等操作给出了函数式建模及其严格的机械化验证,保证操作的正确性和可靠性.进一步,首次提出一种匹配算法的通用验证规约,旨在解决一系列的匹配算法正确性验证问题.最后,基于Trie+结构与匹配算法通用验证规约,建模和验证了函数式中英文混合多模式匹配算法,发现并解决了现有研究中的基于完全哈希Trie的多模式匹配算法的模式串前缀终止的Bug.所提的Trie+结构以及验证规约在提高Trie结构空间利用率和验证匹配算法中,有一定的理论和应用价值. 相似文献
13.
14.
针对在数据量动态增加的场景下现有的排序算法管理数据导致算法性能大大降低的问题,提出一种16-bit Trie树排序算法。借助邻居节点上存储的链节点指针完成排序,它不仅可以边构建边排序,且引入动态数组可以提高该算法的空间效率。仿真结果表明,传统Trie树支持数据动态更新,但通过遍历Trie树的方式完成排序耗时较多,快速排序算法在数据动态增加时效率低,16-bit Trie树排序算法支持数据动态更新,排序时间明显少于传统Trie树,优于快速排序,这表明16-bit Trie树排序算法在处理海量动态数据时具有突出优势。 相似文献
15.
Trie树数据结构的实现方法灵活,所需存储器空间小,是实现高速路由查找和分组转发的理想选择。为满足10 Gb/s线速度网络处理器中微引擎的设计要求,提出一种基于最优平衡、多层存储的Trie树路由查找算法。建立一种平衡的压缩树结构,将该树中相邻的多层节点压缩到一个存储节点中。通过构造特定的数据存储结构来减小树的搜索深度,以空间换取时间,从而提高路由查找速度和分组转发效率。在网络处理器的查找微引擎设计中实现Trie路由查找算法,实验结果表明,单个微引擎的查找速度为4.4 Mb/s,能达到节省存储空间、提高查找效率的效果。 相似文献
16.
研究了一种有效的词典驱动的联机手写日文病名识别方法。病名词典以树结构存储,包含21 713个病名短语。在切分中,手写病名字符串通过分析相邻笔划之间的空间信息等特征被切分为原始的片段序列。连续的片段动态地合并为候选字符模式,不同的合并方式产生不同的候选字符序列,这样可构成一个切分候选网格。在识别过程中,结合病名词典匹配来限制候选字符模式的类别扩展,采用集束搜索策略来寻找到一条最优路径作为识别结果。用500个实际的手写病名样本做实验,平均每个病名的识别时间为0.87 s,识别正确率为83.16%。 相似文献
17.
局部搜索算法是目前求解SAT问题比较有效的方法,而Sattime算法是在SAT国际大赛中获得大奖的一种典型局部搜索算法。在Sattime算法的求解过程中,记录变元翻转事件流数据库,通过数据分析与模式挖掘,发现Sattime算法的局部搜索行为中会出现相邻搜索步选择同一个变元的现象,即所谓的回环现象,从而降低了求解效率。为解决此问题,提出两种概率控制策略:加强子句选择策略和加强变元选择策略,并将这两种策略应用到Sattime算法中,形成新的局部搜索算法Sattime-P。实验结果表明,与Sattime算法相比,改进后的Sattime-P算法求解效率有显著的提升。该方法也对其他局部搜索算法的改进具有参考价值。 相似文献
18.
包分类技术是下一代网络设备的关键技术之一.研究有效的包分类算法是目前网络技术领域的热门课题.层压缩树包分类算法的基本思想是:对路径压缩之后的二叉树进行层压缩,使压缩树中的节点能够按序存储在数组中.通过对数组元素跳跃式的查找快速的对包头进行分类.仿真试验结果表明该算法在较大规则数下能够实现对包头的快速分类,分类速度可以达到每秒处理接近2M个包头,具有O(d)的时间复杂度(d为域的个数);在中等规模规则数下具有O(dN)的空间复杂度,并且其存储量优于其他算法(如Bitmap和区域分割包分类算法).由于层压缩树算法对包头的每个域独立查找,在硬件实现上采用并行查找各个域的处理方式将使该算法的查找性能得到更大的提高. 相似文献