問題タブ [information-theory]

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

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

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

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

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

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

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

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

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

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

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

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

私はカバー、トーマス「情報理論の要素」に取り組んでおり、バイナリ対称チャネルの簡単な例を試して実装したいと考えています。つまり、メッセージ「1001」、エンコーディング「11000011」(基本的に各ビットを 2 回繰り返す)、チャネル法則 p(y|x) を指定でき、受信機で事後情報を確認したいアップデート。

正直なところ、どこから始めればよいかさえわかりません。また、オンラインで多くのヘルプを見つけることができないようです。私が見つけたもののほとんどは、Matlab の simulink を使用してプロセスを抽象化することです。私は実際に分布をベクトルなどとして指定したいと思っています。どんなポインタでも素晴らしいでしょう!

編集: この質問が DSP.SE の方が適しているかどうかはわかりませんが、そうであれば移動できます。

仮定の状況:

ホスト A は、1 秒あたり 1 ビットの速度でホスト B に情報を送信できます。

ホスト B は、毎秒 1 テラバイトの速度でホスト A に情報を送信できます。

A から B に 1 ギガバイトのランダムな情報を送信したいとします。

どのようにしますか？

B -> A を利用して A -> B を高速化する方法はありますか?

学校で得た課題の助けが必要です... 月の日数、月の名前、および番号の情報を記憶する列挙型または複数を作成しようとしています今月の。

また、私の教えは、すべての情報が私のコードにある必要があると言いました...データベースやそのようなものはありません。-_-

経験値:

別の経験:

注: 人間工学に基づいた X_X ではないため、配列を使用したくありませんが、それが最善の解決策であると思われる場合は、それを使用します。

3 つの変数をリンクする最も倹約的な (何が倹約的かという問題は、この場合は少し恣意的に思えるかもしれません!) 式を探すアルゴリズムを構築することは可能ですか?

たとえば、次のようになります。

これら3つの変数間の最も節約的なリンクは次のとおりです（これが最も節約的であることを願っています）：

なぜなら：

私の質問は次のとおりです。

• そのようなアルゴリズムを構築することは可能ですか?
• この種の既存のアルゴリズムを知っていますか?
  • はいの場合、私の例のように比較的簡単な関係で (迅速に) うまくいきますか?

アップデート：

これは、3 つの変数を作成する R コードでa.lありb.l、c.l例を作成するためのものです。

mxn行列の場合、列のすべてのペア ( nxn )の相互情報を計算する最適な (最速の) 方法は何ですか?

相互情報とは、次のことを意味します。

I(X, Y) = H(X) + H(Y) - H(X,Y)

ここで、H(X)はXのシャノン エントロピーを表します。

現在、私は and を使用np.histogram2dしnp.histogramて、関節(X、Y)と個々の(X または Y)の数を計算しています。特定の行列A(たとえば、250000 X 1000 の float 行列) に対して、ネストされたforループを実行しています。

確かにこれを行うためのより良い/より速い方法があるに違いありませんか?

余談ですが、配列の列に対するマッピング関数 (列方向または行方向の操作) も探しましたが、まだ適切な一般的な答えは見つかりませんでした。

Wikiページの規則に従って、私の完全な実装を次に示します。

ネストされたループを使用した私の作業バージョンは妥当な速度で実行されますが、 (ペアごとの相互情報を計算するために) のすべての列にfor適用するより最適な方法があるかどうかを知りたいですか?calc_MIA

私も知りたいです：

1. 関数をマップして列 (または行) を操作する効率的な方法があるかどうか (np.arraysデコレータnp.vectorizeのように見える のように)?

2. この特定の計算に最適な実装が他にあるかどうか (相互情報)?

決定木は、エントロピーの高い分類器を決定木の上位に配置しようとすることを理解しています。しかし、情報利得はこれにどのように影響するのでしょうか?

情報取得は次のように定義されます。

ディシジョン ツリーは、情報ゲインの低い分類子をツリーの一番上に配置しようとしますか? エントロピーは常に最大化され、情報利得は常に最小化されるのでしょうか?

申し訳ありませんが、私は少し混乱しています。ありがとうございました！

はっきりさせておきますが、これは、任意のソース マテリアルを圧縮できるアルゴリズムという意味での完全な圧縮について話しているのではありません。それは不可能だと認識しています。私が取得しようとしているのは、シャノンエントロピーによって決定されるように、ビットのソース文字列を絶対最大圧縮状態にエンコードできるアルゴリズムです。

ハフマン符号化はある意味で最適であると聞いたことがあると思うので、この暗号化スキームはそれに基づいている可能性があると思いますが、ここに私の問題があります:

ビット文字列を考えてみましょう: a = "101010101010", b = "110100011010".

単純なシャノン エントロピーを使用すると、ビット文字列を 0 と 1 の単純な記号と見なした場合、これらのビット文字列はまったく同じエントロピーを持つはずですが、このアプローチには欠陥があります。単純に 10 の繰り返しのパターンです。これを念頭に置いて、複合シンボル 00、10、01、および 11 のシャノン エントロピーを計算することで、ソースの実際のエントロピーをより正確に把握できます。

これは単なる私の理解であり、私は完全にベースから外れている可能性がありますが、私が理解していることから、エルゴード ソースが真にランダムであるためには、長さ n のエルゴード ソースに対してです。長さ n のシンボル グループすべての統計的確率は、同じ確率である必要があります。

タイトルの質問よりも具体的だと思いますが、主な質問が 3 つあります。

シンボルとして単一ビットを使用するハフマン エンコーディングは、2 ビット シンボルのレベルで文字列を分析したときに発生する明らかなパターンがあっても、最適にビット文字列を圧縮しますか? そうでない場合、最適な圧縮率が見つかるまで、ハフマン コーディングのさまざまな「レベル」(ここで用語を乱用している場合は申し訳ありません) を循環させることで、ソースを最適に圧縮できますか? ハフマンコーディングのさまざまな「ラウンド」を経ることで、場合によっては圧縮率がさらに向上する可能性がありますか? (最初に 5 ビット長のシンボルでハフマン コーディングを行い、次に 4 ビット長のシンボルでハフマン コーディングを行いますか? huff_4bits(huff_5bits(bitstring)))

いくつかの属性で構成されるクエリがあります。そのクエリの情報量を測定したいと思います。次に、特定の属性を削除した場合に、その情報コンテンツがどの程度減少するか、または影響を受けないかを測定します。

この問題を解決する情報理論からの尺度または測定基準はありますか? ありがとう