`
emily2ly
  • 浏览: 166644 次
  • 性别: Icon_minigender_2
  • 来自: 武汉
社区版块
存档分类
最新评论

BWT数据压缩算法

阅读更多

在全文检索中通常要对索引进行压缩存储,在压缩之前如果对文本进行一定的可逆变换能够使之更易压缩,BWT就是这样一种变换.
    通过一个例子来介绍BWT,假设一段待转换的文本为:ababc, 则BWT的过程如下:

 

在T后插入结束符#得到新的文本串T#,循环左移,每次一位,得到一个|T#|行的矩阵,按首字母排序得到M
  F = first column of M

  L = last column of M
  BMT使用L来代表T,这样做的原因是L通常比T更容易压缩(具有很多连续的相同元素),那么怎么通过L恢复出F呢?
注意下面的性质:
    1、L的第一个元素是T中的最后一个元素
    2、对于M中的每一行(第一行除外)第一个元素都是最后一个元素的下一个元素
    利用这两个性质以上面的例子说明怎么恢复T:
c是最后一个元素,然后找c的前一个元素,因为M中仅有最后一行是以c开头的,则这一行的b是c的前一个元素,
再找b的前一个元素,在M中找以b开头的元素,有两行(4、5),到底是哪一行呢?只需看刚才以c开头的那一行之前,在L中出现了几个b,这里出现了一个,
所以应该看第5行,也就是b之前是a。继续找a的前一个元素。。。。。
 
    显然不能整个存储M,那们上面的过程如何在实际中运用,答案是建立 一个L-M Mapping(LF)的辅助向量
LF[i]=C[L[i]]+ri 
其中 C[c]是字符c在F中的zeroth occurrence位置(也就是c-1字符最后出现的位置),ri是c在L[1,i]中c的出现次数
所以使用BWT,我们最后得到的是L和LF,回复T的算法为:
 
For each i = u-1, …, 1 do:
      s = LF[s] (threading backwards)
     T[i] = L[s] (read off the next letter back)

 

 

(完)

create@2009-10-28

  • 大小: 11.9 KB
分享到:
评论

相关推荐

    Burrows-Wheeler Transformation(BWT)压缩算法

    Burrows-Wheeler Transformation (BWT) 是一种革命性的数据压缩算法,它改变了传统压缩算法的处理方式。通过对输入数据进行特定的变换,BWT 为后续的压缩步骤创造了更佳的机会,特别是在文本数据的压缩方面表现出色...

    基于BWT的文本压缩算法研究

    ### 基于BWT的文本压缩算法研究 #### 一、引言 随着信息技术的飞速发展,数据量呈爆炸性增长,如何有效地存储和传输这些数据成为了亟待解决的问题。数据压缩技术应运而生,其核心目标是减少数据占用的空间,提升...

    常用数据无损压缩算法分析

    BWT常与其他压缩算法结合使用,如在Bzip2中。 5. Arithmetic coding(算术编码):算术编码通过对每个字符的概率进行精确量化,将数据编码为一个连续的实数值区间,相比传统的熵编码如霍夫曼编码,算术编码可以更...

    一些常用的Delphi数据压缩算法示例源码..rar

    本资源"一些常用的Delphi数据压缩算法示例源码..rar"包含了一些在Delphi中实现的数据压缩算法的源代码,对于理解和应用这些算法具有很高的参考价值。 1. **LZ77(Lempel-Ziv 1977)算法**: LZ77是最早的数据压缩...

    几种常用无损数据压缩算法研究.docx

    Burrows-Wheeler 变换(BWT)是一种基于字符块的数据压缩算法。它将数据块中的字符按照出现频率进行排序,并仅保留一个字符块中的最后一个字符。通过在数据中重复这一过程,可以实现对数据的压缩。BWT 的优点在于...

    BWT完整算法

    - **文本压缩**:由于BWT能够将相似的字符集中到一起,因此它在数据压缩中表现出色,可以减少重复信息,提高压缩率。 - **字符串搜索**:BWT使得在大量文本中搜索特定模式变得高效,因为相似的模式在BWT字符串中...

    各种压缩算法源码

    这种方法可以实现无损数据压缩,适用于文本和图像等数据的压缩。 2. **LZW(Lempel-Ziv-Welch)编码**: LZW编码是一种动态构建字典的无损压缩算法,最初由Ziv和Lempel提出,Welch进行了改进。它通过查找输入数据...

    论文研究-BWTBoyerMoore压缩域搜索算法的研究.pdf

    Burrow-Wheeler变换是一种将字符串转换为更容易进行数据压缩和搜索的形式的算法。在BWT之后,相同字符的连续出现会被聚在一起,这使得数据压缩效果更好,同时也使得某些类型的数据搜索变得更加容易。 4. **BWT-...

    各类压缩算法聚合

    在IT行业中,压缩算法是数据处理和存储领域的重要组成部分,特别是在大数据传输和存储效率方面起着关键作用。本文将深入探讨“压缩算法 集合 java”这一主题,结合Java编程语言,阐述压缩算法的基本原理、常用算法...

    bwt.zip_bwt_压缩编码

    **标题:“bwt.zip_bwt_压缩编码”** 在信息技术领域,压缩编码是一种重要的数据处理技术,用于减小数据的存储需求和...同时,理解并掌握这两种技术的原理和应用,对于任何涉及数据压缩的IT专业人员来说都至关重要。

    BWT.rar_BWT MATLAB_BWT压缩_BWT编译_arithmetic codec_bwt

    标题 "BWT.rar" 包含的是一个关于MATLAB实现的BWT(Burrows-Wheeler Transform)压缩算法,结合了算术编码器(Arithmetic Codec),用于高效地压缩文本数据。这一组合提供了高效的文件压缩解决方案,特别是在处理...

    数据压缩软件源代码

    在数据压缩算法中,常见的有哈夫曼编码、算术编码、LZ77(Lempel-Ziv)家族、Burrows-Wheeler变换(BWT)、游程编码(Run-Length Encoding, RLE)等。哈夫曼编码是一种基于频率的前缀编码,通过构建最优二叉树来分配...

    BWT.rar_C++_bwt_compress_in

    标题"BWT.rar_C++_bwt_compress_in"指的是使用C++实现的Burrows-Wheeler Transform(伯罗斯-怀勒变换,简称BWT)压缩算法。这个压缩算法是数据压缩领域的一个重要技术,由Michael Burrows和David Wheeler在1994年...

    Google新开源压缩算法Brotli

    它通过使用BWT(Burrows-Wheeler transform)和Huffman编码等技术来实现数据压缩。 在测试方法方面,作者使用了不同的窗口大小来测试不同算法的性能,以比较其压缩比和速度。对于Brotli、LZMA和LZHAM,使用了22位的...

    bwt.rar_bwt

    由于BWT的复杂性和对数据模式的敏感性,它并不总是提供最佳的压缩效果,但结合其他压缩技术,如LZ77、LZ78或者PFC(Predict by Partial Match),可以形成更高效的压缩算法,如BWT+LZ77的bzip2或BWT+MR(Move-to-...

    浅谈数据压缩技巧.pdf

    常用的数据压缩方法包括霍夫曼编码(Huffman Coding)、算术编码(Arithmetic Coding)、变动长度编码(Variable-length Coding)和BWT算法。 霍夫曼编码是一种广泛使用的无损压缩算法。它根据数据中字符出现的频率构建一...

    lzw压缩,解压缩算法

    LZW(Lempel-Ziv-Welch)压缩算法是一种数据压缩方法,广泛应用于文本、图像和其他二进制数据的压缩。它通过构建一个动态的字典来编码数据,允许新出现的模式被编码为较短的代码,从而实现数据的高效压缩。以下是...

    文件压缩算法,比较经典的几种

    同时,有些压缩算法如Burrows-Wheeler Transform(BWT)和LZMA(Lempel-Ziv-Markov chain Algorithm)在特定场景下也能达到极高的压缩效率。 总结来说,文件压缩算法是信息存储和传输的关键技术,Huffman编码和LZ...

    bwt.rar_BWT编码_bwt

    BWT变换的关键在于它能够将数据中的重复模式暴露出来,使得后续的压缩算法如算术编码能够更高效地处理这些模式。 具体步骤如下: 1. **创建矩阵**:将输入的字符串排列成一个圆形的矩阵,每一行代表一次右移后的...

Global site tag (gtag.js) - Google Analytics