后缀树

摘要： 查询文本中频繁出现的短语可快速掌握文本内容,然而传统频繁词序列挖掘算法面向挖掘任务时的时间复杂度较高,无法满足频繁更换查询条件及快速获得反馈的查询需求。利用基于频率树的快速频繁词序列挖掘算法(TS;ining),在保持后缀树线性构造时间的情况下实现文本集合中频繁词序列的查询,并采用树型索引结构避免多次扫描文本集合,降低算法时间复杂度。针对连续时间区间内的频繁词序列查询问题,提出改进的剪枝挖掘算法(TS;runing),通过减少频率树的扫描范围进一步提高挖掘效率。实验结果表明,TS;ining与TS;runing算法的运行时间相比经典Apriori挖掘算法约减少了2个数量级,具有更高的频繁词序列挖掘效率。

摘要： 为保障用户免遭侵犯隐私的风险,提出了一种特别支持基因数据的可搜索加密方法.针对目前密文搜索方案大多数仅支持通过关键字进行搜索,而无法用于不含关键字的基因数据的问题,利用后缀树和伪随机函数等密码学原语构建安全索引,实现对密文基因数据的任意子字符串搜索.安全性证明该方法满足动态自适应安全,利用理论分析和真实数据对效率进行测评.该方法可以对基因数据进行高效安全的任意子字符串搜索,保护数据完整性和隐私性,在个性化医疗大众化的环境下具备广阔的应用前景.

摘要： 传统后缀树算法对于中文场景的适用性较差并且有着空间占用大的缺点.面向中文分词改造后缀树索引的构建,以适用于中文的短语检索和域搜索.改进域搜索的索引结构以加快检索速度,将文档ID从索引中剥离出来以减少空间占用,选取最合适的压缩算法对索引进行压缩.实验结果表明,该索引的检索速度至少较Lucene快约37％,空间占用相较原算法可以减少约82％.

摘要： To solve the problem that the existing methods based on the fixed-order Markov models cannot make full use of the structural features involved in the subsequences of different orders,a new Bayesian method based on the multi-order Markov model was proposed for symbolic sequences classification.First,a Conditional Probability Distribution (CPD) model was built based on the multi-order Markov model.Second,a suffix tree for n-order subsequences with efficient suffix-tables and its efficient construction algorithm were proposed,where the algorithm could be used to learn the multi-order CPD models by scanning once the sequence set.A Bayesian classifier was finally proposed for the classification task.The training algorithm was designed to learn the order-weights for the models of different orders based on the Maximum Likelihood (ML) method,while the classification algorithm was defined to carry out the Bayesian prediction using the weighted conditional probabilities of each order.A series of experiments were conducted on real-world sequence sets from three domains and the results demonstrate that the new classifier is insensitive to the predefined order change of the model.Compared with the existing methods such as the support vector machine using the fixed-order model,the proposed method can achieve more than 40％ improvement on both gene sequences and speech sequences in terms of classification accuracy,yielding reference values for the optimal order of a Markov model on symbolic sequences.%针对基于固定阶Markov链模型的方法不能充分利用不同阶次子序列结构特征的问题,提出一种基于多阶Markov模型的符号序列贝叶斯分类新方法.首先,建立了基于多阶次Markov模型的条件概率分布模型;其次,提出一种附后缀表的n-阶子序列后缀树结构和高效的树构造算法,该算法能够在扫描一遍序列集过程中建立多阶条件概率模型;最后,提出符号序列的贝叶斯分类器,其训练算法基于最大似然法学习不同阶次模型的权重,分类算法使用各阶次的加权条件概率进行贝叶斯分类预测.在三个应用领域实际序列集上进行了系列实验,结果表明:新分类器对模型阶数变化不敏感;与使用固定阶模型的支持向量机等现有方法相比,所提方法在基因序列与语音序列上可以取得40％以上的分类精度提升,且可输出符号序列Markov模型最优阶数参考值.

摘要： 后缀树和后缀数组广泛用于生物信息学领域中,特别是通过启发式算法在对DNA基因片段进行匹配的阶段.本文提出了在GPU的平台下,利用多核和超多核体系构成的后缀树以及后缀数组并行匹配大规模基因片段,从而加速基因搜索匹配过程.相对于后缀树,后缀数组二分搜素算法具有内存占用少,缓存使用率高等优点.在GPU的性能评估中,后缀数组执行效率明显超过后缀树,后缀数组占用的空间仅为后缀树的20％～30％.相对于CPU的串行实现,后缀树组达到了约99倍的加速比.实验结果表明在基因片段匹配的过程中,基于GPU的后缀数组二分搜索是一种高效且实用的方法.%Suffix trees and suffix arrays have been used widely in bioinformatics applications,especially for DNA sequence alignments in the initial exact match phase of heuristic algorithms.In this paper,a new GPU implementation and optimization of the suffix tree and suffix array on both multi-core and many-core platforms to accelerate multiple genome sequence searching is presented.The comparative performance evaluation between the suffix tree and suffix array is then carried out.The results showed that the suffix array needed only 20％-30％ of memory space compared with the suffix tree,and that the mean search time of the suffix array was significantly shorter than the mean search time of the suffix tree because of the use of a binary search with coalesced memory access and tile optimization under the GPU architecture.Moreover,the GPU implementation of the suffix array gained a speedup of approximate 99 times compared with the corresponding CPU serial implementation.This study showed that the massively parallel sequence matching algorithm based on suffix array was an efficient approach with the high-performance in the process of multiple DNA sequence matching.

摘要： 为提高Web搜索精度和检准率,在后缀树聚类算法基本模型的基础上,提出了一种改进的基于后缀树的搜索结果聚类算法.将向量空间模型与后缀树聚类相结合,改善了基类合并的效果,综合基类节点对应文本数、短语包含词语长度、短语权重及是否包含查询词作为聚类标签的筛选条件,改进了聚类标签的合理性和可读性.以搜狗语料库中的文本分类语料库为数据源进行的实验结果表明,该方法在一定程度上提高了聚类结果的准确率.

摘要： Aiming at the problem of poor instantaneity and low accuracy in current study of dynamic measure.ment,this pa-per proposed a kind of measurement method using the program behavior feature.It constituted variable-length system call se-quences as behavior features according to the sifting and relevance analyzing of system calls generated from running program.It devised the FMUS algorithm based on suffix tree and achieved the feature matching when program was running.Experiments on the selected samples show that this method has high accuracy and low time expending rate.%针对目前程序动态度量研究中实时性与准确性较差的问题，提出了一种利用程序行为特征进行度量的方法。通过筛选程序运行过程中产生的系统调用，依据其关联特性构成非定长系统调用序列作为程序的行为特征；采用后缀树结构设计实时特征度量匹配算法（feature matching with updating suffix tree，FMUS），实现了程序运行过程中的实时特征匹配。实验表明，该方法具有较高的准确率和低时间耗费比。

摘要： 半监督文本聚类是文本聚类中的研究热点,广泛应用于数据挖掘和机器学习领域.现有基于划分和密度的半监督文本聚类算法不能适应多密度不平衡文本数据集的聚类.此外,基于向量空间的文档模型使用词或字向量表示文档特征,没有考虑到词组之间的关联性.针对以上问题,提出一种基于后缀树文档模型的半监督自适应多密度文本聚类算法.该算法基于后缀树文档模型表征文档间的相似度,使用K最近邻思想传播扩展簇标签,并在传播扩展过程中不断更新扩展阈值,以适应多密度不平衡的文本数据集.经实验验证,算法具有较高质量的聚类结果且能够适应多密度数据集.

摘要： 对检索结果进行聚类能够方便用户从搜索结果中快速的找到自己需要的信息,当前已有各种聚类方法和系统被广泛使用,但是,现有大部分方法由于聚类标签的可读性和描述性较差,难以达到预期效果.本文提出了一种新的思路,注重于如何在聚类之前就产生好的标签,在生成了标签的基础上,再进行检索结果聚类.对于搜索引擎返回的结果,我们先统一建立一棵后缀树,然后计算后缀树中各个短语的得分,选取得分最高的若干短语作为候选标签.得到标签后,将搜索引擎返回的各个结果项分配到它所包含的标签对应的分类中,形成最后的聚类.实验表明,我们的方法是比较有效的.

摘要： WEB文档聚类在新闻信息检索领域起到重要的作用。但由于新闻领域不断涌现出一些新的名词。现有的技术在文档特征抽取和权重计算、类标签生成方面存在不足,导致聚类质量下降。本文提出一种基于网络词典的后缀树聚类算法,利用网络词典来识别新的名词,排除干扰因素;在后缀树聚类计算聚类分数时利用网络词典设置词语权重,提高聚类质量;聚类结果描述利用网络词典确定聚类标签,标志聚类话题的基本类别。这种方法在新闻领域取得了很好的效果。

摘要： 本文针对形如∥element1/element2/…/elementm的查询,提出了一种基于后缀树(suffixtree)的XML索引结构SuffIndex地，SuffIndex的构造通过只对OEM数据树遍历一次以及在SuffIndex中引入后缀链(Sufflink)的方法,从而达到较低的构造代价，SuffIndex中所有结点利用Hash表保存到其所有子结点的指针,最终使查询∥element1/element2/…/elementm的处理代价为O(m)。

摘要： 随着网络信息量的迅速增长,传统的搜索引擎技术也只能为用户提越来越长的检索结果列表。用户不得不从中进行按照自己标准的二次检索.浪费了时间和效率.针对这问题,据挖掘领域中的聚类技术引入网络信息搜索中(Web聚类技术),以解决搜索引擎结果集不便于用户浏览问题为目的。本论文分析维吾尔语的词法特点,选择适合维吾尔文文本聚类的牲,构造可展后缀树,选择基类,合并基类,把维吾尔文网页按相似度分成不同的类并形成类标签。

摘要： 本发明公开了一种基于后缀树和向量机的故障检测方法、系统、装置及介质，方法包括：获取第一振动信号，通过后缀树算法对第一振动信号进行分解，得到第一重复特征波形和第一重复时间序列；根据第一重复特征波形和第一重复时间序列确定第一振动信号的第一时频特征图，并根据第一时频特征图构建训练样本集；构建支持向量机分类器；将训练样本集输入到支持向量机分类器中进行训练，对支持向量机分类器的参数进行优化，得到最优参数组合；根据最优参数组合确定分类决策函数，根据分类决策函数确定待检测的第二振动信号的故障类型。本发明提高了训练样本的准确性和可靠性，进而提高了分类器的精度和故障检测的准确度，可广泛应用于故障检测技术领域。

摘要： 本发明公开了一种基于后缀树的故障信号特征提取方法、系统、装置及介质，方法包括：获取待诊断的第一故障信号，对第一故障信号进行编码得到第一时域信号；通过后缀树算法对第一时域信号进行分解，得到多个故障波形信息和对应的时刻信息，根据故障波形信息和时刻信息构建第一后缀树；对第一后缀树的各个节点进行遍历，获取重复出现的故障波形信息作为故障重复波形，确定故障重复波形的重复时间序列；根据故障重复波形和/或重复时间序列确定第一故障信号的故障信号特征。本发明获取故障重复波形和重复时间序列两个不同尺度的信息，避免了傅里叶算法的混叠现象产生的误差，提高了故障信号特征提取的准确性和可靠性，可广泛应用于故障检测技术领域。

摘要： 本发明公开了一种基于后缀树的故障检测方法、系统、装置及存储介质，方法包括：获取第一故障信号，并通过后缀树算法对第一故障信号进行分解，得到故障重复波形和重复时间序列；根据故障重复波形和重复时间序列确定第一故障信号的第一时频特征图，并根据第一时频特征图构建训练图片集；将训练图片集输入到预先构建的卷积神经网络中进行训练，得到训练好的故障识别模型；获取待检测的第二故障信号，并通过后缀树算法确定第二故障信号的第二时频特征图，进而将第二时频特征图输入到故障识别模型，输出得到故障类型识别结果。本发明提高了训练样本的准确性和可靠性，进而提高了故障识别模型的精度和故障检测的准确度，可广泛应用于故障检测技术领域。

摘要： 本发明涉及一种基于后缀树的代码文件克隆检测方法，对工程项目文件构造后缀树，在线性时间内实现代码文件克隆检测。LP检测方案及算法是以计算机软件源代码文件内容为粒度，通过对代码文件进行词法分析过滤，并MD5哈希得到指纹值，构造指纹建立指纹库。指纹库保存在MySQL数据库中，以指纹所在的开源项目id作为索引。可以直接提取后缀树中被标记为克隆结果的节点，将这些节点直接保存到克隆结果数据表中。由此，能在线性时间内检测出克隆的代码文件，比直接按照指纹值进行检测有更高效率，实现海量检测。

摘要： 本发明公开了一种通用后缀树的分布式并行构建方法，包括以下步骤：第一步，整合输入序列并将其平均分配给每个计算节点；第二步，并行地统计子序列频数，确定所有的子树构建任务；第三步，将这些子树构建任务按规模尽量均匀地分配给不同的计算节点；第四步，分轮批量构建所有子树。每一轮批量构建可以分为以下三步：第一步，并行扫描输入以定位本轮构建任务需要的后缀并分别排序，将排序结果汇总至负责构建任务的计算节点；第二步，多路归并生成全局有序的后缀排序结果；第三步，利用排序结果生成对应的后缀子树。本发明可高效地并行构建通用后缀树，解决现有通用后缀树构建方法过于依赖I/O或主存容量、通用性不足、应对大规模输入困难等问题。

摘要： 本发明公开了一种基于后缀树的故障信号特征提取方法、系统、装置及介质，方法包括：获取待诊断的第一故障信号，对第一故障信号进行编码得到第一时域信号；通过后缀树算法对第一时域信号进行分解，得到多个故障波形信息和对应的时刻信息，根据故障波形信息和时刻信息构建第一后缀树；对第一后缀树的各个节点进行遍历，获取重复出现的故障波形信息作为故障重复波形，确定故障重复波形的重复时间序列；根据故障重复波形和/或重复时间序列确定第一故障信号的故障信号特征。本发明获取故障重复波形和重复时间序列两个不同尺度的信息，避免了傅里叶算法的混叠现象产生的误差，提高了故障信号特征提取的准确性和可靠性，可广泛应用于故障检测技术领域。

摘要： 本发明公开了一种基于后缀树的故障检测方法、系统、装置及存储介质，方法包括：获取第一故障信号，并通过后缀树算法对第一故障信号进行分解，得到故障重复波形和重复时间序列；根据故障重复波形和重复时间序列确定第一故障信号的第一时频特征图，并根据第一时频特征图构建训练图片集；将训练图片集输入到预先构建的卷积神经网络中进行训练，得到训练好的故障识别模型；获取待检测的第二故障信号，并通过后缀树算法确定第二故障信号的第二时频特征图，进而将第二时频特征图输入到故障识别模型，输出得到故障类型识别结果。本发明提高了训练样本的准确性和可靠性，进而提高了故障识别模型的精度和故障检测的准确度，可广泛应用于故障检测技术领域。

摘要： 本发明公开了一种基于后缀树和向量机的故障检测方法、系统、装置及介质，方法包括：获取第一振动信号，通过后缀树算法对第一振动信号进行分解，得到第一重复特征波形和第一重复时间序列；根据第一重复特征波形和第一重复时间序列确定第一振动信号的第一时频特征图，并根据第一时频特征图构建训练样本集；构建支持向量机分类器；将训练样本集输入到支持向量机分类器中进行训练，对支持向量机分类器的参数进行优化，得到最优参数组合；根据最优参数组合确定分类决策函数，根据分类决策函数确定待检测的第二振动信号的故障类型。本发明提高了训练样本的准确性和可靠性，进而提高了分类器的精度和故障检测的准确度，可广泛应用于故障检测技术领域。

摘要： 本发明涉及生物信息技术领域，具体涉及一种基于后缀树算法的基因组测序序列与参考基因组比对的方法。本发明提供的基于后缀树算法的基因组测序序列与参考基因组比对的方法包括构建参考基因组索引以及将基因组测序序列与参考基因组索引进行序列比对的步骤，其中，所述构建参考基因组索引包括如下步骤：(1)构建参考基因组索引的初步后缀树；(2)将所述初步后缀树中含有分叉的节点转换成节点数字，不含有分叉的节点转换成节点矩阵，构建后续用于比对的最终后缀树。本发明提供了一种占用内存相对较小、运行速度较快的、基于后缀树算法进行序列比对的方法，有效降低了读入索引对计算机内存的要求。

摘要： 本发明公开了一种基于后缀树误差有界的轨迹预测方法。历史轨迹输入到深度学习模型中进行处理获得预测轨迹，将历史轨迹存储到后缀树中，当有新的预测请求时，在后缀树中找到相似的轨迹作为预测结果，由后缀树直接返回预测结果。本发明能在后缀树中找到相似轨迹，由后缀树直接返回预测结果，无需进入神经网络进行预测，极大提高了轨迹预测的效率。