2011-12-27 21 views
2

実際の圧縮ファイルデータがすべて挿入された後、圧縮ファイルにハフマンツリーを書き込もうとしています。しかし、私はちょっとした問題を認識しました。私の実際のデータがすべてファイルに書き込まれたら、2つの改行文字を入力してツリーを書きます。 つまり、私は物を読んで、これらの2つの改行(または本当に任意の文字)は私の区切り文字です。問題は、実際のデータにも2つの改行が連続して存在することが完全に可能であることです。このようなシナリオでは、区切り文字のチェックは失敗します。 ここでは2つの改行の例を取り上げましたが、文字列にも同じことが当てはまりますが、長い文字列を区切り文字として使用することで問題を覆すことができますが、それは2つの嫌な結果をもたらすでしょう: 1.長い文字列が圧縮されたデータに一致している可能性があります。 2.圧縮する必要のあるファイルを必ずしも膨らませません。圧縮後のファイルへのハフマンツリーの書き込み

圧縮データをツリーデータから分離する方法はありますか?

答えて

3

まず、ツリーのサイズをバイト単位で書き込みます。次に、ツリー自体と内容そのものを書きます。

読んでいるときは、最初にサイズを読んでから、次にツリーを読んでください。

サイズは改行で終わる文字列として書くことができます。この方法で、最初の数字と改行はツリーのサイズに属することがわかります。

+0

これは私が最初にやったと思ったことですが、問題は木が巨大になることです!だから私はIntegerを書く必要があります、それはそこに4バイトです! それを文字列として書くと、そこに入れた整数ごとに1バイトを使用します。一度に2または3ビットを節約することで、圧縮することを試みているプログラムにとってはあまり効率的ではありません。 – angryInsomniac

+0

木がどのくらい大きくなると思いますか?数キロバイトですか? – Giorgio

+0

@angryInsomniacそれはさらに悪いことです。適切な条件の下で 'size(tree)+ size(compressed_data)'は 'size(original_data)'より大きくなる可能性があります。あなたのアルファベットが小さく、データが巨大である(均一に分布していない)場合は、明らかに意味があります。 コミュニケーションのビット数を最小限に抑えることに興味があれば(辞書を考慮して)、コミュニケーションの複雑さという理論的なコンピュータサイエンス(オープン)の研究分野があります:) – user1071136

0

なぜ、最初の8バイト(4バイト)にサイズとlenを書いてからデータを書いてみませんか? その後のようなもの:

uint32_t compressed_size; 
uint32_t data_len; 
char * data; 

file.read((char*)compressed_size, 4); 
file.read((char*)data_len, 4); 
data = new char[data_len]; 
zip.read(data, data_len); 

が動作するはずです。 より良い圧縮のためにデータを収縮させることができます。

関連する問題