符号化の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/31 04:39 UTC 版)
「シャノン・ファノ符号化」の記事における「符号化の原理」の解説
記号を出現確率の高い物から低い物の順に並べ替える。 それぞれの集合の確率の合計ができるだけ等しくなるようなところで二分割する。 分割した片方の集合に"0"、もう片方の集合に"1"を割り当て、符号の1桁目とする。 分割して出来た2つの集合をそれぞれ更に二分割し、同様に0と1を割り当てる。 この操作を、各集合に含まれる記号が1つになるまで行うと、それぞれの記号の符号が得られる。 このアルゴリズムは、かなり効率の良い可変長の符号を生成する。分割によって作られた2つの集号は、実際にほぼ等しい出現確率がある。それらを識別するのに用いられる1ビットの情報は、最も効率的に使われる。残念なことに、シャノン・ファノ符号化は常に最短の符号を表すとは限らない。{0.35, 0.17, 0.17, 0.16, 0.15}という出現確率の集合からは、シャノン・ファノ符号化では最適化されていない符号が生成される。 この理由から、シャノン・ファノ符号化が用いられることは少ない。多くの場合はハフマン符号、あるいは算術符号やRange Coderが用いられる。
※この「符号化の原理」の解説は、「シャノン・ファノ符号化」の解説の一部です。
「符号化の原理」を含む「シャノン・ファノ符号化」の記事については、「シャノン・ファノ符号化」の概要を参照ください。
符号化の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/09 01:48 UTC 版)
例として DAEBCBACBBBC という12文字からなるメッセージを考える。 このメッセージ中には5種類の文字が使われているので、もしそれぞれの文字を固定長のビット列で表すとすれば、1文字につき最低3ビット必要となる。 文字とビット列の対応表として、 A B C D E 000 001 010 011 100 を使い、それぞれの文字をビット列に置き換えたとすると、メッセージ全体は次のビット列で表される。 D A E B C B A C B B B C 011 000 100 001 010 001 000 010 001 001 001 010 12文字 x 3ビットで全体のビット数は36ビットとなる。 もし、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることができれば、メッセージ全体の符号化に必要なビット数を抑えることが期待できる。そこで、文字とビット列の対応表として、 A B C D E 110 0 10 1110 1111 を使ったとすると、メッセージ全体は D A E B C B A C B B B C 1110 110 1111 0 10 0 110 10 0 0 0 10 となり、全体のビット数は25ビットとなる。固定長の方式に比べると 70% ほどのデータ量に抑えられている。
※この「符号化の原理」の解説は、「ハフマン符号」の解説の一部です。
「符号化の原理」を含む「ハフマン符号」の記事については、「ハフマン符号」の概要を参照ください。
符号化の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/03 22:32 UTC 版)
データを先頭から順番に符号化していく方式である。現在注目している位置から始まる記号列が、それ以前に出現していたかを探す。もし出現していたならば、記号列をその出現位置と長さのポインタに置き換える。記号列を探す範囲をスライド窓と呼び、これを辞書として使用するので、辞書式圧縮法（英語版）と呼ばれる。 もともとのLZ77では、記号列を（一致位置、一致長、次の不一致記号）という3つの値に置き換えるが、さまざまな亜種が存在する。中でもLZSSは、単純で性能もよく、いろいろな応用に使用されている。
※この「符号化の原理」の解説は、「LZ77」の解説の一部です。
「符号化の原理」を含む「LZ77」の記事については、「LZ77」の概要を参照ください。
符号化の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2010/05/24 16:16 UTC 版)
出現頻度が高い2バイトを使われていない1バイトに置き換えていくことを繰り返して圧縮する。 ABCDCDABCDCDE 出現頻度の高い CD のペアを使われていない Z に、次に頻度の高い AB のペアを Y に置き換える YZZYZZE 出現頻度の高い YZ（ZZ でも構わない）のペアを使われていない X に置き換える XZXZE 出現頻度の高い XZ のペアを使われていない W に置き換える WWE WWのペアはひとつしか出てこないのでここで終わり 実際には、これに符号の対応表を付加してからファイルに出力する。 表・話・編・歴 データ圧縮方法 可逆 理論 情報量 · 複雑性 · 冗長性 · 非可逆 エントロピー符号 シャノン符号 · シャノン・ファノ・イライアス · ハフマン · 適応型ハフマン · 算術 · Range · ゴロム · ユニバーサル符号 (ガンマ · 指数ゴロム · フィボナッチ · レーベンシュタイン) 辞書式 RLE · BPE · Deflate · Lempel–Ziv (LZ77 · LZ78 · LZSS · LZW · LZWL · LZO · LZMA · LZX · LZRW · LZJB · LZT · ROLZ) その他 CTW · BWT · PPM · DMC · Delta 音声 理論 コンパンディング · 畳み込み · ダイナミックレンジ · レイテンシ · 標本化 · 標本化定理 · 音声品質 音声コーデック LPC (LAR · LSP) · WLPC · CELP · ACELP · A-law · μ-law · ADPCM · DPCM · MDCT · フーリエ変換 · 音響心理学 その他 ビットレート (CBR · ABR · VBR) · 音声符号化 · サブバンド符号化 画像 用語 色空間 · ピクセル · クロマサブサンプリング · ブロックノイズ · 解像度 手法 RLE · フラクタル · ウェーブレット · EZW · SPIHT · LP · DCT · チェインコード · KLT その他 テストイメージ · PSNRクオリティ測定 · 量子化 映像 用語 フレーム · フレームレート · インターレース · フレームの種類 · 映像品質 · 解像度 映像コーデック フレーム間予測 · DCT · 量子化 その他 映像コーデック · レート歪理論 · ビットレート (CBR · ABR · VBR) 情報理論とデータ圧縮と誤り検出訂正の年表 圧縮フォーマットと圧縮ソフトウェアも参照
※この「符号化の原理」の解説は、「BPE」の解説の一部です。
「符号化の原理」を含む「BPE」の記事については、「BPE」の概要を参照ください。
符号化の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/22 16:48 UTC 版)
対象となる整数Xの数-1の0を出力し、1を出力するだけである。 アルファ符号の出力(10まで)対象となる数出力1 1 2 01 3 001 4 0001 5 00001 6 000001 7 0000001 8 00000001 9 000000001 10 0000000001
※この「符号化の原理」の解説は、「アルファ符号」の解説の一部です。
「符号化の原理」を含む「アルファ符号」の記事については、「アルファ符号」の概要を参照ください。
符号化の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/13 20:51 UTC 版)
連長圧縮では、ある連続したデータを、そのデータ一つ分と連続した長さで表現することで圧縮している。 例えば、「A A A A A B B B B B B B B B A A A」は「A 5 B 9 A 3」と表せる。これは、Aが5回続き、そのあとにBが9回、そしてAが3回続いていることを表している（連続回数を、元のデータを表す符号の前に記録することもある。その場合、符号化した後は「5 A 9 B 3 A」と表される）。 さらに、データがこの2種類（AとB）だけで、最初にAが来ることにしておけば、「5 9 3」だけで表せる。このルールに従ったときにBが最初に見つかった場合は、最初にAが0回連続していることにすれば良い。例えば、「B B B A A A A A B B B B B A A A」は「0 3 5 5 3」で表せることになる。 こういったことから、白と黒以外にほとんど情報がないモノクロファクシミリでよく使われている。 「ファクシミリ#データの圧縮」を参照
※この「符号化の原理」の解説は、「連長圧縮」の解説の一部です。
「符号化の原理」を含む「連長圧縮」の記事については、「連長圧縮」の概要を参照ください。
符号化の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/07/05 02:35 UTC 版)
「Move To Front」の記事における「符号化の原理」の解説
まず初期化として、符号化の対象とするデータ列をリスト状に並べる。対象：a b a b a c a c a 次に、符号化対象とするデータ列から記号を1つ読み込む。この読み込んだ記号が以前に出現していなければそのまま出力する。同時に、出現した記号をテーブルに登録する。出力：a テーブル：a 一度出力したことのある記号まで1と2を繰り返す。出現した記号は常にテーブルの先頭に登録する。出力：a b テーブル：b a aは一度出力したことがあるので、以前のaがテーブルの何番目に位置するかを、整数で出力する。そして、この記号をテーブルの先頭位置に移動する。出力：a b 2 テーブル：a b データ列のすべての記号を符号化するまでこの操作を繰り返す。出力：a b 2 2 テーブル：b a 出力：a b 2 2 2 テーブル：a b 出力：a b 2 2 2 c テーブル：c a b 出力：a b 2 2 2 c 2 テーブル：a c b 出力：a b 2 2 2 c 2 2 テーブル：c a b 出力：a b 2 2 2 c 2 2 2 テーブル：a c b このように、MTFを施すとデータが偏るようになる。これを圧縮すると高い圧縮率が期待できる。
※この「符号化の原理」の解説は、「Move To Front」の解説の一部です。
「符号化の原理」を含む「Move To Front」の記事については、「Move To Front」の概要を参照ください。
符号化の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/07/26 08:55 UTC 版)
対象となる正の整数の2進数表現をXとする。まず、Xの桁数をガンマ符号で出力する。次に、最上位ビットを除いたXを出力する。その結果がデルタ符号である。 デルタ符号の出力(1〜10、31〜35)対象となる数2進数表現桁数のガンマ符号出力ガンマ符号の出力(比較)1 1 1 1 1 2 10 010 0100 010 3 11 010 0101 011 4 100 011 01100 00100 5 101 011 01101 00101 6 110 011 01110 00110 7 111 011 01111 00111 8 1000 00100 00100000 0001000 9 1001 00100 00100001 0001001 10 1010 00100 00100010 0001010 ⋮ 31 11111 00101 001011111 000011111 32 100000 00110 0011000000 00000100000 33 100001 00110 0011000001 00000100001 34 100010 00110 0011000010 00000100010 35 100011 00110 0011000011 00000100011 大きな整数を効率よく符号化できるようになっているが、小さな値ではガンマ符号のほうが良い性能をみせる。
※この「符号化の原理」の解説は、「デルタ符号」の解説の一部です。
「符号化の原理」を含む「デルタ符号」の記事については、「デルタ符号」の概要を参照ください。
符号化の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/07/30 06:41 UTC 版)
出現頻度が高い2バイトを使われていない1バイトに置き換えていくことを繰り返して圧縮する。 ABCDCDABCDCDE 出現頻度の高い CD のペアを使われていない Z に、次に頻度の高い AB のペアを Y に置き換える YZZYZZE 出現頻度の高い YZ（ZZ でも構わない）のペアを使われていない X に置き換える XZXZE 出現頻度の高い XZ のペアを使われていない W に置き換える WWE WW のペアはひとつしか出てこないのでここで終わり 実際には、これに符号の対応表を付加してからファイルに出力する。 表 話 編 歴 データ圧縮方式可逆 エントロピー符号 一進法 算術 ゴロム ハフマン適応型（英語版） 正準（英語版） MH Range シャノン シャノン・ファノ シャノン・ファノ・イライアス（英語版） タンストール（英語版） ユニバーサル（英語版）指数ゴロム（英語版） フィボナッチ（英語版） ガンマ レーベンシュタイン（英語版） 辞書式（英語版） BPE Deflate Lempel-ZivLZ77 LZ78 LZH LZJB（英語版） LZMA LZO LZRW（英語版） LZS（英語版） LZSS LZW LZWL（英語版） LZX LZ4 ROLZ（英語版） 統計型（英語版） その他 BWT CTW（英語版） Delta DMC（英語版） MTF PAQ PPM RLE 音声 理論 ビットレート（英語版）平均(ABR) 固定(CBR) 可変(VBR) コンパンディング 畳み込み ダイナミックレンジ レイテンシ（英語版） 標本化定理 標本化 音質 音声符号化 サブバンド符号化 変換符号化 知覚符号化 コーデック（英語版） A-law μ-law ACELP ADPCM CELP DPCM フーリエ変換 LPCLAR LSP MDCT 音響心理学 WLPC 画像 理論 クロマサブサンプリング（英語版） 符号化ツリーユニット（英語版） 色空間 ブロックノイズ 解像度 マクロブロック（英語版） ピクセル PSNR 量子化（英語版） 標準テストイメージ（英語版） 手法 チェインコード（英語版） DCT EZW（英語版） フラクタル KLT（英語版） ピラミッド（英語版） RLE SPIHT（英語版） ウェーブレット 映像 理論 ビットレート（英語版）平均(ABR) 固定(CBR) 可変(VBR) 画面解像度 フレーム フレームレート インターレース 映像品質（英語版） コーデック（英語版） 重複変換（英語版） DCT デブロッキングフィルタ（英語版） フレーム間予測 理論 情報量 複雑性 非可逆 量子化 レート歪み（英語版） 冗長性 情報理論の年表（英語版） 圧縮フォーマット 圧縮ソフトウェア
※この「符号化の原理」の解説は、「バイト対符号化」の解説の一部です。
「符号化の原理」を含む「バイト対符号化」の記事については、「バイト対符号化」の概要を参照ください。
符号化の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/12/18 04:37 UTC 版)
対象となる正の整数の2進数表現をXとする。まず、Xの桁数より1つ少ない数だけ「0」を出力する。次に、Xをそのまま出力する。その結果がガンマ符号である。 ガンマ符号の出力(10まで)対象となる数2進数表現出力1 1 1 2 10 010 3 11 011 4 100 00100 5 101 00101 6 110 00110 7 111 00111 8 1000 0001000 9 1001 0001001 10 1010 0001010 Xが大きな値(6ビット以上)であれば、デルタ符号のほうが短い符号語を出力することができる。
※この「符号化の原理」の解説は、「ガンマ符号」の解説の一部です。
「符号化の原理」を含む「ガンマ符号」の記事については、「ガンマ符号」の概要を参照ください。
符号化の原理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/07/29 02:32 UTC 版)
「Lempel–Ziv–Storer–Szymanski」の記事における「符号化の原理」の解説
LZ77では、記号列を（一致位置、一致長、次の不一致記号）という3つの値に置き換えていた。しかし、この方法では一致がなかった場合には（0,0,不一致記号）と一致位置、一致長のぶんだけ冗長になってしまう。 そこでLZSSでは、 一致があった場合：1、一致位置、一致長 一致がなかった場合：0、不一致記号 とすることで圧縮率の向上を図っている。つまり、まず最初に一致したかどうかに1ビット使う。一致位置は、圧縮しようとしている位置より前の位置で、最も長く一致する部分を探索する。一致位置、一致長、不一致記号は固定ビット数で表現する。 LZSSはLZ77とさほど変わらないアルゴリズムであるにもかかわらず、大幅な性能向上が期待でき、多くの圧縮ソフトウェアで用いられている。
※この「符号化の原理」の解説は、「Lempel–Ziv–Storer–Szymanski」の解説の一部です。
「符号化の原理」を含む「Lempel–Ziv–Storer–Szymanski」の記事については、「Lempel–Ziv–Storer–Szymanski」の概要を参照ください。
- 符号化の原理のページへのリンク
