Java - 压缩字节时如何处理特殊字符（霍夫曼编码）？

Question

我正在编写霍夫曼压缩/解压缩程序。我已经开始编写我的压缩方法，但我陷入困境。我试图读取文件中的所有字节，然后将所有字节放入字节数组中。将所有字节放入字节数组后，我创建一个int[]数组，用于存储每个字节的所有频率（索引为 ASCII 代码）。

它确实包含扩展 ASCII 表，因为int数组的大小为 256。但是，当我在文件中读取特殊字符（又名 ASCII 值高于 127 的字符）时，我就会遇到问题。我知道一个字节是有符号的，一旦超过 127 个数字限制（并且数组索引显然不能为负数），它就会环绕为负值，因此我尝试通过在指定时将其转换为有符号值来解决此问题我的数组索引 ( array[myByte&0xFF])。

这种方法有效，但它给了我错误的 ASCII 值（例如，如果字符的正确 ASCII 值是 134，我反而得到 191 或其他值）。更烦人的是，我注意到特殊字符被分成 2 个单独的字节，我觉得这会在以后引起问题（例如当我尝试解压缩时）。

如何使我的程序与每种类型的字符兼容（该程序应该能够压缩/解压缩图片、mp3 等）。

也许我对此采取了错误的方法，但我不知道正确的方法是什么。请给我一些构建这个的提示。

树：

package CompPck;

import java.util.TreeMap;

abstract class Tree implements Comparable<Tree> {
    public final int frequency; // the frequency of this tree
    public Tree(int freq) { frequency = freq; }

    // compares on the frequency
    public int compareTo(Tree tree) {
        return frequency - tree.frequency;
    }
}

class Leaf extends Tree {
    public final int value; // the character this leaf represents

    public Leaf(int freq, int val) {
        super(freq);
        value = val;
    }
}

class Node extends Tree {
    public final Tree left, right; // subtrees

    public Node(Tree l, Tree r) {
        super(l.frequency + r.frequency);
        left = l;
        right = r;
    }
}

建树方法：

public static Tree buildTree(int[] charFreqs) {
        PriorityQueue<Tree> trees = new PriorityQueue<Tree>();

        for (int i = 0; i < charFreqs.length; i++){
            if (charFreqs[i] > 0){
                trees.offer(new Leaf(charFreqs[i], i));
            }
        }

        //assert trees.size() > 0;

        while (trees.size() > 1) {
            Tree a = trees.poll();
            Tree b = trees.poll();

            trees.offer(new Node(a, b));
        }
        return trees.poll();
    }

压缩方法：

public static void compress(File file){
        try {
            Path path = Paths.get(file.getAbsolutePath());
            byte[] content = Files.readAllBytes(path);
            TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();
            File nF = new File(file.getName() + "_comp");
            nF.createNewFile();
            BitFileWriter bfw = new BitFileWriter(nF);

            int[] charFreqs = new int[256];

            // read each byte and record the frequencies
            for (byte b : content){
                charFreqs[b&0xFF]++;
                System.out.println(b&0xFF);
            }

            // build tree
            Tree tree = buildTree(charFreqs);

            // build TreeMap
            fillEncodeMap(tree, new StringBuffer(), treeMap);

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

Answer 1

编码很重要

\n

\n

如果我获取字符“\xc3\xb6”并在我的文件中读取它，那么当其实际 ASCII 表值为 148 时，它现在将由 2 个不同的值（191 和 182 或类似的值）表示。

\n

\n

这实际上取决于使用哪种编码来创建文本文件。编码决定文本消息的存储方式。

\n

\n
• 在 UTF-8 中，\xc3\xb6 存储为十六进制[0xc3, 0xb6]或[195, 182]
\n
• 在 ISO/IEC 8859-1 (= "Latin-1") 中，它将存储为 hex [0xf6]，或[246]
\n
• 在 Mac OS Central Europe 中，它将是十六进制[0x9a]或[154]
\n

\n

请注意，基本 ASCII 表本身并没有真正描述此类字符的任何内容。ASCII 仅使用 7 位，因此仅映射 128 个代码。

\n

\n

部分问题在于，用外行人的话来说，“ASCII”有时也用于描述 ASCII 的扩展（例如 Latin-1）

\n\n

历史

\n

这背后实际上有一些历史。最初 ASCII 是一组非常有限的字符。当这些还不够时，每个地区开始使用第 8 位来添加其语言特定的字符。导致各种兼容性问题。

\n

然后有某种联盟对所有可能的语言（及其他语言）的所有字符进行了清单。该集合称为“unicode”。它不仅包含 128 或 256 个字符，而且包含数千个字符。

\n

从那时起，您将需要更高级的编码来覆盖它们。UTF-8 是涵盖整个 unicode 集的编码之一，并且它在某种程度上向后兼容 ASCII。

\n

每个 ASCII 字符仍然以相同的方式映射，但是当 1 个字节不够时，它将使用第 8 位来指示后面将有第 2 个字节，这就是字符的情况\xc3\xb6。

\n\n

工具

\n

如果您使用的是更高级的文本编辑器（例如 Notepad++），那么您可以从下拉菜单中选择编码。

\n

\n\n

在编程中

\n

话虽如此，您当前的 java 源读取字节，而不是读取字符。我认为当它在字节级别工作时它是一个优点，因为这样它就可以支持所有编码。也许你根本不需要在角色层面上工作。

\n

但是，如果这对您的特定算法确实很重要。假设您编写了一个仅处理 Latin-1 编码的算法。因此，它实际上将在“字符级”而不是“字节级”上工作。在这种情况下，请考虑直接读取String或char[]。

\n

在这种情况下，Java 可以为您完成繁重的工作。java 中有一些阅读器可以让您将文本文件直接读取到 Strings/char[]。但是，在这些情况下，您当然应该在使用它们时指定编码。在内部，单个 java 字符最多可以包含 2 个字节的数据。

\n

尝试手动将字节转换为字符是一件棘手的事情。当然，除非您使用的是普通的老式 ASCII。当您看到高于 0x7F (127) 的值（在 中由负值表示byte）时，您就不再使用简单的 ASCII。然后考虑使用类似的东西：new String(bytes, StandardCharsets.UTF_8)。无需从头开始编写解码算法。

\n