algorithm - 冗長性の高い値を持つ行列を効率的に格納する方法

Question

非常に大きな行列 (1 億行 x 1 億列) があり、多数の重複値が隣り合っています。例えば：

8 8 8 8 8 8 8 8 8 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 3 3 3 3 3 3 3 3 3 3 3

このような行列をできるだけコンパクトに格納するためのデータ構造/アルゴリズムが必要です。たとえば、上記の行列は、(行列が任意に大きく引き伸ばされたとしても) O(1) スペースしかとらないはずです。これは、各領域が 1 つの値しか持たない一定数の長方形領域しかないためです。

繰り返しは行と下の列の両方で発生するため、行列を行ごとに圧縮する単純な方法では十分ではありません。(これには、行列を格納するために最低でも O(num_rows) のスペースが必要です。)

行列の表現も行ごとにアクセスできる必要があるため、列ベクトルに対して行列の乗算を行うことができます。

Answer 1

単一の値を含む葉を持つ四分木として行列を保存できます。これは、値の 2 次元の「実行」と考えてください。

Answer 2

さて、私の好みの方法です。

わかりました、前の回答で述べたように、行列 A の各列に同じエントリを持つ行は、行列 AB で同じ結果に乗算されます。その関係を維持できれば、理論的には計算を大幅に高速化できます (プロファイラーはあなたの味方です)。

このメソッドでは、行列の行 * 列構造を維持します。

各行は、乗算速度にあまり影響を与えないように十分に速く解凍できる方法で圧縮されます。RLEで十分かもしれません。

これで、圧縮された行のリストができました。

エントロピー エンコーディング メソッド (Shannon-Fano、Huffman、または算術コーディングなど) を使用しますが、これを使用して行のデータを圧縮するのではなく、行のセットを圧縮するために使用します。これを使用して、行の相対頻度をエンコードします。つまり、標準のエントロピー エンコーディングが文字/バイトを処理するのと同じ方法で行を処理します。

この例では、RLEは行を圧縮し、Huffman は行セット全体を圧縮します。

したがって、たとえば、次の行列が与えられた場合 (行番号が前に付けられ、説明を簡単にするためにハフマンが使用されます)

0 | 8 8 8 8 8 8 8 8 8 8 8 8 8 |
1 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
2 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
3 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
4 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
5 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
6 | 8 8 8 8 8 8 8 8 8 8 8 8 8 |
7 | 8 8 3 3 3 3 3 3 3 3 3 3 3 |

エンコードされたランレングス

0 | 8{13}                    |
1 | 8{1} 4{1} 8{2} 1{5} 8{4} |
2 | 8{1} 4{1} 8{2} 1{5} 8{4} |
3 | 8{1} 4{1} 8{2} 1{5} 8{4} |
4 | 8{1} 4{1} 8{2} 1{5} 8{4} |
5 | 8{1} 4{1} 8{2} 1{5} 8{4} |
6 | 8{13}                    |
7 | 8{2} 3{11}               |

つまり、0 と 6 は 2 回、1 ～ 5 は 5 回出現します。7 一度だけ。

頻度表

A: 5 (1-5) | 8{1} 4{1} 8{2} 1{5} 8{4} |
B: 2 (0,6) | 8{13}                    |
C: 1    7  | 8{2} 3{11}               |

ハフマン木

    0|1
   /   \
  A    0|1
      /   \
     B     C

したがって、この場合、行 1 ～ 5 をエンコードするのに (行ごとに) 1 ビット、行 0、6、および 7 をエンコードするのに 2 ビットかかります。

(実行が数バイトよりも長い場合は、RLE を実行するときに構築したハッシュで freq count を実行します)。

ハフマン ツリー、一意の文字列、および行エンコード ビット ストリームを格納します。

Huffman の優れた点は、一意のプレフィックス プロパティがあることです。そのため、いつ完了したかを常に把握できます。したがって、ビット文字列10000001011を指定すると、格納された一意の文字列とツリーから行列 A を再構築できます。エンコードされたビット ストリームは、行が表示される順序を示します。

適応ハフマンエンコーディング、またはその算術対応物を調べたいと思うかもしれません。

同じ列エントリを持つ A の行が、ベクトル B を介して AB で同じ結果に乗算されるのを見ると、結果をキャッシュして、再度計算する代わりに使用できます (可能であれば、100M*100M の乗算を避けることをお勧めします)。

詳細情報へのリンク:

算術符号化 + 統計モデリング = データ圧縮

プライオリティ キューと STL

算術符号化

ハフマンコーディング

比較

非圧縮

    0   1   2   3   4   5   6   7
  =================================
0 | 3   3   3   3   3   3   3   3 |
  |-------+               +-------|
1 | 4   4 | 3   3   3   3 | 4   4 |
  |       +-----------+---+       |
2 | 4   4 | 5   5   5 | 1 | 4   4 |
  |       |           |   |       |
3 | 4   4 | 5   5   5 | 1 | 4   4 |
  |---+---|           |   |       |
4 | 5 | 0 | 5   5   5 | 1 | 4   4 |
  |   |   +---+-------+---+-------|
5 | 5 | 0   0 | 2   2   2   2   2 |
  |   |       |                   |
6 | 5 | 0   0 | 2   2   2   2   2 |
  |   |       +-------------------|
7 | 5 | 0   0   0   0   0   0   0 |
  =================================

= 64 バイト

四分木

    0   1   2   3   4   5   6   7
  =================================
0 | 3 | 3 |       |       | 3 | 3 |
  |---+---|   3   |   3   |---+---|
1 | 4 | 4 |       |       | 4 | 4 |
  |-------+-------|-------+-------|
2 |       |       | 5 | 1 |       |
  |   4   |   5   |---+---|   4   |
3 |       |       | 5 | 1 |       |
  |---------------+---------------|
4 | 5 | 0 | 5 | 5 | 5 | 1 | 4 | 4 |
  |---+---|---+---|---+---|---+---|
5 | 5 | 0 | 0 | 2 | 2 | 2 | 2 | 2 |
  |-------+-------|-------+-------|
6 | 5 | 0 | 0 | 2 | 2 | 2 | 2 | 2 |
  |---+---+---+---|---+---+---+---|
7 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  =================================

0 +- 0 +- 0 -> 3
  |    +- 1 -> 3
  |    +- 2 -> 4
  |    +- 3 -> 4
  +- 1      -> 3
  +- 2      -> 4
  +- 3      -> 5
1 +- 0      -> 3
  +- 1 +- 0 -> 3
  |    +- 1 -> 3
  |    +- 2 -> 4
  |    +- 3 -> 4
  +- 2 +- 0 -> 5
  |    +- 1 -> 1
  |    +- 2 -> 5
  |    +- 3 -> 1
  +- 3      -> 4
2 +- 0 +- 0 -> 5
  |    +- 1 -> 0
  |    +- 2 -> 5
  |    +- 3 -> 0
  +- 1 +- 0 -> 5
  |    +- 1 -> 5
  |    +- 2 -> 0
  |    +- 3 -> 2
  +- 2 +- 0 -> 5
  |    +- 1 -> 0
  |    +- 2 -> 5
  |    +- 3 -> 0
  +- 3 +- 0 -> 0
       +- 1 -> 2
       +- 2 -> 0
       +- 3 -> 0
3 +- 0 +- 0 -> 5
  |    +- 1 -> 1
  |    +- 2 -> 2
  |    +- 3 -> 2
  +- 1 +- 0 -> 4
  |    +- 1 -> 4
  |    +- 2 -> 2
  |    +- 3 -> 2
  +- 2 +- 0 -> 2
  |    +- 1 -> 2
  |    +- 2 -> 0
  |    +- 3 -> 0
  +- 3 +- 0 -> 2
       +- 1 -> 2
       +- 2 -> 0
       +- 3 -> 0

((1*4) + 3) + ((2*4) + 2) + (4 * 8) = 49 leaf nodes 
49 * (2 + 1) = 147 (2 * 8 bit indexer, 1 byte data)
+ 14 inner nodes -> 2 * 14 bytes (2 * 8 bit indexers)
= 175 Bytes

地域ハッシュ

    0   1   2   3   4   5   6   7
  =================================
0 | 3   3   3   3   3   3   3   3 |
  |-------+---------------+-------|
1 | 4   4 | 3   3   3   3 | 4   4 |
  |       +-----------+---+       |
2 | 4   4 | 5   5   5 | 1 | 4   4 |
  |       |           |   |       |
3 | 4   4 | 5   5   5 | 1 | 4   4 |
  |---+---|           |   |       |
4 | 5 | 0 | 5   5   5 | 1 | 4   4 |
  |   + - +---+-------+---+-------|
5 | 5 | 0   0 | 2   2   2   2   2 |
  |   |       |                   |
6 | 5 | 0   0 | 2   2   2   2   2 |
  |   +-------+-------------------|
7 | 5 | 0   0   0   0   0   0   0 |
  =================================

0: (4,1; 4,1), (5,1; 6,2), (7,1; 7,7)         | 3
1: (2,5; 4,5)                                 | 1
2: (5,3; 6,7)                                 | 1
3: (0,0; 0,7), (1,2; 1,5)                     | 2
4: (1,0; 3,1), (1,6; 4,7)                     | 2
5: (2,2; 4,4), (4,0; 7,0)                     | 2

領域: (3 + 1 + 1 + 2 + 2 + 2) * 5 = 55 バイト {4 バイトの長方形、1 バイトのデータ)

{ルックアップ テーブルは並べ替えられた配列であるため、追加のストレージは必要ありません}。

ハフマン符号化された RLE

0   | 3 {8}                                 | 1
1   | 4 {2} | 3 {4} | 4 {2}                 | 2
2,3 | 4 {2} | 5 {3} | 1 {1} | 4 {2}         | 4
4   | 5 {1} | 0 {1} | 5 {3} | 1 {1} | 4 {2} | 5
5,6 | 5 {1} | 0 {2} | 2 {5}                 | 3
7   | 5 {1} | 0 {7}                         | 2


RLE Data:    (1 + 3+ 4 + 5 + 3 + 2) * 2 = 36
Bit Stream:   20 bits packed into 3 bytes = 3
Huffman Tree: 10 nodes * 3 = 30
= 69 Bytes

1 つの Giant RLE ストリーム

3{8};4{2};3{4};4{4};5{3};1{1};4{4};5{3};1{1};4{2};5{1};0{1};
5{3};1{1};4{2};5{1};0{2};2{5};5{1};0{2};2{5};5{1};0{7}

= 2 * 23 = 46 Bytes

共通のプレフィックス フォールディングでエンコードされた 1 つの Giant RLE ストリーム

3{8};
4{2};3{4};
4{4};5{3};1{1};
4{4};5{3};
1{1};4{2};5{1};0{1};5{3};
1{1};4{2};5{1};0{2};2{5};
5{1};0{2};2{5};
5{1};0{7}

0 + 0 -> 3{8};4{2};3{4};
  + 1 -> 4{4};5{3};1{1};

1 + 0 -> 4{2};5{1} + 0 -> 0{1};5{3};1{1};
  |                + 1 -> 0{2}
  |
  + 1 -> 2{5};5{1} + 0 -> 0{2};
                   + 1 -> 0{7}

3{8};4{2};3{4}           | 00
4{4};5{3};1{1}           | 01
4{4};5{3};1{1}           | 01
4{2};5{1};0{1};5{3};1{1} | 100
4{2};5{1};0{2}           | 101
2{5};5{1};0{2}           | 110
2{5};5{1};0{7}           | 111

Bit stream: 000101100101110111
RLE Data:  16 * 2 = 32
Tree:   : 5 * 2 = 10 
Bit stream: 18 bits in 3 bytes = 3
= 45 bytes

Answer 3

データが本当に規則的である場合は、構造化された形式で保存することでメリットが得られる可能性があります。たとえば、例の行列は、次の「fill-rectangle」命令のリストとして保存される場合があります。

(0,0)-(13,7) = 8
(4,1)-(8,5)  = 1

(次に、特定のセルの値を調べるには、そのセルを含む四角形が見つかるまで、リストを逆方向に繰り返します)

Answer 4

Ira Baxter が提案したように、単一の値を含む葉を持つ四分木として行列を保存できます。

これを行う最も簡単な方法は、四分木のすべてのノードが 2^nx 2^n の領域をカバーし、各非リーフ ノードがサイズ 2^(n-1) x 2^(n-1) の 4 つの子を指すことです。 1)。

不規則な細分割を可能にする適応四分木を使用すると、圧縮率がわずかに向上する場合があります。次に、各非葉ノードはカットポイント (B,G) を格納し、その 4 つの子をポイントします。たとえば、ある非リーフ ノードが左上隅の (A,F) から右下隅の (C,H) までの領域をカバーする場合、その 4 つの子ノードは (A,F) から ( B-1、G-1) (A,G) から (B-1, H) (B,F) から (C,G-1) (B,G) から (C,H)。

データの実際の分割と一致するように、葉以外のノードごとに (B,G) カットポイントを選択しようとします。

たとえば、中央に小さな正方形があり、それ以外が 9 で埋められている行列があるとします。

単純な 2 の累乗四分木では、少なくとも 21 個のノードができます。5 つの非葉ノード、4 つの 9 の葉ノード、および 12 の 0 の葉ノードです。(中央の小さな正方形が左端と上端から正確に 2 のべき乗の距離になく、それ自体が正確な 2 のべき乗でない場合は、さらに多くのノードが得られます)。

適応四分木では、その正方形の左上隅にあるルート ノードのカット ポイントを選択するほどスマートな場合、ルートの右下の子に対しては右下隅にあるカット ポイントを選択します。正方形のうち、行列全体を 9 つのノードで表すことができます。2 つの非葉ノード、9 の 1 つの葉ノード、および 0 の 6 つの葉ノードです。

Answer 5

インターバルツリーについて知っていますか？

間隔ツリーは、間隔を効率的に格納し、クエリを実行する方法です。一般化はRange Treeであり、任意のディメンションに適応できます。

ここでは、長方形を効果的に記述し、それらに値を付けることができます。もちろん、長方形はオーバーラップできます。それが効率的になります。

0,0-n,n --> 8
4,4-7,7 --> 1
8,8-8,n --> 3

次に、ある特定のスポットの値を照会すると、いくつかの長方形のリストが返され、最も内側のものを決定する必要があります。これがこのスポットの値です。

Answer 6

サイズ 100M x 100M のマトリックスの O(1) スペースの説明はわかりにくいです。有限行列がある場合、サイズは定数です (行列を生成するプログラムがそれを変更しない限り)。そのため、スカラーを掛けても、格納に必要なスペースの量も一定です。間違いなく、行列を読み書きする時間は O(1) にはなりません。

疎行列は、そのような行列を格納するために必要なスペースの量を減らすために私が考えることができるものです。このスパース行列をファイルに書き込んで、データをさらに圧縮する tar.gz として保存できます。

100M の M は何を意味するのか質問があります。メガバイト/ミリオンという意味ですか？はいの場合、このマトリックス サイズは 100 x 10^6 x 100 x 10^6 バイト = 10^16 / 10^6 MB = 10^10/10^6 TB = 10^4 TB になります!!! どのような機械をお使いですか？

Answer 7

最も簡単な方法は、1 つの次元でランレングス エンコーディングを使用し、他の次元を気にしないことです。

(データセットがそれほど大きくない場合、それを画像として解釈し、標準の無損失画像圧縮方法を使用することも非常に簡単ですが、疎行列でアルゴリズムを機能させるために作業する必要があるため、それほど単純にはなりません。）

もう 1 つの簡単な方法は、四角形の塗りつぶしを試すことです。右上のピクセルから始めて、可能な限り最大の四角形に増やします (幅優先)。次に、それらすべてのピクセルを「完了」としてマークし、右上の最も残っているピクセルを取得して、完了するまで繰り返します。(おそらく、これらの四角形をある種の BSP または四分木に格納したいと思うでしょう。)

非常に効果的な手法 (最適ではありませんが、おそらく十分です) は、「空間」が空間ではなく変更の数によって測定されるバイナリ空間分割ツリーを使用することです。再帰的にカットして、左と右 (または上と下-おそらく物事を正方形に保ちたい) に同じ数の変更があり、サイズが小さくなるにつれて、できるだけ多くカットするようにします。可能な限り変更します。最終的には、互いに離れた 2 つの長方形を切り取ることになり、それぞれの長方形はすべて同じ数になります。その後停止します。(x と y を RLE でエンコードすると、変化点がどこにあるかがすぐにわかります。)

Answer 8

なぜこの質問が Community Wiki になったのかはわかりませんが、そのとおりです。

線形代数のアプリケーションがあり、行列に長方形の冗長性があるという前提に頼ります。もしそうなら、あなたは四分木よりもはるかに優れた何かを行うことができ、マトリックスを長方形に切り取るよりもきれいになります (これは一般的に正しい考えです)。

M を行列、v を M で乗算するベクトル、A を特別な行列とします。

A = [1 -1  0  0  0]
    [0  1 -1  0  0]
    [0  0  1 -1  0]
    [0  0  0  1 -1]
    [0  0  0  0  1]

A の逆行列も必要です。これを B と呼びます。

B = [1 1 1 1 1]
    [0 1 1 1 1]
    [0 0 1 1 1]
    [0 0 0 1 1]
    [0 0 0 0 1]

ベクトル v を A で乗算するのは速くて簡単です: v の要素の連続したペアの差を取るだけです. ベクトル v を B で乗算するのも速くて簡単です. Bv のエントリは v の要素の部分和です.方程式を使いたい

Mv = B AMA B v

行列 AMA はまばらです。中央では、各エントリは、2 x 2 の正方形を構成する M の 4 つのエントリの交互の合計です。この交互の合計が非ゼロになるには、M のいずれかの四角形の角にいる必要があります。AMA はスパースであるため、ゼロ以外のエントリを連想配列に格納し、スパース行列乗算を使用してベクトルに適用できます。

Answer 9

GIF形式とその圧縮アルゴリズムを確認することをお勧めします。マトリックスをビットマップと考えてください...

Answer 10

最初に試すことは、常に既存のライブラリとソリューションです。最終的に必要なすべての操作でカスタム形式を機能させるのは大変な作業です。スパース行列は古い問題なので、既存のものを必ず読んでください。

適切なものが見つからないと仮定すると、行ベースの形式をお勧めします。超コンパクトな表現に夢中になりすぎないようにしてください。コード内の小さな操作やバグごとに多くの処理が必要になります。代わりに、各行を個別に圧縮してみてください。行列とベクトルの乗算のために各行をスキャンする必要があることを知っています。自分の生活を楽にしてください。

私はランレングスエンコーディングから始めます、それが最初にどのように機能するかを見てください。それが機能したら、前の行のセクションへの参照などのトリックを追加してみてください。したがって、行は次のようにエンコードされる可能性があります：126個のゼロ、8個のゼロ、上の行から直接コピーされた1000個のエントリ、32個のゼロ。あなたの与えられた例ではそれは非常に効率的かもしれないようです。

Answer 11

上記の解決策の多くは問題ありません。

ファイルを扱う場合は、compress、bzip、zip、bzip2 などのファイル指向の圧縮ツールを検討してください。特に、データに冗長な ASCII 文字が含まれている場合は、非常にうまく機能します。外部圧縮ツールを使用すると、コード内の問題や課題が解消され、バイナリ データと ASCII データの両方が圧縮されます。

あなたの例では、1文字の数字を表示しています。0 ～ 9 の数字は、より小さい 4 ビットのエンコード パターンで表すことができます。バイトの追加ビットをカウントとして使用できます。4 ビットは、エクストラにエスケープするための追加のコードを提供します... しかし、2 つの文字が 1 年間使用されていた古い 2000 年問題にまでさかのぼる注意があります。オフセットからのバイト エンコーディングでは 255 年が与えられ、同じ 2 バイトがすべての書かれた履歴にまたがり、さらにいくつかの履歴にまたがることになります。

Answer 12

問題についての私の考えを導く以外の理由がない場合は、私の仮定を確認させてください。

1. 行列は冗長性が高く、必ずしもスパースではありません。
2. ストレージ (ディスクおよび RAM) を最小限に抑えたいと考えています。
3. A[m*n] をベクトル B[n*1] で乗算して、最初に解凍することなく AB[m*1] を取得できるようにしたいと考えています (少なくとも計算に必要な量を超えないようにしてください)。
4. A[i*j] エントリへのランダム アクセスは必要ありません。すべての操作は行列に対して行われます。
5. 乗算は (必要に応じて) オンラインで実行されるため、可能な限り効率的である必要があります。
6. マトリックスは静的です。

四角形や自己類似性などを検出するためにあらゆる種類の巧妙なスキームを試すことができますが、それは乗算を行うときにパフォーマンスを損なうことになります。2 つの比較的単純なソリューションを提案します。

少し後ろ向きに作業する必要がありますので、しばらくお待ちください。

データが主に水平方向の繰り返しに偏っている場合は、次の方法でうまくいく可能性があります。

配列にフラット化されたマトリックスを考えてみてください (これは実際にはメモリに格納される方法です)。例えば

A
| w0 w1 w2 |
| x0 x1 x2 |
| y0 y1 y2 |
| z0 z1 z2 |

になる

A’
| w0 w1 w2 x0 x1 x2 y0 y1 y2 z0 z1 z2 |

任意のインデックスという事実を使用できます[i,j] = i * j.

したがって、乗算を行うとき、k = [0..m*n-1] を使用して「行列」配列 A' を反復し、(k mod n) を使用してベクトル B にインデックスを付け、(k div を使用してベクトル AB にインデックスを付けます) n)。「div」は整数除算です。

たとえば、A[10] = z1. 10 mod 3 = 1と10 div 3 = 3 A[3,1] = z1.

では、圧縮に入ります。通常の Run Length Encoding (RLE) を実行しますが、A ではなく A' に対して実行します。フラット配列を使用すると、繰り返しのシーケンスが長くなるため、圧縮が向上します。次に、実行をエンコードした後、共通の部分文字列を抽出する別のプロセスを実行します。ディクショナリ圧縮の形式を実行するか、実行データを処理して、基数ツリー/サフィックス ツリーなどの空間最適化グラフの形式にするか、トップとテールをマージする独自のデバイスを作成することができます。グラフには、データ内のすべての一意の文字列が表現されている必要があります。ストリームを文字列に分割する方法はいくつでも選択できます: 一致するプレフィックス、長さ、またはその他 (グラフに最適なものは何でも) ですが、バイトではなく実行境界で実行しないと、デコードがより複雑になります。

最も単純な例として、ビット ストリームとパトリシア トライを使用しますが、他のものを使用することもできます (状態ごとのビット数が増えると、マージが改善されます。Stefan Nilssonによる論文を探してください)。

実行データを圧縮するために、グラフに対してハッシュ テーブルを作成します。このテーブルは、文字列をビット シーケンスにマップします。これを行うには、グラフをウォークし、各左ブランチを 0 として、右ブランチを 1 としてエンコードします (任意の選択)。

実行データを処理し、ハッシュ テーブルで一致するまでビット文字列を作成し、ビットを出力して文字列をクリアします (ビットはバイト境界にないため、シーケンスが長くなるまでバッファリングする必要がある場合があります)。書き出すのに十分です）。完全な実行データ ストリームを処理するまで、すすぎと繰り返しを行います。グラフとビット ストリームを保存します。ビット ストリームは、バイトではなく文字列をエンコードします。

プロセスを逆にすると、ビット ストリームを使用してリーフ/ターミナル ノードに到達するまでグラフをたどると、元の実行データが返されます。これをオンザフライでデコードして、ベクトル B に対して乗算する整数のストリームを生成できます。 ABを取得します。ランがなくなるたびに、次のビットを読み取り、対応する文字列を検索します。A へのランダム アクセスが必要ないのは、B でのみ必要なためです (B は範囲/間隔圧縮できますが、そうする必要はありません)。

したがって、RLE は水平ランに偏っていますが、一般的な文字列は 1 回しか保存されないため、垂直方向の圧縮は良好です。

これは長くなりすぎるため、別の回答で別の方法を説明しますが、その方法は、行列Aの繰り返し行がABの同じ結果に乗算されるという事実により、実際に計算を高速化できます。

Answer 13

わかりました。圧縮アルゴリズムが必要です。RLE (Run Length Encoding) を試してみてください。データの冗長性が高い場合に非常にうまく機能します。

Answer 14

あなたが示したマトリックスに対する具体的な答えはありません。有限要素解析 (FEA) では、冗長データを含むマトリックスがあります。学部のプロジェクトで FEA パッケージを実装する際に、スカイライン ストレージ方式を使用しました。

いくつかのリンク:

疎行列ストレージの Intel ページ

ウィキペディアのリンク