标签: huffman-code

我使用霍夫曼压缩编码压缩字符串数据,即"需要更多资金"

编码

\n 0110
   1011
d  100
e  11
m  001
n  000
o  010
r  0111
y  1010
**
001010011111101100101000011101010110001111100111000110

我想在java中重建Huffman树来解码编码.用于这种解码的任何实现或示例.

我尝试并编写了完美的解决方案.

public class HuffmanTree {

    public Node root;

    public HuffmanTree(){
        this.root = new Node();
    }

    public void add(char data, String sequence){

        Node temp = this.root;
        int i = 0;
        for(i=0;i<sequence.length()-1;i++){

          if(sequence.charAt(i)=='0'){
                if(temp.left == null){
                    temp.left = new Node();
                    temp = temp.left;
                }
                else{
                   temp = (Node) temp.left;
                }
            }
            else
              if(sequence.charAt(i)=='1'){
                if(temp.right == null){
                    temp.right = new Node(); …

"设计一种策略,最大限度地减少在下面的游戏[Gar94],#52中提出的预期问题数量.你有一副牌,其中包括一个黑桃王牌,两个黑桃牌,三个三分球,以及最多九个牌9,总共制作45张牌.有人从洗牌甲板上取出一张牌,你必须通过询问是否回答问题来识别.

这是算法的设计和分析练习.

我想到的是两种解决方法:

1. 它是9吗？不:是8岁吗？不:这是7吗？... 等等.

2. 卡> 5？不是:卡> 2？... 等等.

哪种方法正确？

欢迎任何帮助.

编辑:我应该使用贪婪的方法.

我想用Java创建一个快速的霍夫曼代码解码器，因此考虑了查找表。由于这些表占用内存，并且我们使用Java代码导航和访问表，因此可以轻松（或不容易）编写表示同一表的程序/方法。

这种方法的问题是，我不知道什么是最佳策略。我知道很多有关缓存和分支预测的内容。同样，切换案例的实现意味着实际的ASM在我之外。如果我有一个内存中查找表（或它的层次结构），则可以简单地跳入和跳出，但是出于我的目的，我建议将该表放入高速缓存中。

由于我实际上是走一棵树，因此可以像执行其他语句一样需要一定数量的比较来实现它，但是对于每个比较，它都需要附加的二进制运算。

因此存在以下选项：

• 内存查找表中使用的通用算法
• 决策树的if / else表示
• if / else表示法，使用小的switch语句查找正确的符号组（相同的位模式长度）（if语句较少，可能是更多代码）。
• 代码的switch语句表示

编写和基准测试非常棘手，因此任何初步想法都会很棒。

起作用的另一个问题是位的顺序。最重要的位始终位于最前面，这意味着它以相反的顺序存储。

如果您的树是A = 0，B = 10，C = 11以编写BAC，则它实际上是01 + 0 + 11（加上意味着追加）。

因此，实际上必须以相反的顺序编写代码。对组使用if / else或switch方法将不会有问题，因为屏蔽位很简单，并且位的反转也很可能，但是由于相反，它将失去将组内的索引移出掩码的想法位顺序的添加和删除具有不同的含义，并且不可能进行简单的查找。

反转位是一项昂贵的操作（我使用4位查找表），不会超过二进制操作的性能损失。

但是，在旅途中反转位更适合此操作，并且每位需要四个操作（上移，屏蔽，加法以及下移输入）。由于我提前读取了所有这些操作，因此所有这些操作都将在寄存器中完成，因此它们可能只需要几个周期。

这样，我可以使用switch，sub和if来找到正确的符号组并返回它们。

最后，我需要一些建议。由于我的代码在语言处理方面是全球通用的，因此可以进行硬连线（即在源代码中）。

我想知道像ANTRL这样的解析器生成器是用来表达那些决定的。由于他们也根据输入符号来缝制切换或是否/其他，这可能会给我一个提示。

[更新]

我发现了一种简化方法，可以避免反向位问题，但仍会增加每组的成本。因此，我最终按照要遍历的组的顺序编写了位。因此，我不需要每个位四个修改，而是每个组（不同的位长）。

对于每个组，我们都有：1.第一个元素的值，大小（以及该组中最后一个元素的值）。

因此，对于每个组，算法如下：1.读取mbits并与当前读取值组合。2.将值与该组的最后一个值进行比较，如果它不在该组中，则该值在该组中较小。->接下来阅读3.如果在组内，则可以访问值数组或使用switch语句。

这是完全通用的，可以不使用循环就可以有效地使用。同样，如果检测到该组，则代码的位长是已知的，并且可以从源中消耗这些位，因为代码看起来很远（从流中读取）。

[更新2]

要访问实际值，可以使用按组分组的单个大元素数组。由于按组分组的可传输性降低，因此很可能有相当一部分适合L2或L1缓存，从而加快了访问速度。

或者使用switch语句。

[更新3]

根据开关的情况，编译器会生成表开关或查找开关。查找开关的复杂度为O（log n），并存储密钥，jmp偏移对，因此不理想。因此，检查组更适合if / else。

tableswitch本身仅使用跳转偏移量表，并且仅需进行减法，比较，访问，jmp即可到达目标，而它必须对常量执行返回值。

因此，表访问看起来更有希望。另外，为了避免不必要的跳转，每个组可能包含访问和返回组符号表的逻辑。将所有内容存储在一个大表中是有希望的，因为每个符号可能是int或short，而我的代码通常最多只有1000到4000个符号，这实际上使它很短。

我将检查1-模式是否将使我有机会以更好的方式存储和访问掩码，从而允许二进制搜索正确的组而不是前进O（n），甚至可能在处理期间完全避免任何移位操作。

所以,我有那个用于编码字符串的Huffman树.我已经定义了这个功能plant,但我不确定我的树是不是只向一侧倾斜太多.这是我的代码:

data HuffTree
    = Leaf Char
    | HuffTree |*| HuffTree     
    deriving (Eq, Show)

|*| 是一个中缀构造函数.

plant :: [(Char,Int)] -> HuffTree
plant [(x,y)] = (Leaf x)
plant ((x,y):xs) = plant xs |*| (Leaf x) 

对我来说,它看起来是片面的,因此它实际上并不意味着编码的想法,因为它不是真正的二叉树.我怎么能把它变成一个普通的二叉树？

我需要使用包含ASCII和Huffman位之间的转换的文件来解码我用我的程序编码的霍夫曼代码.我已经在程序中从"代码"到ASCII这样的字典:

{'01110': '!', '01111': 'B', '10100': 'l', '10110': 'q', '10111': 'y'}

我创建了这个函数:

def huffmanDecode (dictionary, text) :

那需要字典和代码.我已经尝试在字典中搜索密钥并使用替换方法表单字符串和来自re的sub,但它们都没有正确地解码消息.例如,如果代码是:

011111011101110

它应该直接解码为:

By!

但我无法通过迭代代码和搜索字典中的匹配来做到这一点!

如何通过查找文本中的键并将其替换为值来使用字典中的键及其值来解码代码？

任何帮助是极大的赞赏.

我正在尝试实现霍夫曼树。

我想做一个简单测试的简单.txt文件的内容：

aaaaabbbbccd

字符频率：a：5，b：4，c：2，d：1

代码表：（1 s和0 s的数据类型：字符串）

a:0
d:100
c:101
b:11         

我想写为二进制的结果：（22位）

0000011111111101101100          

如何将结果的每个字符作为二进制逐位写入“ .dat”文件？（不是字符串）

刚才我看到这个：

这就是一个叫做霍夫曼编码的真正聪明的想法出现的地方！这个想法是我们用如下代码表示字符（例如a，b，c，d，...）。

a: 00
b: 010
c: 011
d: 1000
e: 1001
f: 1010
g: 1011
h: 1111

Run Code Online (Sandbox Code Playgroud)

如果仔细看这些，您会发现一些特别的地方！这些代码都不是任何其他代码的前缀。因此，如果我们写下来，010001001011我们可以看到它是010 00 1001 011或baec！有没有任何歧义，因为0和01和0100没有任何意义。

我领会了这一要点，但我不明白（a）它是如何被发现的，以及（b）您如何知道它是如何工作的，或者（c）它到底是什么意思。此行具体描述了它：

因此，如果我们写下来，010001001011我们可以看到它是010 00 1001 011...。

我看到这些是代码，但我不明白您怎么知道不以的形式阅读0100 01 0010 11。我看到这些值实际上不是表中的代码。但是，我看不出您将如何解决这个问题！我想知道如何发现这一点。如果我试图修改这样的代码和位，我会这样做：

1. 提出一组代码，例如 10 100 1000 101 1001
2. 尝试写出一些代码示例。因此，也许一个示例只是按上述顺序连接代码：1010010001011001。
3. 看看我是否可以解析代码。所以10还是哎呀，没了101还... Darnit，那也许是因为我可以优先添加到代码的解析，所以10比更高的优先级101。那让我10 100 1000 10 x不知道最后10个应该是101。Dangit。

因此，我将尝试添加诸如优先级功能之类的其他功能，或目前我无法想到的其他功能，以查看它是否有助于解决问题。

我无法想象他们会如何发现霍夫曼编码中的这些代码可以被唯一地解析（我仍然看不到它，它实际上是如何实现的，我必须写一些示例才能看到它，或者。 …

我正在为著名的霍夫曼编码算法编写代码。我收到一个致命错误，将系统变成蓝屏然后重新启动。此错误发生在具有递归调用的 display_Codes 中。错误发生在以下几行：

display_Codes(root->l, s + "0"); 
display_Codes(root->r, s + "1" );

以下是完整代码。

#include <iostream>

#include <bits/stdc++.h> 

using namespace std;




class HeapNode_Min {




public:


char d; 

unsigned f; 

HeapNode_Min *l, *r;
HeapNode_Min(char d, unsigned f) 
{ 

      this->d = d;
      this->f = f;
}




~HeapNode_Min()
 {
   delete l;
   delete r;
 } 
}; 



class Analyze {  

  public:
    bool operator()(HeapNode_Min* l, HeapNode_Min* r) 
    { 
        return (l->f > r->f);
    } 
}; 



void display_Codes(HeapNode_Min* root, string s) 
{   
    if(!root) 
        return; 

    if (root->d != '$') 
        cout …

我知道这不是编码问题，但因为我在这里发现了一些霍夫曼问题，所以我在这里发布，因为我的实现仍然需要这个。在进行扩展霍夫曼编码时，我知道您会执行例如 a1a1、a1a2、a1a3 等操作，并且您会执行它们的概率时间，但是，您如何获得代码字？例如，从下图中你如何得到 0.6400 = 0 和 0.0160 = 10101 等？

我想将JPEG文件转换为其二进制等效项,然后将其转换回JPEG格式.即将JPEG文件转换为1和0并将其输出到文本文件中,然后获取此文本文件并将其转换回原始图像(只是为了检查转换中是否没有错误)

我试过用python中的binascii模块做这个,但似乎有一个我无法理解的编码问题.

如果有人可以帮我解决这个问题真的很棒!

PS:Java中的解决方案将更受欢迎