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

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

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

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

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

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

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

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

空间平滑搜索CLARANS算法

CLARANS是一种有效且广泛应用于空间数据挖掘的聚类算法,非常适合发现多边形的聚类结果.CLARANS的实质是随机重启搜索优化算法.由于搜索空间的表面粗糙不平,布满了局部最优解的"陷阱",因此CLARANS算法易受局部最优解的影响.空间平滑技术允许启发式搜索有效地避开局部最优解的"陷阱".本文给出了基于空间平滑搜索的CLARANS算法(CLARANS algorithm based on Search Space Smoothing - CLARANS-SSS),设计合理的噪声法空间平滑策略能够移除搜索空间中大部分的局部最优解.实验结果表明空间平滑搜索对于CLARANS算法非常有效.     

一种多空间FCM算法

FCM是经典的聚类算法,广泛地应用于模式识别、数据挖掘等领域。FCM算法是一种梯度下降优化算法,对初始解敏感并且容易获得局部最优解。空间平滑能够避免启发式局部搜索算法掉入局部最优解。采用空间平滑策略构造一系列光滑程度不同的搜索空间,在不同的搜索空间中执行FCM算法,并利用前层搜索空间的聚类结果来引导本层搜索空间的聚类。FCMS（FCM based on multi-Space）能够跳过局部最优解的“陷阱”,增大获得全局最优解的概率,达到提高聚类质量的目的。给出了等距法空间平滑策略,并通过实验对比了FCMS算法与FCM算法的聚类质量。实验结果表明,空间平滑对FCM算法非常有效。     

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

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

基于遗传算法的可扩展应用层组播树构建

在应用层组播中,为降低节点的路径延时,通常采用遗传算法和启发式算法来减小组播树直径的方法,但在组播树具有大规模节点数时,遗传算法收敛时间长,而采用启发式算法难以在有约束条件下达到全局最优.本文在具有超节点的双层应用层组播模型基础上,提出了利用遗传算法构建出度受限最小带权路径延时生成树（MWPL-DC-ST）的生成算法GA-MWPL-DC-ST,利用该算法可在超节点上对双层组播树进行分布式构建,从而将求最优解问题的巨大计算量分担到多个超节点上.算法中的初始化、杂交和变异阶段采用启发式算法,对变异参数进行适应性调整,加快了算法的收敛速度.仿真试验表明,本文提出的双层应用层组播模型和GA-MWPL-DC-ST算法能得到比启发式算法更优的解,与采用单层模型的遗传算法相比较,显著降低了算法收敛时间,解决了遗传算法构建有大规模节点数的应用层组播树的可扩展性问题.     

基于反向PageRank的影响力最大化算法

针对社会网络上的影响力最大化算法在大规模网络上难以同时满足传播范围、时间效率和空间效率要求的问题,提出一种混合PageRank和度中心性的启发式算法（MPRD）。首先,基于PageRank,引入一种反向PageRank思想来评估节点影响力;然后,结合局部指标度中心性,设计一种混合的指标来评估节点的最终影响力;最后,通过相似性方法去掉影响力重合严重的节点,选出种子节点集。在6个数据集和两种传播模型上进行实验,实验结果表明,所提的MPRD在传播范围上优于现有的启发式算法,在时间效率上比贪心算法快四、五个数量级,在空间效率上优于基于反向抽样的IMM算法。所提的MPRD在处理大规模网络上的影响力最大化问题时能够取得传播范围、时间效率和空间效率的平衡。     

空间数据库最优位置查询算法研究

针对实际应用的查询要求,提出一种新颖的空间数据库查询类型—最优位置查询。在叙述实际应用的基础上抽象出最优位置查询概念,提出目标对象的优先权度量标准、删减数据对象的启发式规则和最优位置查询算法,分析最优位置查询算法的时间复杂度。实验结果表明,在参数不同取值情况下最优位置查询算法的查询性能仍然高效。     

无线ad hoc网络中定向连通控制集的局部构造算法

在无线ad hoc网络中采用定向天线模型寻找定向连通控制集（DCDS）是构造虚拟骨干网的有效方法。由于求解最小DCDS问题是NPC的。提出了一种在无线ad hoc网络中构造DCDS的局部启发式算法。该算法同时选择转发节点和转发边,极大地减少了时间开销,时间和信息复杂度分别为O（1）和O（n）。理论分析和仿真实验都证明该算法具有良好的性能。     

一种Trie结构

本文描述了一种Ｔｒｉｅ结构，给出了这种Ｔｒｉｅ结构的插入，查找算法，查找算法的时间复杂度为O(log_nK），与以前的工作相比，这是一个改进。本文也给出了将Ｔｒｉｅ结构存放在一维数组后的查找算法。     

Bounded size dictionary compression: SC-completeness and NC algorithms

We study the parallel complexity of a bounded size dictionary version (LRU deletion heuristic) of the LZ2 compression algorithm. The unbounded version was shown to be P-complete. When the size of the dictionary is O(log^kn), the problem of computing the LZ2 compression is shown to be hard for the class of problems solvable simultaneously in polynomial time and O(log^kn) space (that is, SC^k). We also introduce a variation of this heuristic that turns out to be an SC^k-complete problem (the original heuristic belongs to SC^k+1). In virtue of these results, we argue that there are no practical parallel algorithms for LZ2 compression with LRU deletion heuristic or any other heuristic deleting dictionary elements in a continuous way. For simpler heuristics (SWAP, RESTART, FREEZE), practical parallel algorithms are given.     

Platform impact on performance of parallel genetic algorithms: Design and implementation considerations

Many problems in the operations research field cannot be solved to optimality within reasonable amounts of time with current computational resources. In order to find acceptable solutions to these computationally demanding problems, heuristic methods such as genetic algorithms are often developed. Parallel computing provides alternative design options for heuristic algorithms, as well as the opportunity to obtain performance benefits in both computational time and solution quality of these heuristics. Heuristic algorithms may be designed to benefit from parallelism by taking advantage of the parallel architecture. This study will investigate the performance of the same global parallel genetic algorithm on two popular parallel architectures to investigate the interaction of parallel platform choice and genetic algorithm design. The computational results of the study illustrate the impact of platform choice on parallel heuristic methods. This paper develops computational experiments to compare algorithm development on a shared memory architecture and a distributed memory architecture. The results suggest that the performance of a parallel heuristic can be increased by considering the desired outcome and tailoring the development of the parallel heuristic to a specific platform based on the hardware and software characteristics of that platform.     

求解加权圆集布局问题的快速启发式搜索算法

加权圆集布局问题是基于性能驱动的一类布局问题,由于其NP-hard属性,难以在多项式时间内求解,提出一种快速启发式搜索算法。权矩阵的行向量1范数作为首次赌轮选择圆的启发信息,依次以权矩阵的当前行（其行号等于当前选择圆的序号）元素作为下次赌轮选择的启发信息,利用图形学理论给出低计算复杂度的定位规则,进而基于该定序定位规则提出一种启发式搜索算法,以求得该问题的最优解。数值实验表明,该算法的性能优于已有算法。     

基于半耦合稀疏表达的极低分辨率人脸识别

现有基于学习的人脸超分辨率算法假设高低分辨率特征具有流形一致性（耦合字典学习）,然而低分辨率图像的降质过程使得高低分辨率特征产生了“一对多”的映射关系偏差,减少了极低分辨率图像特征的判决信息,降低了超分辨率重建图像的识别率。针对这一问题,引入了半耦合稀疏字典学习模型,松弛高低分辨率流形一致性假设,同时学习稀疏表达字典和稀疏表达系数之间的映射函数,提升高低分辨率判决特征的一致性,在此基础上,引入协同分类模型,实现半耦合特征的高效分类。实验表明：相比于传统稀疏表达分类算法,算法不仅提高了识别率,并且还大幅度降低了时间开销,验证了半耦合稀疏学习字典在人脸识别中的有效性。     

一种基于局部歧义词网格的快速分词算法

提出了局部歧义词网格的概念,针对汉语分词中的覆盖歧义,提出了一种使用迭代算法训练覆盖歧义词典的算法,得到覆盖歧义候选词条词典。在此基础上提出了一种基于局部歧义词网格的、能够检测汉语分词过程中产生的组合歧义和覆盖歧义的分词算法,该算法仅考虑存在歧义的局部歧义词网格,并将对覆盖歧义的处理简化为查询覆盖歧义候选词典,因此,该算法的时间复杂度大幅下降。实验结果表明,该算法能够实现快速的汉语分词,且其分词正确率能够达到97%以上。     

一种并行中英文混合多模式匹配算法

针对中英文混合文本的匹配准确性及大规模数据文本的匹配效率等问题,基于经典的线索化完全哈希特里树算法,提出一种并行化的中英文混合多模式文本匹配算法。采用拆分文本降低多模式匹配算法的串行度,进而在拆分出的小文本上并行地执行文本匹配。通过并行化预处理过程,设计新的存储结构。实验结果表明,该算法在保证结果正确的前提下,执行效率高于经典的串行匹配算法,当数据规模达到226个字符时,可以获得8倍以上的加速比。     

Compressed double-array tries for string dictionaries supporting fast lookup

A string dictionary is a basic tool for storing a set of strings in many kinds of applications. Recently, many applications need space-efficient dictionaries to handle very large datasets. In this paper, we propose new compressed string dictionaries using improved double-array tries. The double-array trie is a data structure that can implement a string dictionary supporting extremely fast lookup of strings, but its space efficiency is low. We introduce approaches for improving the disadvantage. From experimental evaluations, our dictionaries can provide the fastest lookup compared to state-of-the-art compressed string dictionaries. Moreover, the space efficiency is competitive in many cases.