3

私はアカデミックな目的でhaskellに関する小さな（比較的）アプリケーションを書いています。このコードhttp://www.haskell.org/haskellwiki/Toy_compression_implementationsに基づいて、ハフマン圧縮を実装しています。

このコードの私の変種はここhttps://github.com/kravitz/har/blob/a5d221f227c27fd1c5587217a29a169a377521a6/huffman.hsであり、遅延バイト文字列を使用します。RLE圧縮を実装したとき、入力ストリームを1つのステップで処理するため、すべてがスムーズでした。しかし、ハフマンはそれを2回処理し、その結果、評価されたバイト文字列がメモリに格納されます。これは、大きなファイルには適していません（ただし、比較的小さなファイルの場合は、ヒープに割り当てられるスペースも多すぎます）。これは私の疑いだけではありません。プロファイリングでは、ヒープのほとんどがバイト文字列の割り当てによって消費されていることも示されているためです。

また、ファイル内のストリームの長さをシリアル化すると、メモリに完全なバイト文字列が読み込まれる可能性があります。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 が言ったように、通常のアプローチは、一度に 1 ブロックずつ圧縮することです。

于 2011-02-16T14:53:49.667 に答える
3

（ハフマン-）圧縮の通常のアプローチは、入力を2回処理することを回避できないため、1回は確率分布を収集し、もう1回は実際の圧縮を行うために、入力をブロックに分割し、それぞれを個別に圧縮することです。それはまだ記憶を食べますが、それは最大限に一定量しか食べません。

とは言うものの、 bytestring-mmapを確認することをお勧めしますが、mmapをサポートするファイルシステムによってサポートされていない標準の入力、ソケット、およびその他のファイル記述子では機能しません。

確率分布を収集した後、ファイルからバイト文字列を再読み取りすることもできます（ただし、パイプのようなものからバイト文字列を受信して​​いない場合）。ただし、それでも、たとえば1TBファイルでコードがベイルアウトされます。

于 2011-02-16T14:39:47.960 に答える