当您初次登录到 developerWorks 时，将会为您创建一份概要信息。您在 developerWorks 概要信息中选择公开的信息将公开显示给其他人，但您可以随时修改这些信息的显示状态。您的姓名（除非选择隐藏）和昵称将和您在 developerWorks 发布的内容一同显示。

所有提交的信息确保安全。

当您初次登录到 developerWorks 时，将会为您创建一份概要信息，您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。

昵称长度在 3 至 31 个字符之间。您的昵称在 developerWorks 社区中必须是唯一的，并且出于隐私保护的原因，不能是您的电子邮件地址。

所有提交的信息确保安全。

My developerWorks:

我的通知：

退出

选择语言：

功能丰富的 Perl: 在 Perl 中使用倒排表

压缩比特串和其他数据

Teodor Zlatanov (tzz@iglou.com), 程序员, Gold Software Systems

Teodor Zlatanov 于 1999 年从美国波士顿大学（Boston University）毕业，获得计算机工程硕士学位。他从 1992 年起就从事程序员的工作，使用了 Perl、Java、C 和 C++。他的兴趣是文本解析、三层客户机-服务器数据库体系结构、UNIX 系统管理、CORBA 和项目管理方面的开放源码工作。可以通过 tzz@iglou.com与 Teodor 联系。

简介： 对于Perl 程序员，尤其是那些要和数据序列和 Unicode 打交道的程序员来说，倒排表是不可或缺的工具。在本文中，Ted 以他自己完成并提交到CPAN 网络上的一个 Perl 实现为例，为我们讲解了倒排表，并介绍了如何用倒排表来压缩比特串及普通的数据。

标记本文！

发布日期： 2003 年 12 月 09 日
级别： 初级
访问情况： 1730 次浏览
评论：

我最早使用倒排表，是在编写 Perl 6 Unicode 程序的时候。在 Unicode 编程中，基本上都是用倒排表来存储二进制属性和字符序列。我要感谢 Unicode 联盟的主席 Dr. Mark Davis，是他给我提供了一些倒排表的 C 语言实现版本。他说 (大体内容如下)：

“我大约是在 1985 年开始使用倒排表。它可以压缩大部分数据，可以快速查找，而且支持快速的 boolean 操作。我不了解以前人们是怎样实现倒排表的，不过它很简单，应该曾被多种方法实现过。”

另外，Richard Gillam 的“Unicode Demystified”一书 (在本文后面的参考资料中相关链接) 中有关于倒排表的帮助资料，以及很多其他吸引人的话题。我向所有对 Unicode 编程感兴趣的人强烈推荐这本书。

倒排表

那么什么是倒排表？对 倒排表 的最好描述是：它是对比特串的压缩表示。倒排表和按出现长度进行的简单数据编码相似，但也有所不同。

让我们来看一个例子。假设您要对一个比特串“1110011”进行编码。倒排表将存储一个由三个数字构成的序列：0，3，5。我们存储的是，开始出现 1 的位置，开始出现 0 的位置，然后再是出现 1 的位置，如此重复直到比特串结束。

如果开始出现的是 1，我们以数字 0 来开始这个序列，表示这个比特串以 1 开始。如果开始出现的是 0 ，那么这个规则需要改变，但效果是一样的，因为编码器和解码器都遵循这一规则。实际上，这个规则是倒排表惟一的巧妙之处。

如果我们要构建一个只用于查找的倒排表，我们就不需要存储最后一比特的位置。不过，如果我们想要通过倒排表构造出原始的数据，我们必须要知道在哪里停止增加新的比特，这时就需要存储最后一比特的位置。

生成倒排表实际上就是对比特的计数。在某些应用中，比如 Unicode 字符序列，使用倒排表可以为您节省大量的时间，降低工作难度。

回页首

Algorithm::InversionList 模块

我编写了一个可以由任何数据生成的倒排表的模块，称为 Algorithm::InversionList 。我已经将它上传到 CPAN 的 Perl 模块档案文件中，可以免费获得 (参阅参考资料中的链接)。

开始时我尝试使用正则表达式和 index() 函数来编写 Algorithm::InversionList 。虽然完成了，但是它很慢，而且难用。CPAN 上当前的实现版本是 0.03，获取和存储数据使用的是 Perl 的 vec() 函数。它还可以再优化 -- 例如，现在获取和存储是以 1 比特为单位进行操作的，如果以 8 个比特作为一组来处理，效率将会得到提高。

Algorithm::InversionList 模块分为四部分。首先是头信息：

清单 1. Algorithm::InversionList 头信息

package Algorithm::InversionList;
use 5.006;
use strict;
use warnings;
require Exporter;
our @ISA = qw(Exporter);
our @EXPORT = qw(
invlist data_from_invlist	
);
our $VERSION = '0.03';

这是基本的部分；它声明了程序需要 Perl 5.006 来解释执行，要求进行严格的变量检查和警告，还有我们将要导出 invlist() 和 data_from_invlist() 函数。这是一个过程模块，也就是说并不存在对象，您只是得到了两个导入的函数，然后您可以用它们来生成倒排表，或者将倒排表转换回规则数据。参考资料中有关于 Exporter 模块的资料。

接下来是 invlist() 函数，用于生成倒排表。

清单 2. invlist() 函数

sub invlist
{
 my $string = shift @_;
 # we need a valid string
 return undef unless defined $string;
 # handle trivial case of 0-length string
 return [] unless length $string;
 # this is suboptimal, we eventually want to do things
 #    in multiples of 8 (on byte boundaries)
 # $length is length in bits, we avoid b* because it will
 #    create a list 8 times larger than C*
 my @unpacked = unpack("C*", $string);
 my $length = scalar @unpacked * 8;
 my $current = vec($string, 0, 1);
 my $new;
 my @list;
 push @list, 0 if $current;
 foreach my $offset (0..$length)
 {  
  $new = vec($string, $offset, 1);
  if ($new != $current)
  {
   push @list, $offset;
  }
  $current = $new;
 }
 push @list, $length;
 return \@list;
}

首先来看 $string 中给出的数据。如果此变量没有被定义，将返回 undef 。如果它为空，将返回一个空数组。注意 Perl 如何区分未定义的串和空串 (长度是 0)。

然后初始化变量，通过调用 unpack() 来得到串的长度。阅读参考资料中关于 pack() 和 unpack() 的文档，您将会明白我们为什么用 “C*” 模板。而且，通过阅读那篇文档，您还可以得到关于 Perl 的最基本的知识。

变量 $current 将始终保持当前比特值 (我们处理过的最后一比特)。开始时序列为空，如果第 1 个比特是 1，我们就插入一个 0。这说明在第 0 比特的位置开始出现 1 。

读取数据使用的是 vec() 函数 -- 在参考资料一节中也有相关文档的链接。虽然 vec() 可以读取更多的比特，但在这里，我们只用它每次读取一个比特。

现在，我们来运行主循环。我们把串中的每一比特读到变量 $new 中，如果它与 $current (先前的比特) 不同，我们就将偏移量 (存储在相应的名为 $offset 的变量中) 压入到序列 @list 的尾部。然后，我们将 $new 赋给 $current ，以使之成为下一个循环中的 “old” 比特。

循环完成后，我们将数据的长度压入到序列的尾部。这是必须的，因为只有这样解码器才可以知道最后一比特出现在什么位置。然后返回一个对 @list 的引用给调用者，任务完成。

清单 3. data_from_invlist() 函数

sub data_from_invlist
{
 my $out = '';              # start with a blank string
 my $append = 0;            # we're appending '0' bits first
 my $list = shift @_;
 return undef unless defined $list;
 my $start_offset = 0;
 foreach my $end_offset (@$list)    # for each inversion list value
 {
  foreach my $offset ($start_offset .. $end_offset-1)
  {
   vec($out, $offset, 1) = $append;
  }
  $append++;                # 0 => 1, 1 => 2
  $append %= 2;             # 2 => 0, 1 => 1
  $start_offset = $end_offset;
 }
 return $out;               # return the data
}

与 invlist() 函数相对应的函数是 data_from_invlist() ，用来从倒排表中生成原始数据。

首先初始化 $out ，这将是最终的输出。开始时添加 0，从得到的第一个偏移位置开始添加 1。所以我们要将 $append 初始化为 0。

对倒排表中的每一个偏移量，我们从前一个偏移位置 (第一个 item 是 0) 到当前偏移位置减 1 之间的所有位置进行遍历，按 $append 的值设置在所有这些位置上的比特。我之所以称它为 $append ，是因为当 $out 对偏移量来说长度不够时 vec() 函数需要附加数据到 $out 。

注意当结束偏移量与开始偏移量相等时，什么都不会发生，因为 .. 操作不会向后进行。

当所有的位置都设置完成后，我们将 $append 加 1 然后模 2 除，目的是将 1 变成 0，0 变成 1，也就是切换 0、1 值。

最后，我们将当前的结束偏移量设置为下一个循环的开始偏移量。

在这个模块最后是 POD 文档。您还可以看一下模块中的测试脚本，test.pl。其中实现了一些自动的系统测试。

回页首

压缩任意的数据

表面看来，倒排表并不适合用于规则数据，但是实际上它很容易扩展用以处理规则数据。我们只需要生成 8 个并行的倒排表，去对每个字节的 8 比特进行编码。为什么用字节？因为在一个很长的数据序列中，最容易重复出现的就是字节。换句话说，我们不想用一个单独的倒排表来对

101000111010001110100011101000111010001110100011101000111010001110100011

(10100011 重复 9 次) 进行编码；我们希望用 8 个并行的通道来对其进行编码，得到 9 个 1，9 个 0，9 个 1，9 个 0，9 个 0，9 个 0，9 个 1，9 个 1。还可以有更好的压缩算法；这不过是为了证明倒排表可以用于比单个比特更宽的通道。

清单 4. 比特通道

sub do_channels
{
 my $data = shift @_;
 print "Test data $data\n";
 my $n = 8;
 # you don't have to change this unpack if $n changes
 my @unpacked = unpack("C*", $data);
 my $length = scalar @unpacked;
 $length *= 8/$n;
 my @channels = ('' x $n);
 # multiplex the data onto $n channels
 foreach my $channel (0..$n-1)
 {
  foreach my $offset (0..$length-1)
  {
   vec($channels[$channel], $offset, 1) = vec($data, $offset*$n+$channel, 1);
  }
 }
 my @inv = map { invlist($_) } @channels;
 foreach my $channel (0..$n-1)
 {
  my $list = $inv[$channel];
  print "Channel $channel: @$list\n", 
 }
 my @out = map { data_from_invlist($_) } @inv;
 my $out = '';
 # demux the $n channels back
 foreach my $channel (0..$n-1)
 {
  foreach my $offset (0..$length-1)
  {
   vec($out, $offset*$n+$channel, 1) = vec($out[$channel], $offset, 1);
  }
 }
 print "All OK\n" if $out eq $data;
}

接下来会怎样？ do_channels() 函数使用 $n 变量 (默认是 8) 来确定使用多少个通道来处理 $data 中的数据。例如，如果数据每 32 比特重复一次，您可以将 $n 设置为 32，用各个通道来容纳重复的数据。

@channels 序列被初始化为 $n 个空串。这样，每一个串将被由相应通道从 $data 得到的比特所填充。我们通过对 @channels 调用 map() 方法来得到每个通道数据的倒排表，将这些倒排表存储在 @out 序列中，然后可以对 @inv 序列调用 map() 方法将其还原为数据，并存储到 @out 中。

注意这里使用 map() 的技巧。当数据序列数目不是太大的时候，用 map() 来完成一个序列到另一个序列的映射是非常好的选择。

最后，我们将 @out 序列中的数据通过通道还原到 $out 串。经过验证， $out 和 $data 是相同的，也应该是相同的。

回页首

结束语

希望您能喜欢阅读有关倒排表的资料。倒排映射和压缩数组等其他一些数据结构也具有类似的优点；参考资料一节中 Gillam 的书中有关于这些数据结构更详细的资料。

在 Perl 中实现倒排表是既有趣又麻烦的。Perl 对程序员来说非常有用，但是它并不擅长处理面向比特的算法。而且，您还要考虑指令潜在的速度问题，与 C 相比在 Perl 中这种影响要严重很多。

如果您对 Algorithm::InversionList 的更多细节或者其他类似的算法和数据结构有好的想法或建议，不要犹豫，请给我写信。

参考资料

您可以参阅本文在 developerWorks 全球站点上的英文原文.
阅读 developerWorks 上 Ted 的 “功能丰富的 Perl” 系列中的其他 Perl 文章。
CPAN module archive是一个有用的 Perl 代码仓库。
您可以下载 Algorithm-InversionList 模块和 Algorithm::InversionList 帮助手册。
Ted 强烈向您推荐 Richard Gillam 的 Unicode Demystified: A Practical Programmer's Guide to the Encoding Standard 一书 (Addison-Wesley, 2002 年)。这是关于 Unicode 编程的极好的一本书，涵盖了倒排表和倒排映射等内容。
如果您对 Unicode 编程感兴趣应该去访问 Unicode Consortium。
在 developerWorks Linux 专区您可以找到更多 Linux 文章。