标签: huffman-code

我以为我可以自己解决这个问题,但我似乎根本没有前进.

好的,背景:

我需要根据jpg文件中FFC4,DHT(Define Huffman Table)标头提供的信息创建一个Huffman代码树.DHT标头以这种方式定义Huffman表:

1)一系列16个字节.每个字节定义有多少符号具有n位的霍夫曼码,其中n是系列中字节的位置.(这有什么意义吗？!!)例如,十六进制的原始数据是:

00 01 05 01 01 01 ... 00

这意味着:

Num of bits:    1   2   3   4   5   6   7 ...  16  
Num of codes:   00  01  05  01  01  01  01 ... 00

2)在16个字节的列表之后出现实际的符号本身.例如:

00 01 02 03 04 05 06 07 08 09 0A 0B

3)结合这两部分,我们看到它们是:
00代码,1位.
01代码有2位:所以从列表中取第一个符号:00
05代码3位:所以从列表中取下一个5个符号:01 02 03 04 05
..等等

4)最后,我们必须根据上述信息计算出实际的霍夫曼代码.如果你是一个数学天才,你可能已经发现这些代码可以通过简单地为某个位长度的每个新代码增加一个具有适当位数的二进制数来计算出来.当位长增加时,只需增加二进制数,然后将其加倍并继续.当你手工绘制出一些二元树时,对其他人来说显而易见......

5)所以这是我用来计算霍夫曼代码并将它们存储在数组中的代码:(首先我在1读取数据)并将其放在一个数组中:dhtBitnum)

            int binaryCode = 0;
            count = 0;
            StringBuffer codeString = new StringBuffer();               

            //populate array with code strings …

我试图通过读取文件并计算每个字母空格符号的频率等来创建一个霍夫曼树.我正在使用Priorityqueue将项目从最小到最大排队但是当我将它们插入队列时它们不能正确排队这是我的代码.包霍夫曼;

import java.io.FileNotFoundException; import java.io.FileReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner;

公共课霍夫曼{

public ArrayList<Frequency> fileReader(String file)
{
    ArrayList<Frequency> al = new ArrayList<Frequency>();
    Scanner s;
    try {

        s = new Scanner(new FileReader(file)).useDelimiter("");
        while (s.hasNext())
        {
            boolean found = false;
            int i = 0;
            String temp = s.next();
            while(!found)
            {


                if(al.size() == i && !found)
                {
                    found = true;
                    al.add(new Frequency(temp, 1));
                }
                else if(temp.equals(al.get(i).getString()))
                {
                    int tempNum = al.get(i).getFreq() + 1;
                    al.get(i).setFreq(tempNum);
                    found = true;
                }
                i++;

            }



        }
    } catch …

甲前缀代码是一组代码,使得没有代码的另一代码前缀.例如,以下集合是前缀代码:

10
11
000
001
0100
0101
0110
0111

有n = 8会员.我认为这些通常是用某种类型的霍夫曼树创造的.

我的问题是:你能帮助我创建一个能够生成带'n'成员的二进制前缀代码的函数吗？

像这样的东西:

list<int> GenerateBinaryPrefixCodes(int n);

而且,要求是在总位数最小化的意义上它是"最佳的".

我更喜欢用C/C++/C#/类似的答案.这不是真正的功课,但我标记它是因为它听起来像是一个很好的hw问题.

谢谢!

我有以下字符串，需要霍夫曼编码并将其有效地存储到位数组中：

>>> print sequence
GTCAGGACAAGAAAGACAANTCCAATTNACATTATG|

中的符号频率为sequence：

>>> print freqTuples
[(0.40540540540540543, 'A'), (0.1891891891891892, 'T'), (0.16216216216216217, 'C'), (0.16216216216216217, 'G'), (0.05405405405405406, 'N'), (0.02702702702702703, '|')]`

我将其翻译成霍夫曼代码字典：

>>> print codeDict
{'A': '1', 'C': '010', 'G': '001', 'N': '0110', 'T': '000', '|': '0111'}

然后，我使用Python bitstring包将字符串逐个字符地转换为BitArray该类的实例，我称之为bitArray，该实例包含每个用其各自的霍夫曼代码编码的字符的位：

>>> print bitArray.bin
0b001000010100100110101100111100110101101100000100101100000001101010100000010000010111

这是位数组，以字节为单位：

>>> print bitArray.tobytes()
!I\254\363[^D\260^Z\240Ap

我必须使用tobytes()而不是bytes，因为我生成的位数组不能平均分为8位段。

当我计算表示的存储效率BitArray（位数组和输入字符串的大小之比）时，与未对输入字符串进行未编码的情况相比，我得到的性能更差：

>>> sys.getsizeof(bitArray.tobytes()) / float(len(sequence))
1.2972972973

我是否正确测量存储效率？（如果我对更长的输入字符串进行编码，则该比率会提高，但似乎接近0.28的渐近极限。我想确认这是否是正确的度量方法。）

编辑

以下两种方法得出不同的答案：

>>> print len(bitArray.tobytes()) / float(len(mergedSequence))
0.297297297297

>>> print bitArray.len …

我正在尝试用c ++实现Huffman的编码算法.

我的问题是:在我得到每个字符的等效二进制字符串后,如何将这些0和1作为二进制写入文件而不是字符串0或字符串1？

提前致谢 ...

我想知道如何处理我的作业问题.我正在尝试创建一个将用Java编码和解码消息的霍夫曼树.我有字符串和频率.

[a=10, b=15, c=12, e=3, nl=4, sp=13, t=1]. 

我知道,对于霍夫曼树,你可以选择两个最低的频率,然后将它们变成一棵树,其频率为总和.我知道使用优先级队列我可以将所有频率插入其中并使用该remove()方法取出2个最低频率.然后将它们加在一起以获得它们的重量,然后将该重量插入队列并重复.

最终的树应该保持重量

[58=root, root.left = 33, root.right = 25]   
[33.left = 18,  18.left = 8,  8.left = 4] 

我不确定如何开始实现一个能够用频率创建树并显示树的霍夫曼树代码.我看看其他代码,似乎他们都是从Streaming Input Code创建的.

让我走的任何帮助都会很棒.提前致谢!

我想用以下格式打印出来:(预订遍历)

58  
- 33  
- - 18  
- - - 8  
- - - - 4  
- - - - - 1:t  
- - - - - 3:e  
- - - -  4:nl  
- - - 10:a  
- - 15:b  
- 25  
- - 12:c  
- - 13:sp  

我编写了一个算法来实现Huffman Coding来压缩文本文件.它基本上将字符串作为输入,并生成一串位作为输出.但是,我在存储这个二进制数据时遇到了问题,因为它存储为一个字符串,其中每个位都是一个字符,并占用2个字节的内存用于存储.最终结果,输出文件大于输入,使整个程序一文不值.我应该如何存储这个二进制输出,使每个位只占用一位内存用于存储？PS.我尝试过使用BitSet,但根本没有改变输出的大小

我的朋友告诉我它存在,但我找不到它,不确定他是否在撒谎,但我对证明如何运作非常感兴趣.(是的,我是那些从硅谷电视节目中发现霍夫曼编码的人之一,抱歉)

我正在尝试编写一种算法来执行霍夫曼解码.我在Scala中这样做 - 这是Coursera课程的作业,我不想违反荣誉代码,所以下面是伪代码而不是Scala.

我编写的算法采用树tree和位列表bits,并且应该返回消息.但是,当我在提供的树上尝试它时,我得到一个NoSuchElementException(空列表的头部).我不明白为什么.

我知道我的代码可以整理一下 - 我对函数式编程仍然很陌生,所以我用一种对我有意义的方式编写它,而不是以最紧凑的方式编写.

def decode(tree, bits) [returns a list of chars]: {

    def dc(aTree, someBits, charList) [returns a list of chars]: {

        if aTree is a leaf: 

            if someBits is empty: return char(leaf) + charList
            else: dc(aTree, someBits, char(leaf) + charList)

        else aTree is a fork:

            if someBits.head is 0: dc(leftFork, someBits.tail, charList)
            else someBits is 1:  dc(rightFork, someBits.tail, charList)
        }

     dc(tree, bits, [empty list])

     }

在此先感谢您的帮助.这是我第一次使用StackOverflow,所以我可能有一些学习如何最好地使用该网站.

我最近申请了一份工作,并在几个问题上发了一个hackerrank考试.其中一个是霍夫曼解码算法.有可用的类似的问题在这里这也解释了格式化好了很多,然后我可以.

实际的任务是获取两个参数并返回已解码的字符串.

第一个参数是代码,它是一个字符串数组,如:

[
    "a      00",
    "b      101",
    "c      0111",
    "[newline]      1001"
]

这就像:单个字符,两个标签,霍夫曼代码.

由于黑客级别的设置方式,新行被指定为采用此格式.

第二个参数是使用代码解码的字符串.例如:

101000111 = bac

这是我的解决方案:

function decode($codes, $encoded) {
    $returnString = '';
    $codeArray = array();

    foreach($codes as $code) {
        sscanf($code, "%s\t\t%s", $letter, $code);
        if ($letter == "[newline]")
            $letter = "\n";
        $codeArray[$code] = $letter;
    }
    print_r($codeArray);

    $numbers = str_split($encoded);
    $searchCode = '';
    foreach ($numbers as $number) {
        $searchCode .= $number;
        if (isset($codeArray[$searchCode])) {
            $returnString .= $codeArray[$searchCode];
            $searchCode = '';
        }
    }

    return $returnString;
} …