1

我正在解码由霍夫曼编码生成的字节文件，我将字节转换为字符串，然后搜索霍夫曼树给出的值。我有一个哈希表，其中包含原始文件的编码值和字节值。这是我的代码。

for(int i = 0, j = 1; j <= encodedString.length(); j++){

        if(huffEncodeTable.get( encodedString.substring(i, j)) != null){

            decodedString.append(huffEncodeTable.get( encodedString.substring(i, j)));
            i = j;      

        }

它非常简单，它是一个遍历所有字符串的循环，当字符串太大时问题就来了 - 压缩文件的大小大于 100KB - 处理它们需要很长时间，所以我想知道是否这是一种以更快的方式进行此过程的方法，或者如果将我的编码值存储在另一个结构中而不是 hastable 中更好。

huffEncodeTable -> 哈希表

encodedString -> 带有霍夫曼值的字符串

decodedString -> 表示原始文件的原始字节的字符串

4

2 回答 2

0

对不同长度的字符串使用子字符串确实会减慢速度。在 Java 7 中，它使用原始字符串的副本创建两个对象。您最好创建一个子字符串并针对 NavigableMap 进行搜索。

使用 NavigableMap 将允许您在一次操作中找到最长的匹配字符串，并减少您需要存储在地图中的字符串数量。

注意：即使如此 Map 的大小将是 O(N^2) 其中 N 是您可以回顾的最大字符串长度，因此您必须对 N 的大小设置合理的限制。

注意 2：您将很幸运能够达到内置霍夫曼代码（为您编写，标准且有效）的十分之一的速度，因此如果性能很重要，请使用它。

于 2013-04-24T20:53:36.020 回答
0

几个建议：

每次附加到字符串时，都会创建一个新字符串。你应该StringBuilder改用。正如我所看到的，这可能是主要问题。

另外，我会使用hashtable.containsKey而不是get检查密钥的存在。我怀疑它会影响你的表现。

如果将调用结果存储到子字符串，也可以节省一点时间，因此只调用一次。

所以，类似的东西。

StringBuilder sb = new StringBuilder()
String currentString;
for(int i = 0, j = 1; j <= encodedString.length(); j++){
    currentString = encodedString.substring(i, j)
    if(huffEncodeTable.containsKey( currentString )){

        sb.append(huffEncodeTable.get( currentString ));
        i = j;      

    }
}
return sb.toString(); //Or whatever you do with it.
于 2013-04-24T20:45:29.070 回答