如何强制 haskell 不存储整个字节串？

Question

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

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

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

Answer 1

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

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))

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

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

Answer 2

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

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

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