炎炎设计
由于您已经必须实现代码以按字节组织的流/文件之上处理按位层，因此这是我的建议。不要存储实际频率，解码不需要它们。但是，您确实需要实际的树。因此，对于每个节点，从根目录开始：如果是叶节点：输出1位+ N位字符/字节如果不是叶节点，则输出0位。然后以相同的方式编码两个子节点（先左后右）要阅读，请执行以下操作：读取位。如果为1，则读取N位字符/字节，返回其周围没有子节点的新节点如果bit为0，则用相同的方式解码左右子节点，并用这些子节点返回周围的新节点，但没有值叶节点基本上是没有子节点的任何节点。使用这种方法，您可以在编写输出之前计算出确切的输出大小，以判断增益是否足以证明工作的合理性。假设您有一个键/值对字典，其中包含每个字符的出现频率，其中频率是实际出现的次数。用于计算的伪代码：Tree-size = 10 * NUMBER_OF_CHARACTERS - 1Encoded-size = Sum(for each char,freq in table: freq * len(PATH(char)))树大小的计算考虑了叶子节点和非叶子节点，并且内联节点比字符少一个。SIZE_OF_ONE_CHARACTER将是位数，而这两个位数将为您提供我的树+编码数据所占用的位数。PATH（c）是一个函数/表，它将产生从根到树中该字符的位路径。这是一个看起来像C＃的伪代码，它假定一个字符只是一个简单的字节。void EncodeNode(Node node, BitWriter writer){ if (node.IsLeafNode) { writer.WriteBit(1); writer.WriteByte(node.Value); } else { writer.WriteBit(0); EncodeNode(node.LeftChild, writer); EncodeNode(node.Right, writer); }}要重新阅读：Node ReadNode(BitReader reader){ if (reader.ReadBit() == 1) { return new Node(reader.ReadByte(), null, null); } else { Node leftChild = ReadNode(reader); Node rightChild = ReadNode(reader); return new Node(0, leftChild, rightChild); }}一个示例（简化，使用属性等）节点实现：public class Node{ public Byte Value; public Node LeftChild; public Node RightChild; public Node(Byte value, Node leftChild, Node rightChild) { Value = value; LeftChild = leftChild; RightChild = rightChild; } public Boolean IsLeafNode { get { return LeftChild == null; } }}这是一个特定示例的示例输出。输入：AAAAAABCCCCCCDDEEEEE频率：答：6B：1C：6D：2E：5每个字符只有8位，因此树的大小将为10 * 5-1 = 49位。这棵树可能看起来像这样： 20 ---------- | 8 | ------- 12 | 3----- | -----A C E B D6 6 5 1 2因此，每个字符的路径如下（左为0，右为1）：A：00乙：110C：01D：111E：10因此要计算输出大小：A：6次出现* 2位= 12位B：1次出现* 3位= 3位C：6次出现* 2位= 12位D：2次出现* 3位= 6位E：5次出现* 2位= 10位编码字节的总和是12 + 3 + 12 + 6 + 10 = 43位将其添加到树的49位中，输出将为92位或12个字节。将其与存储未经编码的原始20个字符所需的20 * 8个字节进行比较，您将节省8个字节。最终的输出（包括开始的树）如下。流（AE）中的每个字符都被编码为8位，而0和1只是一个位。流中的空间仅用于将树与编码数据分开，并且在最终输出中不占用任何空间。001A1C01E01B1D 0000000000001100101010101011111111010101010对于注释中包含的具体示例AABCDEF，您将获得以下信息：输入：AABCDEF频率：A2B：1C：1D：1E：1F：1树： 7 ------------- | 4 | --------- 3 2 2----- ----- -----A B C D E F2 1 1 1 1 1路径：A：00B：01C：100D：101E：110传真：111树：001A1B001C1D01E1F = 59位数据：000001100101110111 = 18位总和：59 + 18 = 77位= 10字节由于原始字符是8个位的7个字符= 56，所以这样的小数据块会有太多开销。