模板化的 Burrows-Wheeler 变换

• 下载源代码文件 - 3.4 Kb

引言

这段代码是我在奥尔堡大学完成硕士论文时编写的。我们研究了多种压缩倒排索引的方法，以保持较低的磁盘空间需求。 附带的代码演示了一种在模板化的 C++ 环境中实现 Burrows-Wheeler 变换的方法。 到目前为止，我只使用 G++ 在 Sun Solaris 上对其进行了测试，但该代码与平台无关，应该可以在任何地方编译。

背景

在研究重新排列数据以实现更高压缩率的方法时，我偶然发现许多不同编解码器中的大量代码片段。 但是，我从未找到任何关于 Burrows-Wheeler 变换（也称为 BWT）的代码。

那么，什么是 BWT？

BWT 是一种用于重新排列数据以通过以下编解码器实现更高压缩率的高级技术。 通常，BWT 将一系列符号作为输入，并尝试通过重新排列位置来对数据进行排序，而不会篡改实际值。 作为独立的编解码器，BWT 除了对数据添加少量开销外，什么也不做，但是，在开发自定义压缩方案时，可以将多个编解码器按顺序设置，以实现更高的压缩率。 一个简单的编解码器场景是首先执行 BWT，然后执行行程长度编码 (RLE)。 以下是 BWT 后跟 RLE 的示例应用

给定以下输入到 BWT

The quick brown fox jumped over the silvermoon. The quick brown fox jumped 
over the silvermoon. The quick brown fox jumped over the silvermoon. The 
quick brown fox jumped over the silvermoon.

BWT 将输出以下代码

...kkkknnnnxxxxddddeeeeeeeerrrr.nnnn|       iiiieeeehhhhhhhhppppvvvvvvvv    
TTTTttttuuuussss    cccciiiirrrruuuuwwwwoooooooommmm    rrrrffffmmmm    eeee
eeeebbbb        qqqqjjjjoooolllloooooooo|

其中“|”是 BWT 分隔符符号。

与原始文本相比，这段代码高度可压缩。 以下是在上述 BWT 代码上显示的简单 RLE 编码

3.#4k#4n#4x#4d#8e#4r#.#4n#|#7 #4i#4e#8h#4p#8v#4T#4t#4u#4s#4 #4c#4i#4r#4u
#4w#8o#4m#4 #8e#4b#4q#4j#3o#4l#8o#|#

其中“#”是 RLE 分隔符符号。

应用比 RLE 更高效的编解码器将产生更好的压缩率。

使用代码

由于代码是模板化的，因此您可以将各种数据放入集合中并执行 BWT。 但是，请确保您分配一个符号作为分隔符，用于 BWT 和反 BWT。

第一个示例演示了如何将短字符串转换为易于压缩的 BWT 形式

    // instantiate the BWT and allocate the value 127 as delimiter
    cBWTransform<char> transform(127);
    
    // push the string "BANANA" of length 6 onto the BWT-list
    transform.push_back("BANANA", 6);
    
    // perform the BWT transformation
    cBWTransformationCode<char> code = transform.Transform();
    
    // prepare for the inverse-BWT transformation
    // and allocate the value 127 delimiter
    // the delimiter value must be
    // the same for the inverse-BWT and the BWT
    cBWTransformation<char> inverse_transform(127);
    
    // execute the inverse-BWT on the BWT-code from above
    inversetransform.InverseTransform(code);
    
    // output the value to std out
    for (cBWTransform< char>::iterator i=inversetransform.begin(); 
                                       i!=inversetransform.end(); i++) {
        cout << *i << " ";
    }
    cout << endl;

关注点

上述代码使用 STL 编写，并且在很大程度上依赖于 STL。 在我们的硕士论文项目中，我们发现时间压力使 STL 非常有用，但是，对于特殊用途，您可能希望编写手动优化的代码 :-)

有关 BWT 变换的更多信息，请参阅以下来源

• Mark Nelson 的《使用 Burrows-Wheeler 变换进行数据压缩》.
• 维基百科上的 Burrows-Wheeler.
• Kalchas - 动态 XML 全文搜索引擎.

历史

• 2005/05/28 - 初始版本。
• 2005/05/28 - 添加了（希望）说明性示例。
• 2005/05/29 - 更新 ZIP 文件，其中包含 VS.NET 2003 项目。