优化字节对编码

Question

注意到大文本压缩基准测试中缺少字节对编码(BPE),我很快就对其进行了简单的文字实现.

压缩比 - 考虑到没有进一步处理,例如没有霍夫曼或算术编码 - 令人惊讶地好.

然而,我的琐碎实现的运行时间不是很好.

如何优化？是否可以一次性完成？

Answer 1

这是迄今为止我的进展摘要:

谷歌搜索发现这个小报告链接到原始代码并引用来源:

Philip Gage,题为'一种新的数据压缩算法',出现在'C用户期刊' - 1994年2月版.

Dr Dobbs网站上的代码链接已损坏,但该网页反映了它们.

该代码使用哈希表来跟踪使用的有向图及其每次通过缓冲区的计数,以避免重新计算新的每次传递.

我的测试数据是来自Hutter奖的enwik8.

|----------------|-----------------|
| Implementation | Time (min.secs) |
|----------------|-----------------|
| bpev2          | 1.24            | //The current version in the large text benchmark
| bpe_c          | 1.07            | //The original version by Gage, using a hashtable
| bpev3          | 0.25            | //Uses a list, custom sort, less memcpy
|----------------|-----------------|

bpev3创建所有有向图的列表; 这些块的大小为10KB,并且通常有200个左右的有向图(4个,这是我们通过压缩可以获得一个字节的最小值); 此列表已排序,并进行第一次替换.

在进行替换时,统计数据会更新; 通常每次通过只有大约10或20个有向图变化; 这些都是'绘制'并排序,然后与有向图列表合并; 这比直接对每个传递的整个有向图列表进行排序要快得多,因为列表几乎已经排序.

原始代码在'tmp'和'buf'字节缓冲区之间移动; bpev3只是交换缓冲区指针,单独运行时值约10秒.

鉴于对bpev2的缓冲区交换修复将使穷举搜索符合哈希表版本; 我认为哈希表是可论证的值,并且列表是这个问题的更好结构.

它的窗台多通过.因此它不是一般的竞争算法.

如果您查看大文本压缩基准测试,则会添加原始bpe.由于它的块大,它在enwik9上比我的bpe更好.此外,哈希表和我的列表之间的性能差距更接近 - 我把它归结为march=PentiumProLTCB使用的.

当然有适合和使用的场合; Symbian使用它来压缩ROM映像中的页面.我推测Thumb二进制文件的16位特性使其成为一种简单而有益的方法; 压缩在PC上完成,解压缩在设备上完成.