algorithm - smaz 压缩库是如何工作的？

Question

我目前正在为一个基于我的语言的短文本压缩项目工作。但是作为一个初学者，我也知道一些基本的压缩算法，比如 LZW。但我仍然不明白smaz是如何工作的。我有两个问题：

1. smaz 是如何工作的？
2. 如何构建码本和逆码本？

任何人都可以为我解释一下吗？

非常感谢。

Answer 1

试图回答你的问题

smaz 是如何工作的？ 根据[1]，

Smaz 有一个硬连线常量内置密码本，包含 254 个常用英语单词、单词片段、二元组和小写字母（j、k、q 除外）。Smaz 解码器的内部循环非常简单：

• 从压缩文件中获取下一个字节 X。
  1. X == 254 吗？单字节文字：获取下一个字节 L，并将其直接传递给解码的文本。
  2. X == 255 吗？文字字符串：获取下一个字节 L，然后将以下 L+1 个字节直接传递给解码后的文本。
  3. X 的任何其他值：在码本中查找第 X 个“单词”（该“单词”可以是 1 到 5 个字母），并将该单词复制到解码的文本中。
• 重复直到压缩文件中没有更多的压缩字节。

因为码本是不变的，所以 Smaz 解码器无法“学习”新词并对其进行压缩，无论它们在原始文本中出现的频率如何。

此页面可能有助于理解代码。

如何构建码本和逆码本？ 存储库中的TODO文件和redit 中的作者评论指出字典是由未发布的 ruby​​ 脚本生成的。此外，作者解释说：

顺便说一句，Ruby 程序所做的是考虑所有可能的子字符串，甚至所有可能的分隔词，并建立一个频率表，然后根据字符串长度调整权重，最后手动调整表以非常压缩特定的东西出色地。例如，我手动添加了“http://”和“.com”标记，删除了最后两个条目。

您项目的替代方案可能是shoco 库，它支持基于您的语言生成自定义压缩模型。

Answer 2

smaz源代码只有 178 行，而且只有 99 行，没有注释和码本表。你应该看看它是如何工作的。

Smaz 是非常简单的码本压缩（就像你知道的 LZW）。该库包含最流行的英语术语表（第 5 - 51 行用于压缩表，第 56 -76 行用于解压缩）并将这些术语替换为压缩字符串中的索引。和解压相反。

例如，如果术语是压缩表中的一个字节索引，则字符串the end将压缩 58% 。the所以 7 字节长度的字符串变成了 4 字节长度的字符串。