一种高效的全文检索索引技术*

针对目前比较流行的基于词的倒排文档索引模型,结合全文检索数据的特点,提出了变长编码的索引压缩算法。利用该压缩编码,研究了基于内存缓存的快速创建索引的流程。通过实验,对索引膨胀率、创建时间和检索响应速度进行了对比分析,表明该技术提高了索引的空间与时间效率。     

编码单位可变的倒排索引压缩算法研究

倒排索引是大多数大型文本搜索系统的核心数据结构，索引压缩可以有效地减少倒排索引的空间占用，提升检索效率。针对倒排索引压缩算法中的字节对齐编码进行研究，对于其压缩率不够优秀的问题，提出了分区可变单位编码（PVU编码）。算法以可变单位方式代替固定字节存储，使实际存储空间更加贴合原码长度，从而提高压缩效果。针对序列均匀分区并非最优分区的问题，提出将最优分区问题转化为图论中最短路径问题的方法，使用Dijkstra算法求解序列的最优编码分区。通过对比实验验证了改进优化的PVU编码相较于传统的字节对齐编码能够更好地压缩倒排索引序列。     

用改进的游程编码方法压缩值索引

为了进一步提高采用游程编码方法压缩值索引的效率,针对原有方法的不足之处,采取了两个改进措施,一是在索引前排序被索引的数据表使得值索引中的0串和1串更长,二是改进现有编码算法使之可以同时压缩0串和1串。实验结果表明,采用改进后方法压缩值索引形成的压缩文件体积仅为采用原有方法时的11.83%。     

WSNs中状态数据的n位索引编码式数据融合

通过对节点状态数据的分析设计了一个特殊的包格式,这样可以避免发送节点的节点号;对节点的数据进行聚类处理,可以划分出大概率的数值,并有利于提高n位索引编码压缩的效率;为了减少节点状态数据的编码位数,再对所有的数据进行n位索引编码压缩操作,这样可以大大降低数据传输量。     

基于PATRICIA-TRIES的XML路径索引设计

随着XML逐渐成为Internet数据表示与交换的标准，如何快速准确地访问XML文档中的数据已成为亟待解决的关键问题，建立路径索引是提高查询效率的一种重要手段．本文设计了一种基于PATRICIA-TRIES的路径索引，简称PT索引．该索引有如下特点：一、基于PATRICIA-TRIES结构，实现快速检索．二、采用压缩编码能够将路径索引放入内存，三、索引含有结构和文本信息，通过查询索引就能提供结果，无需打开原文档．其后，分析了PT索引的时间和空间复杂性，并与三种的典型的索引结构进行了对比实验，结果证明了其在路径查询方面具有更高的效率．     

基于SOM和统计检验的语音特征索引技术

本文在深入介绍线性预测编码、倒谱及Gabor滤波法等三种语音特征抽取方法的基础上,提出基于SOM和统计检验的索引、分段索引以及二重索引的方法用于多媒体声音的自动检索。该方法弥补了传统索引方法的不足,适应语音特征,有效地将语音特征动态索引。仿真结果显示,该方法的查询效率要远远优于顺序查找,基本达到了特征索引的要求。     

空间数据在嵌入式导航系统中的索引

研究了基于嵌入式Linux平台电子地图数据的空间索引,介绍了空间索引的基本方法。通过分析常见的空间索引算法如B树、R树、四叉树等算法的特点,结合嵌入式电子地图数据特点,设计了基于Hilbert编码的格网空间数据索引机制,并改进了格网索引的数据结构,从而提高了索引效率;并使用嵌入式数据库SQLite管理空间数据,达到了预期效果。     

倒排索引中的文档序号重排技术综述

倒排索引作为文本搜索的核心索引技术,广泛应用于搜索引擎、桌面搜索和数字图书馆领域。倒排索引由字典和对应的倒排表组成,倒排表一般采用差值存储和整数编码进行压缩。研究表明,当倒排表具有较好的局部连续性时,上述方法能够获得很高的压缩率。整数编码研究通过不断改进编码算法来充分利用倒排表的局部连续性特征,而文档序号重排正是一种对文档序号重新排列来产生局部连续性的技术。通过文档序号重排,索引压缩率得到显著提高。该文主要介绍近年来文档序号重排技术取得的研究成果: 首先介绍索引压缩的基本原理,然后详细介绍文档序号重排技术,包括分析、对比各个方法的优劣;最后对文档序号重排技术进行总结、整理和展望。     

一种易于硬件实现的小波图像压缩算法仿真

SPIHT算法是压缩效率很高的静止图像压缩编码算法,但需要使用三个集合链表来存储已编码信息,内存需求大及难于硬件实现。据此,提出一种改进的易于硬件实现的小波图像压缩算法。该算法引入了线性索引技术和LZC算法标志位图,采用了类似于SPIHT算法的扫描顺序,将待编码流按不同种类进行算术编码。仿真实验结果表明,该算法的峰值信噪比优于LZC算法,略低于SPIHT算法,但对内存需求仅为SPIHT算法的二十分之一,易于硬件实现。     

基于字典的保序字符串压缩改进方法

传统基于字典的保序字符串压缩方法对数据的压缩和解压时间较长。为此,对编码索引CS-Prefix-Tree进行改进,根据字符串出现的概率,设计一种新的解码索引,从而减少查找时间,提高压缩性能。实验结果表明,与传统方法相比,改进方法的创建时间减少1/3,较大地降低内存消耗,查找时间降低近30%。     

一种支持动态XML文档上关键字查询的索引结构

在关键字查询领域,目前提出的大多数索引结构主要考虑的是静态的XML文档.当XML文档出现频繁更新时,这些索引结构可能面临着大范围的重新编码,从而增加了数据库索引维护的代价.为了能在XML文档动态更新的环境下保持其索引结构的稳定,提出了一种支持动态XML文档上关键字查询的索引结构DLSS( DDE Level Structure Summary).该索引结构采用了一种针对动态更新改进的Dewey编码,该编码只需在文档更新时对新的节点赋予相应的编码,而不需要调整原有的编码结构.实验证明,DLSS索引结构可以在XML文档频繁更新或者较少更新时都能保持索引结构的相对稳定,并能在其上实现较高的关键字查询效率.     

一种基于间接索引桶的OLAP查询算法

提高多表连接和聚集操作性能是OLAP查询中的关键问题之一。本文提出了一种基于间接索引桶的OLAP分组聚集查询算法MIBGA。该算法将维层次编码和事实表标识符分组集合进行有效结合，用间接索引桶代替目前流行的位图连接索引，并通过分组属性位图的位操作方式来快速完成OLAP查询。分析表明，该方法压缩了索引的存储空间，减少了I／O开销，有效地提高了多表连接的查询效率。     

一种改进的XML压缩树索引技术

压缩树索引技术是XML数据压缩的热点问题之一,本文提出一种压缩树索引改进方法.针对压缩树在查询过程中不能很好的解决向上匹配与向下匹配的问题,改进方法引入正排索引和倒排索引.当查询到组一级时,利用正排索引可以快速的查找出以该组为父节点的子组.而选出符合值谓词的元素后,在进行向上匹配时利用倒排索引可找出该元素的父节点.新的索引方法在保留原压缩树索引优点的基础上,解决了压缩树索引在查询过程中匹配问题.     

全文检索字索引技术的研究与实现

针对中文全文检索字表法检索索引的创建，提出了快速的建立方法，并根据中文文体的特点，提出了有效的索引压缩方法。实验表明，使用虚拟内存技术可以大大节省索引的建立时间；采用字节对齐的索相压缩技术，不但可以有效地减少索引占用的磁盘空间，而且可以加快检索时间，索引的空间和时间效率都得以提高。     

基于小波的压缩图像索引技术

在JPEG2000压缩框架下给出了两种压缩图像索引方法, 不需要完全解压缩, 减少了数据处理量。实验结果证明,给出的索引方法具有很强的图像表征能力,利用该索引进行图像检索,提高了检索效率。     

基于索引的XML查询技术研究

介绍了目前XML数据查询技术的研究现状,对主要的XML索引查询技术作了较深入的探讨,其中包括：基于路径索引的XML查询方法,如DataGuide、1-index、A（k）索引等;基于编码的XML索引查询方法,如Anc_Desc_B^＋、XR树＋XR-Stack算法等。文中对相关XML索引查询方法的优点和不足进行了分析。     

屏幕内容索引图的马尔可夫预测算法

目的 调色板编码是屏幕内容编码的典型方法之一,其索引图的编码效率直接影响到调色板编码算法的总体压缩性能。但是,在处理物体前景和文字边缘的过渡区或连接区索引时,现有索引图预测编码方法的效率仍有待改善。为此提出一种基于马尔可夫模型的索引图预测算法。方法 随机选取了2 000个局部预测失败的索引值并将它们划分为3类典型分布,发现前2类分布的索引值往往处于边缘的灰度平滑过渡区,相邻索引值间呈现较为明显的线性变化,进而提出采用1阶2维马尔可夫随机过程来刻画这种线性性。对于一个待预测索引值,首先利用1阶2维马尔可夫模型计算相邻索引值的线性相关得到初始预测值,再利用颜色转移概率最大化确定其最优预测值。结果 本文算法的预测准确率为97.53%,比多级预测算法（MSP）和基于局部方向相关性的预测算法分别平均提高了4.33%和2.10%,尤其适用于包含大量文字字符和几何图元的视频序列的索引图预测。并且,渐近时间复杂度与基于局部方向相关性的预测算法相当,明显低于MSP。具体地,本文算法的实际运行时间比MSP算法节省了95.08%,比基于局部方向相关性的预测算法增加了35.46%。结论 本文提出的基于马尔可夫模型的索引图预测算法通过发掘索引值在边缘区域的线性相关性和特定的颜色转移模式,提高了索引预测效率,并保持了较低的计算复杂度,可应用在屏幕内容文本/图形块的调色板编码中。     

高效Unicode／GB编码转换算法的设计和实现

为了在存储空间和运算能力严格受限的嵌入式系统中实现Unicode和GB2312编码的相互转换,设计了一种高效率的编码转换算法.该算法通过提取数据表中公共部分实现压缩存储,采用索引和二分法查找相结合的方式进行快速查找,和传统的转换算法相比约节省25%的存储空间,查找效率最高约提高3倍.该算法可在无操作系统支持的嵌入式系统中实现汉字编码之间的高效率的转换.     

调色板编码中双向预测的索引值优化分配*

调色板编码中关于索引值分配对索引图编码效率的影响研究较少.因此文中提出索引值优化分配算法,利用索引图生成过程及其预测过程的双向反馈,通过正向、反向预测反馈和联合概率最大化优化索引值分配,更容易准确预测生成的索引图,提高调色板编码的效率.实验表明,相比多级预测算法,文中算法可以提高局部方向相关性预测算法的预测准确率.     

基于测试数据分组合并的索引编码压缩方案

为降低集成电路的测试数据量,提出一种分组合并的索引编码压缩方案。该方案将原始测试集以固定宽度分组,根据相关性对每组测试字段进行群划分,选取若干较大的群,分别合并为标准字段存入解压结构的ROM中以备索引,并对测试字段进行索引编码。给出解压过程及实验结果,通过与其他编码方案的比较,证明该方案可行有效,且硬件开销较小。