3

我在学术目的上写了一个关于haskell的小（相对）应用程序。我正在基于此代码http://www.haskell.org/haskellwiki/Toy_compression_implementations实现霍夫曼压缩。

我的此代码变体在这里https://github.com/kravitz/har/blob/a5d221f227c27fd1c5587217a29a169a377521a6/huffman.hs它使用惰性字节串。当我实现 RLE 压缩时，一切都很顺利，因为它一步处理输入流。但是 Huffman 对其进行了两次处理，结果我在内存中存储了一个评估的字节串，这对大文件不利（但对于相对较小的文件，它也在堆中分配了太多空间）。这不仅是我的怀疑，因为 profiling 还表明大部分堆都被字节串分配吃掉了。

此外，我在文件中序列化流长度，它也可能导致完整的字节串加载到内存中。有什么简单的方法可以说 ghc 友善并多次重新评估流？

4

2 回答 2

4

您可以传递一些计算字节串的东西，然后在每次需要时显式地重新计算该值，而不是将字节串传递给编码器。

compress :: ST s ByteString -> ST s ByteString
compress makeInput = do
  len      <- (return $!) . ByteString.length =<< makeInput
  codebook <- (return $!) . makeCodebook      =<< makeInput
  return . encode len codebook                =<< makeInput

compressIO :: IO ByteString -> IO ByteString
compressIO m = stToIO (compress (unsafeIOToST m))

参数 tocompress应该实际计算值。简单地包装一个值是return行不通的。此外，每次调用都makeInput必须实际评估其结果，否则当重新计算输入时，内存中将保留一个惰性的、未评估的输入副本。

正如barsoap所说，通常的方法是一次只压缩一个块。

于 2011-02-16T14:53:49.667 回答
3

（Huffmann-）压缩时的常用方法，因为无法绕过两次处理输入，一次收集概率分布，一次进行实际压缩，是将输入分块并分别压缩。虽然这仍然会消耗内存，但它只会最大程度地消耗一个恒定的量。

也就是说，您可能想看看bytestring-mmap，尽管它不适用于标准输入、套接字和其他不受支持 mmap 的文件系统支持的文件描述符。

在收集概率分布之后，您还可以从文件中重新读取字节串（再次，前提是您没有从任何类似管道的东西中接收它），但这仍然会使您的代码在 1TB 文件上得到释放。

于 2011-02-16T14:39:47.960 回答