問題タブ [run-length-encoding]

ランレングスエンコーディングを実行するプログラムを作成しました。典型的なシナリオでは、テキストが

ランレングスエンコーディングはそれを作ります

ただし、繰り返されない文字ごとに1が追加されていました。私はそれを使ってBMPファイルを圧縮しているので、繰り返し文字の出現を示すためにマーカー「$」を配置するというアイデアを思いつきました（画像ファイルに大量の繰り返しテキストがあると仮定します）。

だからそれは次のようになります

現在の例では、長さは同じですが、BMPファイルには顕著な違いがあります。今、私の問題はデコードにあります。一部のBMPファイルにはパターンがあります。$<char><num>つまり$I9、元のファイルにあるため、圧縮ファイルにも同じテキストが含まれています。$I9ただし、デコードすると、9回繰り返される繰り返しIとして扱われます。したがって、間違った出力が生成されます。私が知りたいのは、元のソースと競合しないように、繰り返し文字（実行）の開始をマークするためにどの記号を使用できるかです。

次の特性を持つバイナリ (16 進データ) の組み込みシステムなど、リソースが制限された環境向けに最適化された FAST 解凍ルーチンが必要です。

1. データは 8 ビット (バイト) 指向です (データ バスは 8 ビット幅)。
2. バイト値の範囲は 0 ～ 0xFF で均一ではありませんが、各 DataSet にはポアソン分布 (ベル カーブ) があります。
3. データセットは高度に固定されており (フラッシュに焼き付けられる)、各セットが 1 - 2MB を超えることはめったにありません

圧縮には必要なだけの時間がかかる場合がありますが、組み込みシステム (3Mhz - 12Mhz コア、2k バイト RAM) のような制限されたリソース環境で実行されるため、メモリ フットプリントが最小の最悪のシナリオでは、1 バイトの解凍に 23uS かかります。 .

適切な減圧ルーチンは何ですか?

基本的なランレングス エンコーディングは無駄が多すぎるようです。圧縮データにヘッダー セットを追加して、未使用のバイト値を使用して繰り返しパターンを表現すると、驚異的なパフォーマンスが得られることがすぐにわかります。

ほんの数分しか投資していない私と一緒に、このようなものを愛する人々からのはるかに優れたアルゴリズムがすでに存在しているに違いありません?

基本的なRLEと比較してパフォーマンスを比較できるように、PCで試してみる「すぐに使える」例をいくつか用意したいと思います。

一次元配列があるとしましょう：

配列と整数を取り、配列のn各要素を n 回複製する組み込みの Matlab 関数はありますか?

たとえば、呼び出しreplicate(a, 3)は を返す必要があり[1,1,1,2,2,2,3,3,3]ます。

これは とまったく同じではないことに注意してくださいrepmat。replicate各要素を実行して結果を連結することで確かに実装できますrepmatが、より効率的な組み込み関数があるかどうか疑問に思っています。

「値」配列と「カウンター」配列を使用して、配列に複数の値を挿入しようとしています。たとえば、次の場合:

いくつかの関数の出力が欲しい

することが

a(1) は b(1) 回繰り返され、a(2) は b(2) 回繰り返されます...

これを行う MATLAB の組み込み関数はありますか? できれば for ループの使用は避けたいと思います。「repmat()」と「kron()」のバリエーションを試しましたが、役に立ちませんでした。

これは基本的にRun-length encodingです。

私はこれについて長い間頭を悩ませてきました

イメージングを行っています。これまでのところ、画像を 2 値化しました。つまり、グレースケール画像から、特定の値を下回るすべてのピクセルが削除されます。これにより、元の画像からいくつかの領域だけが得られ、それらの領域の周りに多くの「ゼロピクセル」があります。

次に、領域を「ブロブ」にエンコードした長さを実行しました。実行は、データの圧縮方法です。たとえば、正方形を 2 値化したと仮定すると、画像全体を表す数回の実行しかありません。ランは、x、y 座標と長さによって定義されます。

画像を再作成するときは、実行ごとに x、y 座標に移動し、実行の長さの x 軸にピクセルを追加します。

次に、ランを取得して、領域の輪郭を表すチェーンを作成する必要があります。私はそれを行う方法がわかりません。

x、y、長さのランがたくさんあり、チェーンを形成するためにエッジを「ナビゲート」する必要があります。通常、イメージングでは、このプロセスは元の画像で行われますが、ここでは元の画像を使用できないため、ランで計算する必要があります。

これが大きなテキストの壁のように見えることはわかっていますが、この質問をより適切に行う方法がわかりません。

同一の実装に関するヒントやポインタは素晴らしいでしょう。

編集

巻き戻しのおかげで、いくつかの画像をリンクします：

_{(出典: tudelft.nl )}

この例では、画像 B を輪郭 C に処理します (チェーンと呼びます)。ただし、D、ランレングスから輪郭を生成したいと思います

従来のRLEアルゴリズムは、数字を使用してデータを圧縮し、数字に続く文字がその位置のテキストに表示される回数を表します。例えば：

AAABBAAABBCECE => 3A2B3A2B1C1E1C1E

ただし、上記の例では、その方法により、圧縮テキストによって使用されるスペースがさらに多くなります。数字を使用して、数字に続く部分文字列が特定のテキストに表示される回数を表すことをお勧めします。例えば：

AAABBAAABBCECE => 2AAABB2CE（ "AAABB"を2回、次に "CE"を2回）。

さて、私の質問は、この方法を使用して、最適なRLEの最小文字数を見つける効率的なアルゴリズムをどのように実装できるかということです。ブルートフォースメソッドは存在しますが、もっと高速なものが必要です（最大でO（長さ²））。おそらく、動的計画法を使用できますか？

私の質問はこれに似ていますが、同じサイズの2番目の配列で指定されたカウントに従って各要素を複製したいと思います。

この例として、配列がある場合、最初の要素を2回複製し、次の要素を3回複製するv = [3 1 9 4]ために使用したい、というように取得します。rep = [2 3 1 5][3 3 1 1 1 9 4 4 4 4 4]

これまでのところ、私は仕事を成し遂げるために単純なループを使用しています。これは私が始めたものです：

スペースを事前に割り当てることで、なんとか改善できました。

しかし、私はまだこれを行うためのより賢い方法が必要だと感じています...ありがとう

たとえば、「aaaaaabbccc」などの長い文字列があります。「a6b2c3」として表す必要があります。これを行う最善の方法は何ですか？文字を比較してカウントをインクリメントし、1 回のパスで 2 つのインデックスを使用して配列内のカウントを置き換えることで、線形時間でこれを行うことができます。これよりも良い方法を考えられますか？ここで機能するエンコード技術はありますか?

「文字列」を検討してください（数字の配列として扱います）

RLE ( "groupby" ) は次のとおりです。

次に、前の要素のランレングスの合計で上記の RLE を強化します。

したがって、上記の強化されたバージョンは次のようになります。

1 で分割された「文字列」:

1 の RLE 分割

8 で分割された「文字列」:

8 で RLE 分割

注 : 私の例では、「Z での RLE 分割」リストを強調せずに引用しました。これはそうではないでしょう。混乱を減らすためにそれらを省略しました。たとえば、「RLE split on 1」は、実際には次のように処理する必要があります。

Z （= 1、8;この場合）でこの「RLE分割」を達成するにはどうすればよいですか

空の配列を省略しても問題ありません ( split の後)。

おそらく賢いリスト構成？( 内にネストされた追加の for ループで解決する方が少し簡単に思えます)