这篇文章将介绍一种将明文消息编码为目标词汇表的算法。该词汇表可以由假想语言中的一组单词构成，并且可产生流畅自然的结果（这里的例子使用了《绝区零》中的邦布叫声；类似的例子还有猫叫声、狗叫声等）。结果如下所示。
词汇表可以替换为任何符号集。如果你想构建一个猫语生成器，可以使用诸如[“喵”, “喵呜”, “嗷”]这样的词汇表。输出将是一个由这些词汇表（和空格）连接起来的序列。
实现
网页版的邦布语生成器： https://bangboo.sakana.moe
源代码：https://gitlab.com/MetricVoid/bangboo
目标
该算法旨在将短句编码为由词汇表中的单词组成的序列。目标是使编码尽可能简短。
Input Data
算法使用以下输入数据
$I$: 输入的明文，编码为一串字节。
$L$: 目标语言的词汇表，表现为一个符号列表。$L[i]$ 指词汇表中的第 $i$ 个符号。符号必须遵守某些要求，见 构造词汇表。
$zdict$: 预设的DEFLATE词典，包含了 $I$中可能出现的常用词汇. 例如，如果 $I$ 是自然语言，那么 $zdict$ 就是这门语言中的常见词汇。
算法
算法包含以下步骤：
第一步 压缩
首先，输入数据使用DEFLATE算法和预设词典压缩。
$$C = DEFLATE(I, zdict)$$
选择DEFLATE的原因是我们预计输入是一个重复较少的短句。像LZMA这样的算法在编码包含重复的大文件时更有效率，但它们使用区间编码器，这意味着在处理重复较少的短文本时效率较低。
与在整个输入上运行zlib并生成并嵌入到输出中的字典相比，我们选择使用预设字典的原因是，我们假设了输入预计是一个重复信息较少的短句。在理想情况下，使用内置大量常用词汇的字典，压缩步骤主要由指向字典的指针序列组成，这样效率更高。
第二步 N进制编码
在第一步后，我们会得到一串代表输入的字节。接下来要将这串字节映射到目标词汇表上。
There are two parameters we can tune here: element group size(M) and lexicon size(N). The basic idea is to treat the byte sequence as a huge number, convert it into base-N format, and correspond each digit to a word in the lexicon. However, the output is usually massive if treated as a single number, preventing efficient modulo and division operations. Therefore, the output sequence $C$ is divided into numerous smaller numbers, each consisting of M bytes. If $C$ is not a multiple of M bytes, zeros will be added as padding. Since N is usually not an integer power of 2, a larger group size M could help efficiency by utilizing more of the fractional bits, but it would also lead to longer padding if $len(C)$ is not a multiple of M.
这里有两个参数可以调整：元素组大小（M）和词汇表大小（N）。基本思路是将字节序列视为一个大数，将其转换为N进制格式，并将每个数字对应到词汇表中的一个单词。然而，如果将输出视为一个单一的大数，通常会非常庞大，导致模运算和除法运算效率低下。因此，输出序列C被分成许多较小的数字，每个数字由M个字节组成。如果C不是M字节的倍数，则会添加零进行填充。由于N通常不是2的整数次幂，较大的组大小M可以通过利用更多的分数位来提高效率，但如果 $len(C)$ 不是M的倍数，也会导致更长的填充。
举例，压缩后的字节序列含有多个M字节长的小段，可以为表示为
$$C = \overline{C_1C_2C_3...}$$
然后将每段M字节的序列转换为N进制，C的N进制编码就可被描述为矢量E
$$E = \langle C_{1_{[N]}}, C_{2_{[N]}}, C_{3_{[N]}}... \rangle$$
Step 3. Correspond encoding to the lexicon
最后一步就是对照词汇词典，找出对应的词组。
将矢量 $E$ 写成如下形式
$$ E = \langle E_1, E_2, E_3, ... \rangle $$
对 $E$ 中的每一个元素，提取它的数位。
$$ E_1 = \overline{E_{1_1}E_{1_2}E_{1_3}...} $$
那么，$E_1$ 的此表编码就是
$$ L_1 = \overline{L[E_{1_1}]L[E_{1_2}]L[E_{1_2}]...}$$
最终的编码$R$ 就是 $E$ 中每一个元素的编码连接在一起
$$R = L_1 + SPACE + L_2 + SPACE + L_3 + ...$$
这里的 $SPACE$ 可以是空格，也可以是词组中选择一个词，专门作为分隔符使用。
Constructing The Lexicon
Rules
词汇表 $L$ 必须遵循特定规则。
- 不能有重复的单词或符号。
- 除非特别保留用于此目的，否则任何符号中不应包含 $SPACE$。
- 任何符号都必须不可以由其他符号连接得到。例如
- [A, B, C] 是一个有效的词汇表。
- [A, B, ABC] 也是一个有效的词汇表。
- [A, B, C, ABC] 是无效的，因为 ABC=A+B+C。在编码结果中，序列 ‘ABC’ 是有歧义的，因为它可以解码为 A+B+C 或 ABC。
- 还值得注意的是，在解码过程中，子词应从最长到最短与编码序列匹配。例如，如果从序列 ‘ABC’ 中消耗了 A+B，剩余的序列 ‘C’ 无法与词汇表中的任何内容匹配，会产生错误。
Tricks
有一些技巧可以用来增加词汇表的大小，从而获得更短的编码输出序列
- 添加不可见字符，例如零宽空格。
- 使用相似的字符创建不同的序列，例如中文感叹号
！和英文感叹号!
Comments NOTHING