gpt4 book ai didi

c++ - 在文本压缩期间存储概率表

转载 作者:太空宇宙 更新时间:2023-11-04 05:00:44 27 4
gpt4 key购买 nike

我正在做一个项目,我比较不同类型的文本压缩方法,例如静态和自适应形式的 Huffman 和 Arithmetic。我使用文本中每个字母的出现次数为两者制作了一个概率表。现在,对于自适应形式,接收方不需要概率表,但对于静态形式,我们需要将此概率表也传输给接收方以解码消息。现在,表的这种存储将需要一些额外的位,在比较时应考虑到这些位。

所以我的问题是:

  1. (在文件中)存储概率表的最佳解决方案是什么。
  2. 做到这一点所需的最少位数是多少? (我知道这取决于文本,但是有什么方法可以找到存储表格所需的最少位数)。

非常感谢。

最佳答案

根据概率,您可以将代码长度分配给符号。要创建代码,接收方需要一个元组列表:(位计数,符号计数),后跟按顺序分配给代码的符号。现在您可以尝试如何对它们进行编码。

编码符号列表可以利用这样一个事实,即对于传输的每个符号,后续符号所需的位数会减少。尽早指定使用(例如)8 位符号的某些子集的选项在这里可以提供帮助。随着码字变长,对一系列符号进行编码可能会很方便,而不是传输每个符号——也许用一种方式来表达一个运行更少的符号,其中“漏洞”可以表示为一些位数取决于游程的长度——或起始符号、长度和位 vector (请注意,表示长度的位数取决于起始符号和剩余符号的数量,并且有无需为范围内的第一个和最后一个发送位!)

霍夫曼码表的编码本身就是一个完整的游戏。然后对于短消息,该表可能是一个严重的开销......在这种情况下,(少量)常用表可能会提供更好的压缩。

您还可以对每个符号的代码长度进行霍夫曼编码,然后按符号顺序发送。重复计数机制及其霍夫曼可以在这里提供帮助,以及一种跳过未使用符号(即代码长度为零的符号)运行的方法。当然,您可以添加一级表来指定此编码!

另一种方法是使用多个位 vector ,每个码字长度对应一个 vector 。从具有最多符号的代码字长度开始,发出长度和一个位 vector ,然后是下一个人口最多的代码长度和一个较小的位 vector ......等等。同样,对运行和范围进行编码的方法可以减少所需的位数,而且,随着您的继续,这些所需的位数也会减少。

问题是,比较对码表大小的敏感度如何?显然,如果它非常敏感,那么调查应用狡猾可以做什么是很重要的。但任何给定方案的有效性将取决于它适合被压缩的“典型”数据的程度。

关于c++ - 在文本压缩期间存储概率表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24973123/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com