级别： 初级 Teodor Zlatanov (tzz@iglou.com), 程序员, Gold Software Systems
2003 年 12 月 09 日 对于Perl 程序员，尤其是那些要和数据序列和 Unicode 打交道的程序员来说，倒排表是不可或缺的工具。在本文中，Ted 以他自己完成并提交到CPAN 网络上的一个 Perl 实现为例，为我们讲解了倒排表，并介绍了如何用倒排表来压缩比特串及普通的数据。
我最早使用倒排表，是在编写 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 的更多细节或者其他类似的算法和数据结构有好的想法或建议，不要犹豫，请给我写信。
参考资料
关于作者  | 
| | Teodor Zlatanov 于 1999 年从美国波士顿大学（Boston University）毕业，获得计算机工程硕士学位。他从 1992 年起就从事程序员的工作，使用了 Perl、Java、C 和 C++。他的兴趣是文本解析、三层客户机-服务器数据库体系结构、UNIX 系统管理、CORBA 和项目管理方面的开放源码工作。可以通过
tzz@iglou.com与 Teodor 联系。
|
对本文的评价
| 
