一种改进的基于广义后缀树的文本聚类算法

分析了基本STC算法存在的三个缺点,即不能有效处理包含文本数目差距较大但具有包含关系的节点,不能有效处理包含文本相似但主题不同的节点,缺乏有效的类别标识提取算法。针对以上问题,在综合考虑主题相似性以及文本包含相似性的基础上,给出了改进的用于基类合并的相似度公式,并提出基于信息增益的类别标识提取算法。为了进一步提高聚类效率,给出了一种简单有效的用于基类选择的测度,用来排除一些无意义的广义后缀树节点。实验结果表明,所提算法不仅可以有效提高STC算法的聚类准确度,而且可以对聚类结果进行有效的类别标识。

一种新的加权后缀树Web文档聚类方法

针对Web文档的结构及其特征,提出了一种新的加权后缀树聚类方法WSTC。首先,根据Web文档的HTML标签,把文档划分为具备不同重要性等级的段,段划分成句子,句子分割为词。其次,用句子替代文档构造后缀树,把其重要性等级作为结构权融入后缀树的节点,形成文档集的加权后缀树模型。最后,在选择和合并基类过程中,综合利用节点包含的文档数、句子数、短语长度和结构权。仿真实验表明,WSTC算法比传统STC算法取得了更好的聚类效果。

基于邻接字符对的三元后缀树全文索引模型

传统后缀树全文索引模型的索引建立复杂、难以维护,且空间消耗大。为此,提出一种改进的后缀树全文索引模型。将一棵完整后缀树划分为若干个三元后缀树,从而简化后缀树的组织结构,便于其建立和维护索引。将邻接字符对的公共前缀作为后缀树的根结点,以降低模型的空间消耗,提高查询效率。实验结果表明,与传统模型相比,该模型具有较高的时空效率。

SuffIndex——一种基于后缀树的XML索引结构

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

基于后缀树模型的文本实时分类系统的研究和实现

本文在面向网络内容分析的前提下,提出了一种基于后缀树的文本向量空间模型(VSM),并在此模型之上实现了文本分类系统。对比基于词的VSM,该模型利用后缀树的快速匹配,实时获得文本的向量表示,不需要对文本进行分词、特征抽取等复杂计算。同时,该模型能够保证训练集中文本的更改,对分类结果产生实时影响。实验结果和算法分析表明,我们系统的文本预处理的时间复杂度为O(N),远远优于分词系统的预处理时间复杂度。此外,由于不需要分词和特征抽取,分类过程与具体语种无关,所以是一种独立语种的分类方法。

基于概率后缀树的移动对象轨迹预测

在移动对象轨迹预测中,针对低阶马尔可夫模型预测准确率不高、高阶模型状态空间膨胀的问题,提出一种基于概率后缀树(PST)的动态自适应变长马尔可夫模型预测方法。首先依时间先后将移动对象的轨迹路径序列化;然后根据移动对象的历史轨迹数据进行学习训练,计算序列上下文的概率特征,建立路径序列的概率后缀树模型,结合当前实际轨迹数据,动态自适应预测将来的位置信息。实验结果表明,该模型在二阶时取得最高的预测精度,随着阶数的增加,预测精度保持在82%左右,能取得较好的预测效果;同时空间复杂度呈指数级减少,大大节省了存储空间。该方法充分利用历史轨迹数据和当前轨迹信息预测未来轨迹,能够提供更加灵活、高效的基于位置服务。

一种基于后缀树的中文网页层次聚类方法

为了便于用户浏览搜索引擎产生的搜索结果,结合STC算法和变色龙算法提出了一种中文网页的层次聚类方法-STCC算法。该方法采用雅可比系数修改了STC算法中基本类相似度的计算方法,然后根据基本类相似度矩阵,利用变色龙算法完成网页聚类。实验结果表明:STCC算法与STC算法相比,聚类精度提高将近10%,避免了单链接算法的链式效应,适用于大规模网页聚类。

基于后缀树的Web论坛信息抽取

针对现有网上论坛信息抽取的不足,提出一种基于后缀树的论坛信息抽取方法。将标准化后的HTML文档转换为后缀树,查找出其中的重复模式并产生分装器,将分装器转换为NFA(非确定型有穷自动机)达到抽取论坛信息的目的。该方法运用构造后缀树的技术来抽取论坛信息,较好地解决了现有的抽取方法准确性较差、通用性不强的问题。实验结果表明,该方法具有较高的准确性和实用性。

基于概率后缀树的股票时间序列预测方法研究

在时间序列符号化基础上,本文引入概率后缀树PST模型,构建基于时间序列符号化和概率后缀树相结合的股票预测模型.本文选择在沪深300的10支股票数据上将预测模型与传统的马尔科夫模型MM和自回归移动平均模型ARMA进行对比,结果显示本文提出的股票预测模型优于MM模型和ARMA模型,验证了本文所提出的预测模型在投资收益上的有效性.

一种基于后缀树的Web访问模式挖掘算法

在Web使用挖掘中,分析用户的行为模式是一个关键的问题。文中提出了一种基于后缀树的最大频繁序列MFS(MaximalFrequentSequences)的有效挖掘算法,该算法能够从增量数据中动态发现和输出MFS。

并行后缀树的构造及查询算法

针对生物信息领域中传统后缀树构造算法在时间和空间上的限制,从结构并行的角度提出了一种新颖的、适用于生物信息学应用的并行后缀树结构和相应的构造算法·该算法首先将给定字符串分成若干连续的片段,并在各个处理机上分别构造这些片段的后缀树,形成了一种分布于多个处理机上的并行后缀树结构·该并行算法不仅大大缩短了后缀树的构造时间,而且避免了主存大小的限制·经分析,其性能优于现有的任何一种并行算法·在此基础上,提出了一种高效的基于这种并行后缀树的字符串匹配算法,解决了传统后缀树的基本查询问题·

概率后缀树在入侵检测中的应用研究

系统调用序列能够反映系统进程的行为特征。而系统调用序列中每个调用的出现都与它之前出现的若干个调用相关。因此可以利用概率后缀树(PST)对系统调用序列建模,反映系统调用基于上下文的概率特性。提出了系统调用序列异常度的定义。在进行序列的异常检测时,先利用正常系统调用序列训练PST模型,然后通过该模型,利用计算未知系统调用序列的异常度,根据给定的阈值判断该序列是否异常。实验表明这一度量对于正常进程与异常进程有着良好的区分效果。

一种基于后缀树的Web搜索结果聚类方法

为同时满足Web搜索结果聚类的关联性、快速性以及类别描述的可浏览性等需求，本文提出了一种适合中文Web信息搜索结果的后缀树聚类算法，其中后缀树的构建以中文汉字为基本单位，一种有效的策略解决了基于二进制方法合并短语类后的类别描述问题，利用短语类语义层面的相似性合并同义短语类，有效地改善了聚类结果的质量。测试结果表明：与传统的文档聚类算法相比，基于后缀树的算法在Web文档聚类的精度和效率方面具有较强的优越性。

基于后缀树词序列核挖掘Web文档

通过将文档表示为一棵后缀树,文章提出一种基于后缀树索引计算文档相似度的词序列核。首先根据文档的词序列构造出后缀树,然后根据后缀树词序列核计算文档间的相似度,最后利用支持向量机对文档进行分类。理论分析表明后缀树词序列核的计算只与比较文档的长度成线性关系,大大减少了序列核的计算时间。在reuters-21578文档集上将后缀树词序列核与词序列核、多项式核进行比较,实验结果表明在改善速度的同时,后缀树词序列核可达到与词序列核相当的性能,优于多项式核,更适于Web文档挖掘等应用。

基于后缀树的文本聚类算法

提出一种基于后缀树的文本聚类算法以实现中文文本的多主题聚类。先介绍基于后缀树的英文多主题聚类的主要流程。再分析中、英文语言的差异,并以中文词和短语为单位构造后缀树模型,随后构造基类关联图实现中文多主题聚类。实验分析表明,该方法能快速、较准确的实现中文文本的多主题聚类。

DNA序列中基于适应性后缀树的重复体识别算法

现有的在DNA序列中识别重复体的算法多数是基于比对的,对识别速度和吞吐量有很大的限制.针对这个问题文中根据一个平衡重复体的长度和频率的定义,提出了一种基于Ukkonen后缀树的快速识别重复体的RepSeeker算法.算法采用最低限制频率,最大程度地扩展了重复体的长度,同时为了进一步地提高RepSeeker算法的效率,对Ukkonen的后缀树构造算法进行了适应性改进,在构造时加入RepSeeker算法所需的结点信息并将叶子结点和分支结点加以区分,从而使得RepSeeker算法能通过直接读取结点信息来求得子串频率和子串位置.这种改进较大地提高了RepSeeker算法的性能,而且空间开销不大.实验中使用了NCBI中的9条典型DNA序列作为测试数据,并对后缀树改进前后的重复体识别算法做了比较分析.结果表明,RepSeeker在没有损失精度的情况下缩短了算法的运行时间.实验结果与理论上的分析一致.

基于后缀树的中文新闻重复网页识别算法

针对识别中文新闻重复网页传统方法的不足,提出以后缀树作为基本数据结构,依据新闻网页的标题性和时间性,构建中文新闻重复网页识别算法。该算法以Ukkonen算法和Matching Statistics算法为基础,并对其具体实现进行优化。实验结果表明,该算法不仅具有有效性,而且对计算字符串相似度也有启发意义。

基于后缀树的程序理解Plan自动提取

为辅助维护用于程序理解的代码片段模版(Plan)库,提出了基于后缀树的Plan自动提取方法.通过词法/语法分析将源代码转换成Token串,然后对Token串生成后缀树,遍历后缀树得到候选代码Plan集,过滤后生成更小、更准确的Plan集.采用动态模式匹配合并合适的Plan和给Plan命名,最后生成可用于程序理解的Plan.由于后缀树的线性增长特性,该方法可以应用于大规模软件的程序理解.将方法应用于多个不同规模的软件,测试结果表明,该方法可以从源码中提取有效的Plan.

基于广义后缀树的二分网络社区挖掘算法

近年来,二分网络的社区挖掘问题得到了极大的关注。提出了一种基于广义后缀树的二分网络社区挖掘算法。首先从二分网络的邻接矩阵中提取网络中每个节点的链接节点序列,然后构建广义后缀树。广义后缀树的每个节点表示二分网络的一个完全二分团,由此获取并调整完全二分团。通过引入二分团的紧密度得到初始的社区划分,最后再对孤立点进行处理以得到最终的社区划分。所提算法不仅能发现重叠社区,而且能得到一对多关系的社区。在人工数据集和真实数据集上的实验表明,所提算法能准确地识别二分网络中的社区个数,获得很好的划分效果。

基于非压缩后缀树的在线PPM预测模型

PPM模型适合预测用户的下一个请求,但已有的PPM模型不具备在线性,更新通过重构来实现,不能满足实时更新的要求。该文提出基于非压缩后缀树的在线PPM预测模型,采用非压缩后缀树实现增量式在线更新,提高了模型的更新速度。该模型的优点是具备在线性。