早教吧 育儿知识 作业答案 考试题库 百科 知识分享

C++题目:字符串S为“abcdeacedaeadcedabadadaead”,对该字符串用[0,1]进行前缀编码,问该字符串的编码至少有多少位。

题目详情
C++题目:字符串S为“abcdeacedaeadcedabadadaead” ,对该字符串用[0,1]进行前缀编码,问该字符串的编码至少有多少位。
▼优质解答
答案和解析

楼下回答都不着边。前缀编码就是Huffman编码。

  1. 字母共abcde,每个出现次数a=9,b=2,c=3,d=7,e=5.

  2. 构造huffman数和编码,过程略(懒得画树)。得到

    a:10, b:000, c:001, d:11, e:01 (编码不唯一)。

  3. 知道编码了,总长度是2*9+2*3+3*3+2*7+2*5=57位。

(口算的可能有计算错误,思路就是这样)