最大频长积字符串及其高效查找算法

在传统的字符串处理算法中往往分别考虑字符串的频度和长度.然而,在实际应用中,将字符串的频度和长度结合考虑是有意义的.基于这点我们提出了频长积的概念,规定字符串的频度和长度的乘积为字符串的频长积.并基于广义后缀树和Ukkonen算法,提出了时间复杂度为O(N)的查找算法.效率实验证实了该算法的高效性.语义实验表明,本算法找出的最大频长积字符串相比于最大频度字符串或最大长度字符串,其实际语义更为明确.这样的字符串在文本压缩、基因序列的分析以及其他注重语义的应用中将具有很高的应用价值.     

多语种网络文本快速新词抽取

从网络文本中提取新词是网络信息处理中的一个重要问题,在信息检索、文本挖掘、词典编纂、中文分词等领域中都有重要应用。本文提出了一种与语言无关的快速新词提取算法,首先针对后缀树的数据结构将多语言文本进行统一编码,然后使用改进的统计方法在双后缀树上以线性时间统计重复串与邻接类别,并计算字符串的整体度,同时通过剪枝大幅度减少计算量,在中、英文语料上较好地实现了新词的抽取及排序。     

基于逐层剪枝的中文高频重复模式快速提取算法

为了从大规模语料中快速提取高频重复模式,以递增n-gram模型为基础,使用散列数据结构提取重复串,并提出了一种基于低频字符和层次剪枝的逐层剪枝算法,用于过滤低频垃圾字串,减少I/O读写次数。在此基础上,应用改进的字串排序算法,使字符串排序可在O(n)时间内完成,从而有效提高重复模式的提取效率。实验表明,该算法是一种有效的重复模式提取算法,其I/O读写次数同语料规模呈线性关系,远小于使用首字符进行语料划分的方法,能快速有效地从规模远大于内存容量的文本语料中提取重复模式,特别适合于大规模语料的高频重复模式提取,对以重复模式为基础的新词识别、术语抽取等具有重要的支撑作用。     

求最长公共子串问题的算法分析

高效求解2个字符串的最长公共子串(Longest Common Substring)是实现很多字符串算法的关键.文中首先给出了求解LCP问题的动态规划算法,广义后缀树算法,研究并分析了这两种算法,得出动态规划算法易于理解,但时间复杂度较高;广义后缀树算法的时间复杂度较低,但实现较为复杂并且广义后缀树占用的空间也较多.最后提出了一个新算法,该算法使用2个字符串的广义后缀数组,在保持和广义后缀树时间复杂度相等的基础上,可以简单地实现并且占用较少的空间.     

一种有效的序列模式增量式更新方法

针对序列模式增量式更新挖掘算法产生大量候选项集以及多次扫描数据库的问题,提出了一种有效的增量式更新算法ESPIA,该算法利用基于2-序列矩阵挖掘算法ESPE对原数据库和增加数据库一次扫描产生序列模式,通过对频繁模式和非频繁模式进行相应的剪枝减少了序列的比较和扫描次数,降低了算法时间和空间复杂度,实验证明该算法是有效和准确的。     

连续时间区间内的频繁词序列挖掘算法

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

基于CTID序列模式的一种改进算法

提高序列模式挖掘算法效率的关键在于减少发现频繁序列的时间。文中基于CTID概念提出了一种改进的频繁序列模式挖掘算法——SPM，它充分利用频繁项集和中间挖掘结果，得到更多有效的序列模式，并简化了剪枝步骤，从而提高了算法效率。实验证明该算法可行。     

基于CTID序列模式的一种改进算法

提高序列模式挖掘算法效率的关键在于减少发现频繁序列的时间.文中基于CTID概念提出了一种改进的频繁序列模式挖掘算法--SPM,它充分利用频繁项集和中间挖掘结果,得到更多有效的序列模式,并简化了剪枝步骤,从而提高了算法效率.实验证明该算法可行.     

基于时间序列的模式表示挖掘频繁子模式

论文提出了一种基于时间序列的模式表示挖掘时间序列中频繁子模式的算法(TSFSM)。时间序列的模式表示本身就具有压缩数据、保持时间序列基本形态的功能,并且具有一定的除噪能力。在时间序列的模式表示的基础上挖掘其频繁子模式,可以大大提高挖掘的效率和准确性,达到事半功倍的效果。在该算法中,还使用了一定的剪枝策略,使得算法的时间复杂度进一步降低。并且该算法计算简单,实现方便,可以支持时间序列的动态增长。     

频繁模式挖掘中的剪枝策略

本文在研究已有剪枝策略的基础上,提出一种基于堆栈的多层回退剪枝新技术,并给出一个采用该剪枝策略的最大频繁模式挖掘算法。分析与试验证明,该算法大大削减了搜索空间,效率优于已有同类算法。     

A space efficient solution to the frequent string mining problem for many databases

The frequent string mining problem is to find all substrings of a collection of string databases which satisfy database specific minimum and maximum frequency constraints. Our contribution improves the existing linear-time algorithm for this problem in such a way that the peak memory consumption is a constant factor of the size of the largest database of strings. We show how the results for each database can be stored implicitly in space proportional to the size of the database, making it possible to traverse the results in lexicographical order. Furthermore, we present a linear-time algorithm which calculates the intersection of the results of different databases. This algorithm is based on an algorithm to merge two suffix arrays, and our modification allows us to also calculate the LCP table of the resulting suffix array during the merging.     

基于功能词缀串的维吾尔语词性标注方法

维吾尔语作为一种典型的黏着语,通过丰富的功能词缀来表达各种语法和语气。该文探讨了“词干词性标注方法”与“词缀词性标注方法”在维吾尔语自然语言处理中的优缺点。在大规模语料库中,统计了常用词缀串的数量、频次和覆盖度,以此来判断词缀词性标注方法在自然语言处理中的可行性。以力提甫·托乎提教授的维吾尔语生成语法理论为指导,对词缀串的词性标注进行了相应的语法定义,并且在实际语料中进行了小规模词性标注实验。该文提出的基于词缀串的词性标注方法不仅适用于维吾尔语,也适用于有着大量相似词缀的突厥语族其他语言。     

基于外部排序的字串左右熵快速计算方法

左右熵在自然语言处理领域有着广泛应用,但目前尚无有效方法实施大规模语料中海量模式的左右熵快速计算。提出了一种计算方法,对于某长度字串计算熵,首先按长度提取语料中的全部字串,使用外部排序和归并获取字串的出现频率,然后分别剔除首尾字符构造待计算字串的频率提供文件,最后使用文件记录频率对比来计算右熵和左熵。分析和实验表明,该方法的计算量同语料规模成线性关系,适于大规模语料中海量字串的左右熵计算。     

一种基于逐层扫描的频繁字串快速提取算法

串频统计是一种简便有效的抽取未登录词方法.本文提出了一种快速的频繁字串提取和计频方法,通过逐层扫描快速发现频繁字串,修正字串有效出现频次,最后抽取平均互信息量达到阈值的字串.实验结果显示该方法有效可行.     

无词典高频字串快速提取和统计算法研究

本文提出了一种快速的高频字串提取和统计方法。使用Hash技术,该方法不需要词典,也不需要语料库的训练,不进行分词操作,依靠统计信息,提取高频字串。用语言学知识进行前缀后缀等处理后,得到的高频字串可以作为未登录词处理、歧义消解和加权处理等的辅助信息。实验显示了该方法速度较快且不受文章本身的限制,在处理小说等真实文本时体现了较高的可用性。     

章回小说的有意义串发现算法

已有有意义串发现算法对于大规模语料中频繁出现的有意义串发现效果较好,而对于语料规模小,或者出现频次较低的有意义串识别效果不够理想。根据章回小说有意义串出现的特点,提出有意义串的局部性原理,并给出了字符串局部性的有效度量方式。将字符串的局部性和语用独立性结合起来,使用局部性和独立性共同描述字符串为有意义串的可能性。实验结果表明：该方法对于章回小说有意义串发现的准确率高于已有方法,同时能够更有效地发现较多的低频有意义串。     

基于统计和浅层语言分析的维吾尔文语义串快速抽取

该文提出了一种基于统计和浅层语言分析的维吾尔文语义串快速抽取方法,采用一种多层动态索引结构为大规模文本建词索引,结合维吾尔文词间关联规则采用一种改进的n元递增算法进行词串扩展并发现文本中的可信频繁模式,最终依次判断频繁模式串结构完整性从而得到语义串。通过在不同规模的语料上实验发现,该方法可行有效, 能够应用到维吾尔文文本挖掘多个领域。     

An incomplex algorithm for fast suffix array construction

The suffix array of a string is a permutation of all starting positions of the string's suffixes that are lexicographically sorted. We present a practical algorithm for suffix array construction that consists of two easy‐to‐implement components. First it sorts the suffixes with respect to a fixed length prefix; then it refines each bucket of suffixes sharing the same prefix using the order of already sorted suffixes. Other suffix array construction algorithms follow more complex strategies. Moreover, we achieve a very fast construction for common strings as well as for worst case strings by enhancing our algorithm with further techniques. Copyright © 2006 John Wiley & Sons, Ltd.     

An efficient index structure for XML based on generalized suffix tree

A novel index structure based on the generalized suffix tree (PIGST) is proposed. Combined with post lists, PIGST can answer both structural and content queries. The distinct paths in an XML collection are mapped into strings. The construction algorithm of the PIGST for the path strings is presented based on the modification and improvement of a well-known suffix tree construction algorithm that only requires linear time and space complexity. The query process merely needs m character comparisons for direct containment queries, where m is the length of a query string. An efficient processing method for the indirect containment queries that avoids the inefficient tree traversal operation is also presented. Experiments show that PIGST outperforms earlier approaches.