BlockSorting
BlockSortingは、今までのデータ圧縮で有名な方法であるLZ法とは全く違う、ユニークな操作を用 いてデータを圧縮する方法であり、M.BurrowsさんとD.J.Wheelerさんが作者なので「BWTransform」 ともいいます。 このアルゴリズムは簡単に言ってしまえば、「データをぐるぐる回してソートして出力」というも のです。簡単すぎるかもしまいませんが、本当にそうなんです。 ちなみに、このBlockSorting、単体では全く圧縮しません。ただ可逆な形にデータを変換すると いうものです。しかし、BlockSorting後のデータは非常に圧縮されやすい状態になります。例える と、色々な形をしたスポンジ（データ）が箱にごちゃごちゃに入って山積みになっているとします 。 これをそのまま上からギューっと押しつぶすのがLZ法やHuffman法なのに対し、一度、形が似た も
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
デフレート圧縮(LZ77圧縮)処理の概要 - ウェブで用いられる画像形式。
PNG画像を生成するのに欠かせないデフレート圧縮(LZ77圧縮)について解説します。 デフレート圧縮とは。 デフレート圧縮は、LZ77圧縮アルゴリズムを応用したもので、圧縮技術としてはかなり旧くからあるもので、GZIP(ZLib)やZIPファイル圧縮技術などに用いられております。 デフレート圧縮は枯れた技術であり、特許問題も無い技術として知られており、この為PNG画像の基幹技術としても採用されたのです。 特許問題の無い技術とされるデフレート圧縮にも、実は特許に引掛かるアルゴリズムが存在します。しかしながら、特許問題が生じるアルゴリズムは効率を上げるためのものなので、効率が悪くても特許に触れないアルゴリズムを撰べば問題はありません。 そもそもPNG画像形式はGIF画像の基幹技術に特許問題が絡んだことに対応して策定されたもので、実際仕様書にも特許問題が生じない事の確認に長い時間を費やしたと書か
槻ノ木隆の「BBっとWORDS」 - その95「PNGの現状と今後」
■ PNGって何？ PNGとは「Portable Network Graphics」の略で、GIFにかわる画像フォーマットして開発されました。特徴としては以下のようなものが挙げられます。 ・GIFに相当する8bit（256色）のほか、24bit（1,677万色）や48bit（280兆色）など、さまざまなフォーマットに対応 ・特許問題の生じない圧縮フォーマットを採用しつつ、GIFよりも圧縮率が高い ・透過色に関して、αチャネルをサポートしている関係で半透明の表現なども可能 ・アニメーションのサポートがない（これはPNGをベースとしたMNGフォーマットでサポートされる） ・古いWebブラウザや画像処理ソフトでは対応しない 前回説明した通り、2000年にGIFの特許問題が出てきたことで、GIFの代替フォーマットとして急速に普及を始めたのがPNGフォーマットになります。そういう意味では、GIFなど
画像圧縮アルゴリズム (4)ハフマン符号化 - 動的ハフマン圧縮
上の例では、赤で塗られた同レベルの節を入れ替えて、木の右側ほどレベルが深くなるようにしてから、黄色で塗られた同レベルの葉を入れ替えて、データ番号が昇順に並ぶようにしています。 正規化によって得られたハフマン符号には強い規則性が見られます。最も符号長が短く、且つパレットコードの一番若い葉は、全てのビットが0になり、逆に符号長が最も長く、且つパレットコードが最大の葉は全てのビットが1になります。符号長の等しい葉の符号は、パレットコードの若いものから順に1ずつ増えていき、符号長が1ビット長くなると、符号に1を加えた後で、末尾に0を付加した形になっていることが、上の例からもわかると思います。 この規則性を利用して、次のような手順で符号長からハフマン符号を再現させることができます。 各節の中で、葉の部分のみを符号長でソートする。符号長が等しい場合は、パレットコード順に並べる。 ソート後の葉の配列から
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
第三部 第二章
アルゴリズムとデータ構造演習
