4

私は、選択した圧縮アルゴリズムを実装するためのコースワークを与えられました。どの言語でもかまいませんが、私が最もよく知っている言語は Java で、次に C です。以下に基づいて評価されます。

  1. 圧縮解除された出力は元の入力と一致する必要があるため、損失の少ないアルゴリズムしか見ることができません。

  2. 実行時間は、メッセージの長さに比例する必要があります。

  3. メモリ要件は、メッセージの長さとは無関係でなければなりません。

私たちの実装は次のようにテストされます -

  1. 標準テキストファイル

  2. 0 ～ 255 のバイト値を持つバイナリ ファイル

  3. 未指定のコンテンツの最大 10 MB の大きなファイル。

私の最初の考えは、動的算術コーディングを使用することですが、上記の制約により適したアルゴリズムがあるかどうか疑問に思っていますか? 次に、Java ではなく C で行う方が良いでしょうか? Cの方がメモリフットプリントが小さいと思うので、これを尋ねますが、実際にそうであるかどうかはわかりません。

この質問をグーグルで検索したところ、動的ハフマン コーディングと組み合わせた LZW コーディングについて言及しているサイトがいくつかありました。これは追求するのに賢明な道でしょうか？私たちの講師は、何年にもわたって動的ハフマン コーディングを試みた提出物の 90% が正しく実装されていないと警告しました。

そうは言っても、試してみることを恐れていませんが、始める前にいくつかの意見を尊重します.

どんなフィードバックでも大歓迎です。

4

3 に答える 3

4

LZW だけで、他のコーディングはなく、非常に単純で、驚くほどうまく機能します。より高速に圧縮できるアルゴリズムが他にあるため、今日では実際に LZW を使用する人はいません。ただし、課題に関しては、LZW のシンプルさに勝るものはありません。動的かどうかに関係なく、ハフマンはありません。いいえシャノンファノ。算術または範囲コーディングはありません。はい、メモリ使用量はメッセージの長さとは無関係です。Mark Nelson は非常に良い説明を書いています。

C または Java で実行できますが、C には符号なしの型があるため、エラーが発生しにくい可能性があります。

于 2013-03-15T04:29:48.553 に答える
1

私自身の質問に答えるには、シャノンファノはそのような任務に「十分に良い」はずです。データ圧縮の分野で何もしたことがない場合は、ハフマンコーディング（または算術コーディングの特殊バージョン）から離れることをお勧めします。

これによると、SFはあなたの空間/時間の要件を満たしています。最初にそのようなものを実装することをお勧めします。擬似コードは次のように与えられます。

 1:  begin
 2:     count source units
 3:     sort source units to non-decreasing order
 4:     SF-SplitS
 5:     output(count of symbols, encoded tree, symbols)
 6:     write output
 7:   end
 8:  
 9:  procedure SF-Split(S)
10:  begin
11:     if (|S|>1) then
12:      begin
13:        divide S to S1 and S2 with about same count of units
14:        add 1 to codes in S1
15:        add 0 to codes in S2
16:        SF-Split(S1)
17:        SF-Split(S2)
18:      end
19:  end

SFを完全に理解している場合（または以前に同様のアルゴリズムを実装したことがある場合）にのみ、より厳密な算術符号化方法を使用することをお勧めします。私は最近、情報理論のクラスにSFを実装しましたが、頭に浮かぶまでは、その一部が直感的でなく奇妙に見えました。紙の上では単純に見えますが、（他の多くのアルゴリズムと同様に）だまされる可能性があります。

あなたが余分な「スタイルポイント」を獲得しない限り、私は個人的にシャノンファノに行きます。

于 2013-03-15T00:23:59.717 に答える
1

メモリの制約は、ある種の適応コーディングを使用することを示唆しています。算術コーディングはいいですね。しかし、パフォーマンスについては何も指定していません。アルゴリズムは、特定のクラスのファイルでパフォーマンス目標を達成する必要がありますか? ファイルをコピーするだけのアルゴリズムは、上記の要件を満たしています (ただし、多くのことはわかりません)。

言語の選択については、より使いやすいものを使用してください。実行するビット操作が多いため、C または Java の両方が適しています。ファイルをビット ストリームに変換したり、再びビット ストリームに戻したりするコードを記述し、それを別のモジュールにする必要があります。CまたはJavaでそれを行うことがわかりました。

于 2013-03-15T00:52:10.107 に答える