python - 如何计算字符串每个字符的位数？ (bpc)

Question

我正在阅读的论文http://www.cs.toronto.edu/~ilya/pubs/2011/LANG-RNN.pdf使用每个字符的位数作为测试度量，以评估生成的文本计算机模型的质量，但未引用其计算方式。谷歌搜索，我真的找不到任何东西。

有人知道如何计算吗？最好使用Python，但使用伪代码或其他任何方法都可以。谢谢!

Answer 1

每个字符的位数是压缩方法性能的度量。它是通过压缩字符串然后测量压缩表示形式总共要用多少位除以原始字符串中有多少个符号(即字符)来应用的。压缩版本占用的每个字符位数越少，压缩方法越有效。

换句话说，作者使用他们的生成语言模型进行压缩，并假设生成的压缩方法的高效性表明底层生成模型的准确性。

在第1节中，他们指出:

The goal of the paper is to demonstrate the power of large RNNs trained with the new Hessian-Free optimizer by applying them to the task of predicting the next character in a stream of text. This is an important problem because a better character-level language model could improve compression of text files (Rissanen & Langdon, 1979) [...]

Rissanen＆Langdon(1979)的文章是对arithmetic coding(一种众所周知的文本压缩方法)的原始描述。

算术编码基于生成语言模型(例如作者建立的语言模型)进行操作。给定一个(可能为空的)字符序列，该模型将预测接下来可能出现的字符。人类也可以这样做，例如，给定输入序列hello w，我们可以猜测下一个字符的概率:o有很高的概率(因为hello world是一个合理的延续)，但是像h或hello where can I find..这样的字符也像i一样。具有非零概率。因此，我们可以为此特定输入建立字符的概率分布，而这正是作者的生成模型所做的。

这自然适合算术编码:给定已编码的输入序列，下一个字符的位序列由可能字符的概率分布确定:高概率的字符获得短位序列，低概率的字符获得短位序列。更长的顺序。然后，从输入中读取下一个字符，并使用根据概率分布确定的位序列进行编码。如果语言模型良好，则将很有可能预测了字符，因此位序列将很短。然后，压缩继续执行下一个字符，再次使用到目前为止的输入来建立字符的概率分布，确定位序列，然后读取实际的下一个字符并对其进行相应的编码。

请注意，在每个步骤中都使用生成模型来建立新的概率分布。因此，这是自适应算术编码的一个实例。

读取并编码所有输入后，将测量结果的总长度(以位为单位)，并除以原始未压缩输入中的字符数。如果模型良好，它将以较高的精度预测字符，因此每个字符使用的位序列平均较短，因此每个字符的总位较低。

关于即用型实现

我不知道算术编码的实现方式是否可以轻松集成自己的生成语言模型。大多数实现都是动态构建自己的自适应模型，即它们在读取输入时会调整字符频率表。

一种选择是从arcode开始。我看了看代码，似乎似乎可以集成您自己的模型，尽管这不是很容易。 hello winston成员表示语言模型；基本上是累积字符频率的数组，因此self._ranges是所有小于self._ranges[ord('d')]的字符的总相对频率(即如果假设仅使用小写字母字符，则为d，a和b)。您将必须在每个输入字符之后修改该数组，并将从生成模型获得的字符概率映射到字符频率范围。