- ＠IT
- アジャイル/DevOps
- Coding Edge
- データ量を操る圧縮／展開を究めよう：コーディング...
データ量を操る圧縮／展開を究めよう：コーディングに役立つ！ アルゴリズムの基本（8）（1/5 ページ）
プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部）
そういえば圧縮／展開って何をやっているの？
読者の皆さまの中には、普段何げなくファイルを圧縮したり、圧縮されたファイルを展開したりしている方が多いと思います。
ところで、これはどういう仕組みになっているかご存じでしょうか。
今回はデータの圧縮の基本的な考え方を学び、実装を通してプログラミングのスキルを付けていきましょう。
ランレングス法
まずは最も簡単な手法であるランレングス法について解説します。
文字列のデータを圧縮することを考えます。同じ文字が多数連続している場合は、「文字」と「連続している文字数」のデータに変換することで圧縮できます。
例えば、
aaaaabbbbbbccc
というデータの場合は、
a5b6c3
というふうに変換します。
文字数で比較してみると、圧縮前は14文字でしたが圧縮後は6文字と半分以下になっています。圧縮後のデータから元のデータに戻すことも容易にできます。
ランレングス法の実装
それでは早速、ランレングス法を実装してみましょう。サンプルデータは某巨大掲示板から引用しました。
- <html>
- <head>
- <script type="text/javascript">
- function getStringById(id) {
- var element = document.getElementById(id);
- return element.innerHTML;
- }
- </script>
- </head>
- <body>
- <div id="area1">
- <pre>
- ＿＿＿＿＿＿＿＿ ＿＿＿＿＿＿＿＿
- （＿＿＿＿＿ ＼ ⊂⊃ ／ ＿＿＿＿）
- （＿＿＿＿＿ ＼ ∧＿∧ ／ ＿＿＿＿）
- （＿＿＿＿ ＼ （ ´∀｀）／ ＿＿＿＿）
- （＿＿＿__⊂ ⊃＿＿＿＿）
- ｜ ｜ ｜
- （＿_）＿）
- </pre>
- </div>
- <br>
- <div id="area2"></div>
- <script type="text/javascript">
- function encodeRunLength(data) {
- var encode_data = new Array();
- var c;
- var len = 0;
- for (var i = 0; i < data.length; i++) {
- if ((0 < len) && (len<9) && (c == data.charAt(i))) {
- len++;
- continue;
- }
- if(len != 0) {
- encode_data.push(c);
- encode_data.push(len);
- }
- c = data.charAt(i);
- len = 1;
- }
- if(len != 0) {
- encode_data.push(c);
- encode_data.push(len);
- }
- return encode_data;
- }
- function decodeRunLength(data) {
- var decode_data = new Array();
- for (var i = 0; i<data.length; i++) {
- if ((i%2) != 0) { continue; }
- var c = data[i];
- var num = parseInt(data[i+1]);
- if (isNaN(num)) { return null; }
- for (var j = 0; j < num; j++) {
- decode_data.push(c);
- }
- }
- return decode_data;
- }
- function execRunLength(input,output) {
- var data = getStringById(input);
- var element = document.getElementById(output);
- element.innerHTML = "元のデータ量: " + data.length + "<br>";
- var encode_data = encodeRunLength(data);
- if (encode_data == null) { return; }
- element.innerHTML += "圧縮しました。<br/>";
- element.innerHTML += "圧縮後のデータ量: " + encode_data.length + "<br/>";
- element.innerHTML += "データを復元します。<br/>";
- var decode_data = decodeRunLength(encode_data);
- if (decode_data == null) { return; }
- element.innerHTML += decode_data.join("");
- element.innerHTML += "<br/>圧縮率: ";
- element.innerHTML += parseInt(encode_data.length / data.length * 100);
- element.innerHTML += "%<br/>";
- }
- </script>
- <input type="button" onClick="execRunLength('area1','area2');" value="RunLength">
- <br><!-- 末尾1 -->
- </body>
- </html>
プログラムを解説します。
11～21行目
圧縮する対象となるデータです。
24行目
結果表示用のdivタグです。
26～52行目
圧縮する関数です。
27行目
圧縮結果は配列に格納します。
31行目
元のデータを1文字ずつループします。
32～35行目
連続文字数lenが9未満で、前の文字cといまの文字が一致すればlenを1増やして次のループに移ります。
37～40行目
前の文字といまの文字が違ったら文字と何文字連続したかを圧縮結果データに追加します。
42、43行目
現在の文字と長さをリセットして次のループに移ります。
54～67行目
圧縮したデータを復元する関数です。
55行目
復元したデータも配列に格納します。
57行目
圧縮データに対してループします。
62～64行目
文字数分ループして文字を追加していきます。
69～88行目
ボタンを押したときに実行する関数です。圧縮を実行して画面に表示します。
90行目
ボタンです。
さて、Webブラウザで実行してみましょう。Webブラウザの種類によってJavaScriptの内部実装が若干違うのでデータ量が少し変わってきますが、おおむね95％くらいになったと思います。
今回のようなアスキーアートに対する圧縮率はいまひとつですが、ランレングス法は白黒の画像データを圧縮する場合などに効果を発揮します。
Copyright © ITmedia, Inc. All Rights Reserved.
Coding Edge 鬯ｯ�ｯ�ｽ�ｯ�ｽ�ｽ�ｽ�ｮ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｫ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｪ鬯ｯ�ｮ�ｽ�ｯ髯具ｽｹ�ｽ�ｺ�ｽ�ｽ�ｽ�ｻ驛｢�ｧ隰�∞�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｿ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｺ鬯ｯ�ｮ�ｽ�｣髯具ｽｹ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｵ鬯ｮ�ｫ�ｽ�ｴ驕ｶ謫ｾ�ｽ�ｵ�ｽ�ｽ�ｽ�ｺ�ｽ�ｽ�ｽ�ｷ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｸ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｷ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｹ鬯ｮ�ｫ�ｽ�ｴ鬮ｮ諛ｶ�ｽ�｣�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�｢�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｳ鬯ｯ�ｯ�ｽ�ｩ髯晢ｽｷ�ｽ�｢�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�｢�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｧ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｭ鬯ｯ�ｯ�ｽ�ｩ髯晢ｽｷ�ｽ�｢�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�｢鬯ｮ�ｫ�ｽ�ｴ鬮ｮ諛ｶ�ｽ�｣�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�｢�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｳ鬯ｯ�ｯ�ｽ�ｩ髯晢ｽｷ�ｽ�｢�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�｢�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｧ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｽ�ｰ
- 「検証はあなたの仕事」 GitHub CopilotにおけるセキュリティのベストプラクティスをGitHubが初学者向けに解説
- 開発現場の「失敗恐怖症」をAIが治療？ クラスメソッドがAI開発導入支援サービスを提供開始
- ダントツで首位のPython、2位のC++との差が過去最大に 2025年5月版プログラミング言語人気ランキング
- 一から始めるローコード開発――タスク管理アプリ作成で分かるkintoneの基本機能
- Microsoftが「Visual Studio Code 1.100」を公開 GitHubリポジトリ横断検索やMCPサポートなど機能拡充
- OAuthだけじゃない 現代のAPI開発者が知るべき「5つの基本戦略」（認証方式編）
- VBAでファイル名や拡張子を取得する方法、特殊フォルダを取得する方法
- 日報メールを半自動化!?――ExcelとVBAで作成するメール作成マクロとは
- JetBrains、C/C++用IDE「CLion」の非商用利用を無料化 非商用ライセンスの注意点は？
- Excelにおける文字列、日付、数値のフォーマット関数の使い方
- ダントツで首位のPython、2位のC++との差が過去最大に 2025年5月版プログラミング言語人気ランキング
- Google、生成AIでアプリのプロトタイピングからデプロイまで支援する「Firebase Studio」を発表 フルスタックAIアプリをどう構築できるのか
- 「検証はあなたの仕事」 GitHub CopilotにおけるセキュリティのベストプラクティスをGitHubが初学者向けに解説
- OAuthだけじゃない 現代のAPI開発者が知るべき「5つの基本戦略」（認証方式編）
- Microsoftが「Visual Studio Code 1.100」を公開 GitHubリポジトリ横断検索やMCPサポートなど機能拡充
- 「Wasmer 6.0」が登場、ネイティブに近い速度でWebAssemblyを実行可能 主要な強化点は？
- Pythonが依然独走、Kotlin、Ruby、Swiftが苦戦 TIOBEプログラミング言語ランキング
- VBAでファイル名や拡張子を取得する方法、特殊フォルダを取得する方法
- 一から始めるローコード開発――タスク管理アプリ作成で分かるkintoneの基本機能
- VS Codeにもついに「持ち込みAI」時代が来た？──バージョン 1.99での変更点を紹介
注目のテーマ
ITmediaはアイティメディア株式会社の登録商標です。