DNA序列中基于后继数组索引的SATR查找算法

研究了基因序列分析中的DNA序列相似性重复片段的查找问题.在对重复片段的相似性衡量进行分析之后,基于海明距离提出了新的相似度衡量标准模式相似度和片段相似度,并在此基础上提出了一个新的相似性重复片段的定义SATR(segment-similarity based approximate tandem repeats).在进行SATR的查找时,采用了一个轻量级的索引后继数组,并设计出在后继数组上进行SATR查找的算法.实验评估和性能分析表明,基于后继数组的SATR查找算法在查找结果和查找时间上都要优于其他同类方法.     

基于改进哈夫曼编码的全文索引结构压缩算法

为解决全文索引的索引结构压缩问题,提出了文本的基于正规哈夫曼编码小波树形式,并将该结构与后缀数组结合,实现了基于正规哈夫曼编码的小波树和高效构造算法.实验结果表明,在不降低运行效率的前提下,存储空间得到有效的压缩,从而证明了改进方法的有效性.     

基于链表结构的多维动态数组设计方法

针对动态数组生成中难以适应任意维数、任意数据类型、索引数据不够灵活等问题,提出一种基于链表结构的多维动态数组设计方法.该方法通过链表进行索引,采用变长参数列表技术动态生成数组.结果表明,该方法能够生成任意维动态数组;适用任意的数据类型;既能够直接利用数组下标索引数据,也能够对数据进行线性访问.与以往动态数组生成方法相比,更易于扩展,使用更加灵活.     

文本检索中动态索引技术研究

分析了当前信息检索多是建立在语词匹配基础上的搜索,索引库不断增大,搜索时间长等问题.通过对文本检索步骤和索引结构的研究表明,索引结构是决定文本检索效率的关键.提出对动态索引结构B+树进行改进,通过改进减少了索引层数,提高了检索速度,降低了索引存储空间,研究结果对改进文本检索效率具有积极意义.     

基于后缀数组改进的全文索引结构研究

为在网络数据中搜索到所需相关数据, 通过对基于后缀数组的全文索引结构的改进研究, 设计和实现一种降低空间占用率并有效提高索引速度的全文索引结构加权有向词图。通过实验证明, 加权有向词图在相同问题规模下能降低存储空间, 同时不影响检索的效率, 是一种更为高效的全文索引结构。     

面向真三维地学建模的海量虚拟八叉树模型研究

高分辨率和海量数据是真三维地学属性建模所面临的关键问题,传统的指针八叉树、线形八叉树及其变种模型在这方面存在不足,存储空间大、处理效率低.作者提出一种多级线性结构、无指针/无位置码的海量虚拟八叉树模型,采用基于规则分块的多级压缩机制实现了海量属性数据的高效压缩和组织,采用基于快速Morton码分解和数组访问的多级索引方式实现了属性数据的高效查询.新模型在内存和外存中具有统一的压缩原理、索引结构和查询机制,以数据块为基本单位进行数据交换,给出了具体的实现方法.应用实例表明,新模型能够有效处理海量属性数据,对于大范围、高精度的真三维地学属性建模及其分析具有重要的应用价值.     

图像分层优化二元树表示及其转换研究

本文在分析图像分层表示的基础上,提出一种图像分层优化二元树结构表示.该优化二元树结构比指针二元树结构及指针四元树结构简单,多幅图像试验结果表明,该结构比指针二元树数据结构及指针四元树数据结构占用存储空间少.文中还研究了图像从二维数组表示到优化二元树结构表示的转换算法,图像显示结果表明,图像完全一样.     

利用水平分割法计算给定串中的所有Maximal(NE/SNE) Repeats

提出一种利用给定符号串x［1…n］的后缀数组和最 长公共前缀数组求x所有最大重复的新方法〖CD2〗水平分割法. 通过对x的最大不可扩展重复和最大超级不可扩展重复所有可能出现的位置以及判定条件的提炼, 分别给出仅由x的后缀数组和最长公共前缀数组求x的所有最大重复、 最大不可扩展重复和最大超级不可扩展重复的算法. 该算法克服了除后缀数组和最长公共前缀数组外, 还需利用其他辅助数组的缺陷, 降低了空间开销, 且时间复杂度没有增加, 并可以在对最长公共前缀数组仅进行一次扫描的情况下求出给定串的所有最大重复、 最大不可扩展重复和最大超级不可扩展重复.     

面向真三维地学建模的海量虚拟八叉树模型研究

高分辨率和海量数据是真三维地学属性建模所面临的关键问题,传统的指针八叉树、线形八叉树及其变种模型在这方面存在不足,存储空间大、处理效率低。作者提出一种多级线性结构、无指针/无位置码的海量虚拟八叉树模型,采用基于规则分块的多级压缩机制实现了海量属性数据的高效压缩和组织,采用基于快速Morton码分解和数组访问的多级索引方式实现了属性数据的高效查询。新模型在内存和外存中具有统一的压缩原理、索引结构和查询机制,以数据块为基本单位进行数据交换,给出了具体的实现方法。应用实例表明,新模型能够有效处理海量属性数据,对于大范围、高精度的真三维地学属性建模及其分析具有重要的应用价值。     

重复数据删除中的无向图遍历分组预测方法

针对重复数据删除系统中存储容量受内存限制难以进行扩展的问题,提出了一种基于无向图遍历的重复数据删除分组预测方法.该方法将索引表保存在磁盘中,并在内存中维护索引表缓存,以此提高系统最大可支持的存储容量.对于索引表缓存命中率低、系统性能差的问题,采用了图遍历分组方法予以解决,根据数据块访问序列特征信息建立无向图并进行分析,基于分析结果对索引项进行分组,并以组进行缓存替换,从而提高缓存命中率和系统性能.实验结果表明,基于缓存预取原理和无向图遍历分组,在将缓存设置为索引表大小的10％时,重复数据删除存储系统最大存储容量比原有方法提高了7.5倍,缓存命中率由不进行索引项分组时的47％提高到87.6％.     

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

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

基于后缀树思想构造Web生物数据搜索的数据模型

针对Web上的公共生物学数据资源,提出一种适合于在线搜索生物学数据的数据模型.该模型基于后缀树思想,通过建立生物体的DNA、RNA、蛋白质序列数据的后缀树结构,并将之转化为更加空间有效的后缀数组,然后搜索数组以找到查询序列的近似匹配.结果表明,这种数据模型比常规的线性搜索模型在时间和空间开销上更加高效.     

改进的基于后缀树的Web搜索结果聚类算法

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

Canonical Huffman code based full-text index

Full-text indices are data structures that can be used to find any substring of a given string. Many full-text indices require space larger than the original string. In this paper, we introduce the canonical Huffman code to the wavelet tree of a string T[I...n]. Compared with Huffman code based wavelet tree, the memory space used to represent the shape of wavelet tree is not needed. In case of large alphabet, this part of memory is not negligible. The operations of wavelet tree are also simpler and more efficient due to the canonical Huffman code. Based on the resulting structure, the multi-key rank and select functions can be performed using at most nHo＋│∑│（lglgn＋lgn-lg│∑│）＋O（nHo）bits and in O（Ho） time for average cases, where Ho is the zeroth order empirical entropy of T. In the end, we present an efficient construction algorithm for this index, which is on-line and linear.     

基于后缀树的图像识别研究

分析了后缀树在一维和二维字符串处理方面的优势．以后缀树为索引，将后缀树和最低公共祖先问题相结合，提出了一个在仅考虑平移变换操作的条件下．进行图像精确识别的算法，并从时间复杂度上证明了其优于传统的二：维精确模式匹配算法。     

ISTC： A New Method for Clustering Search Results

A new common phrase scoring method is proposed according to term frequency-inverse document frequency （TFIDF） and independence of the phrase. Combining the two properties can help identify more reasonable common phrases, which improve the accuracy of clustering. Also, the equation to measure the in-dependence of a phrase is proposed in this paper. The new algorithm which improves suffix tree clustering algorithm （STC） is named as improved suffix tree clustering （ISTC）. To validate the proposed algorithm, a prototype system is implemented and used to cluster several groups of web search results obtained from Google search engine. Experimental results show that the improved algorithm offers higher accuracy than traditional suffix tree clustering.     

基于后缀树的网页聚类算法性能改善研究

网页聚类技术是快速定位搜索引擎返回结果中用户最需要资料的方法。基于后缀树聚类算法是利用网页集中共享的短语来对网页集进行聚类。本文研究怎样充分利用后缀中的共享短语之间的关系提高后缀树性能的方法。     

基于分类树的高效关联规则挖掘算法

在分析类Apriori算法存在效率瓶颈的基础上，提出了一个高效改进算法——基于分类树的关联规则挖掘算法．该算法只需要两次访问数据库，把数据库中的数据利用分类树来存储，减少了访问数据库的次数；并且由分类树的全部或部分来求得频繁项目集，减少了求频繁项目集的比较次数．此算法通过结合Apriori和FP—tree两种算法来提高挖掘效率，降低了挖掘算法的时间复杂度和空间复杂度．通过多次试验证明该算法比Apriori及其改良算法的挖掘效率高2到8倍．     

半导体晶圆生产线调度的性能指标体系研究

针对半导体晶圆生产线调度，提出了由用于日生产计划的调度方案对比的短期性能指标，和用于每日投料计划的、实施分析的长期性能指标组成的半导体晶圆生产制造系统的性能指标体系．其中，短期性能指标分为与产品有关的在制品值、移动步数和移动速率，以及与设备有关的设备利用率、负载程度、排队队长和瓶颈率；长期性能指标主要包括产品的加工周期、流程参数和生产率．在此基础上，设计并实现了半导体晶圆生产线调度性能评价系统，以指导半导体车间的实际生产．该系统已经在工厂中得到应用．