在另一个字符串中查找字符串子集的最快方法？

我正在解码由huffman编码产生的字节文件，我将字节转换为字符串，然后搜索huffman树给出的值。我有一个哈希表与原始文件的编码值和字节值。这是我的代码。在另一个字符串中查找字符串子集的最快方法？

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;  

     }

它很简单，它是itterates在所有的串回路，问题就来了，当串中的过大，-with压缩尺寸是100KB-它需要很长的时间来处理他们的文件，所以我想知道它是否以更快的方式使这个过程的方式，或者如果它更好地将我的编码值存储在另一个hastable的结构体系中。

huffEncodeTable - >散列表

encodedString - > String与霍夫曼值

decodedString - >将代表原始文件

来源

2013-04-24 Pedro

我会将你的结果与内置的huffman编码进行比较（尽管大多数代码是使用本地代码实现的）内置压缩还使用算术编码，可以使数据再次变小。标准压缩的搜索范围有多远。 4 KB。这也使编码回看起来更容易。 – 2013-04-24 20:32:08

我只使用了哈夫曼，它真的很好压缩som类型的文件，但是我没看到的是这个循环需要很长时间，所以我问什么我应该在这里改变。 – Pedro 2013-04-24 20:38:50

内置的huffman编码可以支持多GB文件，而不需要花费更长的时间，所以如果是这样做的话，我怀疑你有一个bug（如果只是一个性能bug）额外的算术压缩可以使它再次变小2到10倍。 – 2013-04-24 20:44:27

一些建议原字节的字符串：

每次追加到字符串时，都会创建一个新字符串。您应该改用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-24 20:45:29 femtoRgon

谢谢很多人让我试试这个=） – Pedro 2013-04-24 20:47:40

男人非常感谢，它增加了很多解码过程谢谢=） – Pedro 2013-04-24 20:52:58

对不同长度的字符串使用子字符串会降低速度。在Java 7中，它需要创建两个对象的原始字符串的副本。创建一个子字符串并根据NavigableMap进行搜索会更好。

使用的NavigableMap将让你找到最长匹配字符串中的一个操作，并减少你需要在地图存储串的数目。

注意：即使是这样地图的大小将是O（N^2），其中N是最大字符串长度，你可以回头看看，所以你必须把对N的大小合理限制

注2：您将很幸运能够获得内置huffman代码速度的十分之一（这是为您编写的，是标准的和有效的）因此，如果性能很重要，请使用它。

来源

2013-04-24 20:53:36

在另一个字符串中查找字符串子集的最快方法？

回答

相关问题