ロゴ
ユニオンペディア
コミュニケーション
Google Play で手に入れよう
新しい! あなたのAndroid™デバイスでユニオンペディアをダウンロードしてください!
ダウンロード
ブラウザよりも高速アクセス!
 

ハフマン符号

索引 ハフマン符号

ハフマン符号(ハフマンふごう、Huffman coding)とは、1952年にデビッド・ハフマンによって開発された符号で、文字列をはじめとするデータの可逆圧縮などに使用される。 ほかのエントロピー符号と同様、よく出現する文字には短いビット列を、あまり出現しない文字には長いビット列を割り当てることで、メッセージ全体の符号化に使われるデータ量を削減することを狙っている。 コンパクト符号やエントロピー符号の一つ。JPEGやZIP (Deflate) などの圧縮フォーマットで使用されている。 シャノン符号化が最適ではない場合が存在する不完全な符号であったのに対し、ハフマン符号は(整数の符号語長という制約のもとでは、)常に最適な符号を構成できる。擬似的に実数の符号語長を割り振る算術符号と比較すれば、データ圧縮効率は劣る。ただし、算術符号やその他の高効率の符号化法と異なり、特許の問題が無い。.

12 関係: 二分木データ圧縮比エントロピー符号コンパクト符号シャノン符号化算術符号DeflateGroovyJPEGZIP接頭符号1952年

二分木

二分木(binary tree; 二進木、バイナリツリー)は、データ構造の1つである。根付き木構造の中で、あるノード(節点 node)が持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。 たとえば、二分探索や二分ヒープを実装するために使われる。 簡単な二分木。大きさ9、深さ3、根は値2を持つ 以後、括弧の中は英語表記。.

新しい!!: ハフマン符号と二分木 · 続きを見る »

データ圧縮比

データ圧縮比(データあっしゅくひ、Data compression ratio)は、データ圧縮でデータの大きさが低減される程度を定量化したものである。データ圧縮比は、物体の物理的圧縮で使われる圧縮比と同様の考え方であり、圧縮されていないときの大きさと圧縮されたときの大きさの比で表される 。 したがって例えば、10MBのファイルを2MBに圧縮した場合、圧縮比は 10/2.

新しい!!: ハフマン符号とデータ圧縮比 · 続きを見る »

エントロピー符号

ントロピー符号(エントロピーふごう)とは、情報源アルファベットのシンボルに対し符号語を割り当てるコンパクト符号の概念の一つで、シンボル毎の出現確率に基づき異なる長さの符号語長を用いることで、情報源を効率的に符号化することを目的としたもの。具体的な例としてハフマン符号や算術符号などがあり、データ圧縮に広く用いられている。 符号アルファベットの要素数をn、任意のシンボルsの出現確率をp_sとすると、-\log_p_sの長さの符号語を割り当てた時に最短の符号が得られることが知られている。当然、任意の情報源に対してこれらの最適な符号語長は整数にはならない。ハフマン符号では、ハフマン木を用いて各符号語長が整数になるように近似しているため、簡便な手法ではあるが最短の符号は得られない。算術符号は半開区間の分割を繰り返すことで、この問題を克服している。 エントロピー符号を復号するには、情報源アルファベットの各出現確率を事前に通知する必要がある。これに対し、復号が完了したデータから順次出現確率を計算する手法も存在し、適応(Adaptive)あるいは動的(Dynamic)と呼ばれる。これと区別する為に静的(Static)という呼称もある。.

新しい!!: ハフマン符号とエントロピー符号 · 続きを見る »

コンパクト符号

ンパクト符号(コンパクトふごう)とは、一意に復号可能な符号のうち、同じ符号アルファベットを用いる他の任意の符号よりも、平均符号長が大きくない符号のこと。ハフマン符号が知られている。.

新しい!!: ハフマン符号とコンパクト符号 · 続きを見る »

シャノン符号化

ャノン符号化(シャノンふごうか、Shannon coding)は、クロード・シャノンによって考案された、可逆圧縮の方法である。.

新しい!!: ハフマン符号とシャノン符号化 · 続きを見る »

算術符号

算術符号(さんじゅつふごう、)とは、1960年頃にマサチューセッツ工科大学のP.

新しい!!: ハフマン符号と算術符号 · 続きを見る »

Deflate

Deflate(デフレート)とはLZ77とハフマン符号化を組み合わせた可逆データ圧縮アルゴリズム。フィル・カッツが開発した圧縮ツールPKZIPのバージョン2で使われていた。ZIPやgzipなどで使われている。1996年5月に RFC 1951 としてドキュメント化された。ヘッダーやフッターをつけた zlib (RFC 1950) 形式や gzip (RFC 1952) 形式とともに使われる事が多い。.

新しい!!: ハフマン符号とDeflate · 続きを見る »

Groovy

Groovy(グルービー)は、Javaプラットフォーム上で動作する動的プログラミング言語である。 Groovy の処理系はオープンソースソフトウェアであり、James Strachan と Bob McWhirter らを中心に、オープンソース開発サイトであるコードハウス上で、2003年8月27日に開発が開始された(CVSへの最初のコミットがなされた)。その後、開発の主体は Guillaume Laforge と Jeremy Rayner らに移り開発が続けられている。2015年3月31日までは Pivotal がスポンサー企業となり、開発者をフルタイム雇用していたが、3月末を持って終了し、Apacheソフトウェア財団の管理に移行する。.

新しい!!: ハフマン符号とGroovy · 続きを見る »

JPEG

JPEG(ジェイペグ、Joint Photographic Experts Group)は、コンピュータなどで扱われる静止画像のデジタルデータを圧縮する方式のひとつ。またはそれをつくった組織 (ISO/IEC JTC 1/SC 29/WG 1, Joint Photographic Experts Group) の略称であり、アクロニムである。JPEG方式による画像ファイルにつけられる拡張子はjpgが多く使われるほか、jpeg等が使われる場合もある。 一般的に非可逆圧縮の画像フォーマットとして知られている。可逆圧縮形式もサポートしているが、可逆圧縮は特許などの関係でほとんど利用されていない。1992年9月18日に最初のリリースが行われた比較的古いフォーマットであり、欠点を克服すべく数々の後継規格が提案されてきたが、企業間の思惑なども絡み、いずれも主流になるには至らず、JPEGが現在も静止画像規格の主流である。 標準では、特定の種類の画像の正式なフォーマットがなく、JFIF形式(マジックナンバー上は、6バイト目から始まる形式部分にJFIFと記されているもの)が事実上の標準ファイルフォーマットとなっている。動画を記録可能にしたものにMotion JPEGがある。立体視 (3D) 用には、ステレオJPEG (JPS) フォーマットがある。 デジタルカメラの記録方式としてもよく利用されているが、デジタルカメラでは様々なオプション機能を使い、JFIFを拡張したExchangeable image file format (EXIF) などのフォーマットとしてまとめられている。.

新しい!!: ハフマン符号とJPEG · 続きを見る »

ZIP

ZIP, Zip, zip.

新しい!!: ハフマン符号とZIP · 続きを見る »

接頭符号

接頭符号(Prefix code)は、語頭属性(prefix property)を満たす符号の事で、通常可変長符号である。主にデータ圧縮に使われる。接頭符号の例として可変長ハフマン符号がある。 日本語では他に語頭符号、英語では prefix-free code、prefix condition code、comma-free code、instantaneous code(日本語では瞬時復号可能符号)などとも呼ばれる。ハフマン符号は接頭符号を生成する数あるアルゴリズムの1つに過ぎないが、ハフマンのアルゴリズムを使わずに生成した接頭符号も「ハフマン符号」と呼ぶことがある。 接頭符号はエントロピー符号の一種で、従って可逆圧縮である。 またクラフトの不等式は、接頭符号として可能な符号語の長さの特性を示している。.

新しい!!: ハフマン符号と接頭符号 · 続きを見る »

1952年

この項目では、国際的な視点に基づいた1952年について記載する。.

新しい!!: ハフマン符号と1952年 · 続きを見る »

出ていきます入ってきます
ヘイ!私たちは今、Facebook上です! »