【摘 要】
：
大数据正以指数级速度增长,其中大量数据是文本数据。文本数据作为传递信息的主要媒介,对文本信息的存储、传输和检索的成本急剧上升。因此需对文本进行压缩以节省存储传输成本,同时建立支持高效检索的压缩索引。压缩自索引已广泛用于许多字符串处理应用程序中,例如信息检索,基因组分析,数据挖掘和Web搜索。索引不仅索引数据,并且采用压缩形式对数据进行编码。而且,索引和它编码的数据可以直接操作,无需解压缩整个索引,
论文部分内容阅读
大数据正以指数级速度增长,其中大量数据是文本数据。文本数据作为传递信息的主要媒介,对文本信息的存储、传输和检索的成本急剧上升。因此需对文本进行压缩以节省存储传输成本,同时建立支持高效检索的压缩索引。压缩自索引已广泛用于许多字符串处理应用程序中,例如信息检索,基因组分析,数据挖掘和Web搜索。索引不仅索引数据,并且采用压缩形式对数据进行编码。而且,索引和它编码的数据可以直接操作,无需解压缩整个索引,从而达到节省时间的同时保持较小的存储空间。在某些应用中,例如在泛基因组分析中,由于泛基因组会关联到像图一样的结构,无法充分利用现有序列上的压缩自索引的功能,因此需要寻求表示泛基因组的方法。本文建立了基于小波树的高阶熵压缩的文本压缩自索引框架,提出了小波树节点上的混合编码方法,给出了所提出文本自索引空间的理论分析。然后面向泛基因组数据在长读比对问题中的潜在应用,将序列上的压缩自索引扩展到图数据上的压缩自索引。本文主要创新工作如下:（1）提出了基于小波树的高阶熵压缩的文本压缩自索引WFM,建立了在压缩空间进行快速检索的方法。WFM结合了BWT变换（Burrows-Wheeler transform）,小波树,混合编码,连同简明数据结构达到了最小空间占用,同时支持在压缩索引上的快速检索。对于长为n的文本T,WFM的理论空间占用为2 n Hk+o（n logσ）位,Hk表示T的高阶经验熵,k clogσn-1,其中c为满足0<c<1的常数,?为T的字符表大小。（2）给定长为m且编码为m log?位的模式P,WFM支持计数查询返回模式P的后缀范围的时间复杂度为O（m log?）;支持获取P在T中的所有出现位置的定位查询的时间复杂度为O（（m+occ log n loglog n）log?）,其中occ为模式P的出现次数;支持字串提取查询的时间复杂度为O（（len+log n loglog n）logσ）,给定子串在T中的起始位置st和长度len。此外,采用后缀数组值采样降低了实际的查询时间。（3）提出了针对泛基因组的图压缩索引方法GFM。对于给定参考基因组以及对应的已知变异信息,由于这些信息包括一组比对的序列集（被定义为泛基因组）,这组序列集可以关联到像图一样的结构。因此可以构造相应的有向无环标签图,然后对该图中每个节点按照图中路径的公共前缀进行排序,构建对应图的BWT变换和辅助标记位序列。使用压缩小波树对BWT串进行存储,并对图数据上的节点信息进行采样存储,以支持路径定位查询。（4）在基准文本数据集上的实验表明,对于不同规模和不同大小的字符表的文本数据,较之主流索引方法,WFM在压缩率和查询时间上具有一定优势,尤其是在块大小b=128时,查询时间的优势更为显著一些。实际上可以通过设置不同参数值来权衡空间占用和查询时间。当b增大时,WFM所占空间会降低,查询时间会增加;当b减小时,WFM所占空间会增加,查询时间会减小。同样后缀数组采样大小s的不同和块大小的变化所带来的空间及查询趋势基本一样。在基准泛基因组数据集上的实验表明,与当前针对图数据的方法GCSA相比,GFM在空间占用和定位查询时间上均具有一定优势。这为进一步将GFM应用于大规模读长比对到泛基因组序列提供了基础。
其他文献
公共场所安全对国家的建设发展具有重要意义。在人们日常生活的公共区域,如:交通十字路口、购物中心、住宅小区等,安装着大量的监控摄像头来进行公共安全监控。因此,如何快速、实时、智能地对视频进行异常事件分析成为计算机视觉领域一个受关注度较高的研究方向。深度学习具有模型容量大、自适应强等特点,并且在图像处理方面硕果累累。本文利用深度学习的相关知识,设计和实现了一个具有良好性能的视频异常行为检测网络。首先本
自1880年发现压电效应,很快传统的压电材料（无机钙钛矿陶瓷晶体和有机聚合物）就在机电传感器、致动器和能量转换器等领域得到广泛应用。然而,这些材料的绝缘特性限制了其压电极化和电子之间的耦合作用发挥。2006年,王中林院士首次利用压电半导体材料制备得到一种新型的压电纳米发电机,随即很快提出压电电子学概念和相应理论。压电电子学效应是将压电极化与半导体性质有效结合,通过压电极化电荷调控半导体界面能带和电
在脑机接口领域中,由于脑电信号能够直接反应人脑对外界变化的认知处理过程,因此利用它进行目标检测成为很多学者的关注焦点。利用脑电信号进行目标检测的关键在于:（1）对脑电信号的分析处理。小样本的脑电数据集往往会导致模型不能学习到泛化能力强的特征,且在二分类的脑电实验中,数据集中类别不平衡,正样本数量远小于负样本的数量,导致模型在训练中严重偏向于样本数较多的类别,对实际的目标检测问题效果很差;（2）设计
光学遥感影像是遥感成像中的重要组成成分,它可以应用于观测和监控地球表面各种物体和目标,如机场、飞机、建筑物等,因此其在国防安全、城市建设规划、灾害监测等领域具有广泛的应用价值。这些广泛的应用需求给光学遥感影像自动化解译带来了更高的要求。随着我国光学遥感技术的快速发展,光学遥感影像获取的数据量越来越丰富,尺度越来越大,分辨率也越来越高。此外,虽然光学遥感影像数据丰富,但是有标签的数据仍然非常稀缺。许
极化合成孔径雷达（Polarimetric synthetic aperture radar,简称为极化SAR）是一种多通道合成孔径雷达,有HH、HV、VH、VH四个通道,应用于环境监测、地球资源勘探和军事系统等。它通过垂直和水平发射和接收电磁波而形成的。后向散射波的极化变化通过反射目标而改变,极化传感器可以获得更多的信息来描述地表结构、地表覆盖、几何结构等。并且,极化SAR系统还具有全天时作业、
随着通信与电子信息技术的发展,天线在无线通信系统中的作用越来越重要。与此同时,对天线测量技术的要求也越来越苛刻,比如更高的精度和更大的带宽。一方面,球面近场测量因为不存在截断误差,可以得到待测天线完整的方向图等优点,在高精度天线测量方面得到了广泛应用。另一方面,球面近场测量的常见探头是矩形波导、圆波导、电偶极子等窄带天线,难以进行宽带测量。如果使用喇叭天线或者对数周期天线等宽带探头进行测量,则相应
空间环肋天线是一种典型的索网-桁架天线,为兼顾天线大口径、小收拢体积与高精度的发展需求,桁架由一系列细长杆组成,用于支撑索网结构,其中,细长杆具有高拉压刚度,但是弯曲刚度非常小。当杆受弯时,桁架会发生变形,这导致索网形面精度变差。为使索网具有高形面精度,本文基于“张拉整体”的结构特点,以索受拉、杆受压为约束,提出了适用于旋转抛物反射面和赋形反射面的空间张拉式环肋天线的几何-预张力设计方法。（1）针
近年来,卫星通信技术朝着高通量、终端小型化和移动化方向快速发展,新一代DVB-S2X标准因具有带宽利用率高、信道频带宽、传输信息量大和传输能力强等优势而得到广泛关注。DVB-S2X标准能支持多种调制编码方式、甚低信噪比模式和超帧模式,从而可以满足高通量卫星和小型移动终端的传输需求。对于不同应用场景,DVB-S2X标准定义了支持连续系统的标准帧结构和支持突发系统的超帧结构,针对这两种不同结构,本文研
合成孔径雷达（Synthetic Aperture Radar,SAR）成像技术有着全天时全天候的独特优势。SAR图像的质量也随着成像技术发展逐步提高,但其固有的成像模式和相干斑导致SAR图像的解译比光学图像更困难。图像分割作为SAR图像解译的重要技术之一有着重要的现实意义,因此有必要发展适用于SAR图像的分割技术。近年来,关于SAR图像分割的方法层出不穷、种类繁多。但由于真实场景SAR图像的复杂
微处理器作为信息处理系统中的运算核心,在高性能计算、信号与图像处理等领域获得了广泛的使用。浮点处理器作为微处理器中的重要部件,对微处理器的性能起着重要的作用,而超越函数作为浮点运算的一种重要类型,其运算的速度与精度都会影响处理器系统的性能。针对雷达信号处理、无人机飞控等领域对超越函数浮点运算的高精度和实时性需求,设计高性能的超越函数浮点处理器具有重要的工程应用价值。本文在分析国内外现有研究的基础上