第2章 · データ

ビット、圧縮、情報

コンピュータが持つものは、数も、名前も、写真も、曲も、突き詰めればビットのパターンです。

ビット（2進数字の略）は、0か1のどちらかです。コンピューティングデバイスは、データをデジタルに表します。どんな値でも、最も低いレベルの構成要素はビットです。

図は2進数で数えます。タイルの1枚が1ビットで、紙の面が0、赤い面が1です。タイルの下には位の値、128, 64, 32, 16, 8, 4, 2, 1があります。1ずつ増やすたびに、一番右のビットが反転し、1が0に反転するところでは、00000111（7）が00001000（8）になるときのように、繰り上がりが1つ左へ伝わります。

プログラムは、データの値を変数や項目のリストに入れたり、単独の定数として持ったりして、手続きに入力として渡し、出力として受け取ります。どの形であっても、値はビットとして保存され、プログラムが人間に読める形に変換します。

この章は、AP Computer Science Principles のビッグアイデア2「データ」で、選択問題の試験の17〜22%を占めます。2進数（2.1）、データ圧縮（2.2）、データからの情報の抽出（2.3）、データを使うプログラム（2.4）を学びます。

2.1 · 一つのパターン、いくつもの意味

ビットをまとめて抽象化にする

バイトは8ビットです。バイトだけでは意味を持ちません。意味は、それを読むプログラムが何として扱うかで決まります。

抽象化とは、主要な考え方に注目して複雑さを減らすことです。目の前の問いに関係のない詳細を隠し、関連する有用な詳細をまとめることで、ビットではなく考え方そのものを考えられるようになります。

ビットはまとめられて、数、文字、色などの抽象化を表します（これらに限りません）。図は1バイト 01000001 を3通りに読みます。

このように、同じビット列が、文脈によって異なる種類のデータを表すことがあります。カラー画像では、一般に1画素あたり、赤、緑、青に1つずつ、3つの数を保存します。つまり3バイト、24ビットです。

2.1 · 2進数から10進数へ

位取りは、右から0番として数える

2進数や10進数など、基数を使ってデータを表します。10進数（基数10）は0〜9の数字だけを使い、2進数（基数2）は0と1だけを使います。

10進数と同じように、数字の位置がその値を決めます。数としての値は、数字に、その位置の位の値をかけたものです。位の値は、基数をその位置の数だけ累乗したもので、位置は一番右を0として、左へ1ずつ増えます。10進数では、305 = 3 × 10² + 0 × 10¹ + 5 × 10⁰ です。

2進数では、各位の価値は、右隣の2倍です。10110101 の場合：

ビットが1の位の値を足します。128 + 32 + 16 + 4 + 1 = 181。0のビットは何も足しません。図は左から右へ読み、1が出るたびに、その位の値が合計に落ちます。

2.1 · 10進数から2進数へ

入る中で最大の位の値をとる

正の整数を2進数で書くには、最大の位の値から順に見ていきます。残りに位の値が入るなら、1と書いてそれを引き、入らないなら0と書きます。

8ビットで100を表すと：

つまり、100 = 01100100：64 + 32 + 4 = 100。先頭の0は何も変えないので、01100100 と 1100100 は同じ数です。

もう一つの方法：2で割ることをくり返し、剰余を最後から最初に向かって読みます。100 ÷ 2 = 50 あまり 0; 50 ÷ 2 = 25 あまり 0; 25 ÷ 2 = 12 あまり 1; 12 ÷ 2 = 6 あまり 0; 6 ÷ 2 = 3 あまり 0; 3 ÷ 2 = 1 あまり 1; 1 ÷ 2 = 0 あまり 1。下から上へ読むと、1100100 です。

図の青い棒は100の残りです。1のたびに、その位の値が棒から切り離され、タイルが赤くなります。

2.1 · nビットで2ⁿ個の値

2進数の比較

1ビットには2通りのパターンがあります。ビットが1つ増えるごとに、数は倍になります。それまでのパターンの前に0をつけたものと、1をつけたものです。したがって、nビットには2ⁿ通りのパターンがあります。

図はそれを組み立てます：1 ビット, 2; 2 bits, 4; 3 bits, 8; 4 bits, 16。1バイトには2⁸ = 256通りのパターンがあり、0から255までの整数を表せます。nビットで表せる最大の数は、すべてが1のときの 2ⁿ − 1 です。

26個の文字にそれぞれ別のパターンを与えるには、何ビット必要でしょうか。2⁴ = 16では足りません。2⁵ = 32なら足ります。答えは5ビットです。

比較と順序づけ。2つの数に同じビット数を与え（先頭に0をつけてそろえ）、左から見ていきます。最初に異なる位置で決まります。そこが1の数のほうが大きいのです。その位の価値1つが、右にあるすべての位の価値を合わせたものより大きいからです（2^p > 2^p − 1）。

01101100 と 01011111 は、位置5の32の位で初めて異なり、最初の数がそこで1です。そのあとのビットが何であっても、108 > 95 です。

2.1 · 固定されたビット数の限界

オーバーフローと丸め誤差

多くのプログラミング言語では、整数は決まったビット数で表されます。そのため、整数の値の範囲とその計算には限界があり、オーバーフローなどのエラーが起こることがあります。

図のカウンタ（仮想のもの）は4ビットで、0から15までを保持します。15（1111）に1を足すには5番目のビットが必要です。繰り上がりの行き場がなく、カウンタは0を示します。これがオーバーフローです。

ほかの言語は、整数の大きさがコンピュータのメモリの大きさだけで制限される抽象化を提供しています。試験の参照シートにある言語は、その一つです。その整数はオーバーフローしません。

実数（小数部分のある数）も決まったビット数で保存されるので、範囲とその計算に限界があり、丸め誤差などのエラーが起こることがあります。実数には、近似値としてしか保存されないものがあります。小数部が3ビット（図は仮想のもの）だと、1/8 = 0.125の倍数しか存在せず、0.1は0.125として保存され、0.025だけずれます。

実際の言語はもっと多くのビットを使うので、誤差ははるかに小さくなりますが、なくなりはしません。多くの言語で、0.1 + 0.2 は 0.30000000000000004 になります。実数の範囲の具体的な限界は、このコースと試験の範囲外です。

2.1 · 標本化されるアナログデータ

デジタルによる近似

アナログデータは、時間とともに、とびとびではなくなめらかに値が変わるデータです。音楽の高さと音量、絵画の色、レース中の短距離走者の位置などがそうです。

コンピュータが保存するのはビットなので、アナログデータは近似することしかできません。現実世界のアナログデータをデジタルデータで近似することは、抽象化の一例です。

アナログデータは、標本化によってデジタルで近い値に近似できます。標本化とは、アナログ信号の値を一定の間隔で測ることで、測った値を標本と呼びます。各標本を測定して、それを保存するのに必要なビットを正確に求めます。

図は、同じなめらかな信号を2回標本化します。まず8個の標本を、それぞれ4段階（2ビット）のどれかに丸めます。8 × 2 = 16ビットで、粗い階段になります。次に8段階（3ビット）で16個の標本をとります。16 × 3 = 48ビットで、階段は曲線により近づきます（信号との平均の距離は43%小さくなります）。

標本が多く、1標本あたりのビットが多いほど、近似は正確になりますが、保存や送信に必要なビットも増えます。標本をどれだけ増やしても、正確にはなりません。

2.2 · 可逆圧縮

小さくなり、正確に元に戻る

データ圧縮は、送信または保存するデータの大きさ（ビット数）を減らせます。可逆アルゴリズムは、多くの場合、元のデータを完全に復元できることを保証しながら大きさを減らせます。

図の列には20個の画素があり、1つが1バイトなので20バイトです（仮想のもの）。ランレングス符号化は、同じ色の連なりを、個数と色で保存します。7W 4R 6W 3B、4個の連なり × 2バイト = 8バイトです。

復号すると7 white, 4 red, 6 white, 3 blueになり、元の列と画素ごとに完全に一致します。何も失われていないので、ビット数が少ないことが、情報が少ないことを意味するとは限りません。

どれだけ小さくなるかは、元のデータの冗長性の大きさと、使う圧縮アルゴリズムの両方で決まります。長い連なりはよく圧縮できます。1画素ごとに色が入れ替わる列（WRWRWR…）には、長さ1の連なりが20個あります。符号化すると40バイトになり、元の20バイトより大きくなります。

2.2 · 非可逆圧縮

さらに小さいが、近似でしかない

非可逆アルゴリズムは、保存または送信するビット数を大きく減らせますが、復元できるのは元のデータの近似だけです。

図の16個の画素（仮想の明るさで、1つが1バイト）は、2つ組ごとの平均だけを残します。8バイト、つまり半分の大きさです。復号すると、各画素に2つ組の平均が入ります。16個のうち14個が元と違う値で返り、差は最大10です。灰色の影が元の値で、8バイトのどこにも、それを取り戻す手がかりはありません。200と180の組も、190と190の組も、平均は190です。

非可逆アルゴリズムは、多くの場合、可逆のものより多くビット数を減らせます。どちらを選ぶかは状況で決まります。

2.3 · データから情報へ

パターンと、それが証明しないこと

情報とは、データから取り出された事実とパターンの集まりです。データを使うと、傾向を見つけ、関連づけ、問題に取り組むことができます。

図は、ビーチの町の仮想の24日分について、アイスクリームの売上と日焼けの件数を並べてプロットしたものです。一方が増えるともう一方も増えます。強い相関です（相関係数 r = 0.86。1なら完全な直線です）。

アイスクリームが日焼けの原因なのではありません。日を気温で色分けすると、理由がわかります。7日の暑い日（赤、27 °C以上）には、アイスクリームもよく売れ、日差しも強いのです。データに見つかった相関は、因果関係があることを必ずしも意味しません。関係の正確な性質を知るには、さらに調べる必要があります。

ここでは、売上の記録だけではそれがわかりませんでした。多くの場合、一つの情報源には結論を出すために必要なデータがそろっておらず、複数の情報源（売上、診療所の受診、気象の記録）のデータを組み合わせる必要があります。

2.3 · メタデータ

データについてのデータ

メタデータは、データについてのデータです。写真がデータで、そのメタデータには、作成日、ファイルサイズ、大きさ、タグなどがあります。

メタデータを変更したり削除したりしても、元のデータは変わりません。図ではタグ「夕焼け」を削除しますが、64個の画素は一つも変わりません。

メタデータは、情報を探し、整理し、管理するために使われます。写真ライブラリは、画素を一つも見なくても、June 14に撮ったすべての写真や、「ビーチ」のタグがついたすべての写真を一覧にできます。メタデータは、追加の情報を与えることでデータをより効果的に使えるようにし、データを構造化して整理できるようにします。

試験では、集められたデータとメタデータが場面として示され、何がわかるかが問われます。各項目が何を記録しているかを考えましょう。日付とタグだけのライブラリは、「6月に撮った写真は何枚か」には答えられますが、「この写真はどこで撮ったか」には答えられません。場所を記録した項目がないからです。

2.3 · データのクレンジング

意味を変えずに、そろえる

データセットには、大きさによらず課題があります。データを整える（クレンジング）必要があること、不完全なデータ、無効なデータ、そして複数のデータ源を組み合わせる必要があることです。データを処理できるかどうかは、利用者とその道具の能力で決まります。

データの集め方によっては、そろっていないことがあります。ユーザーが自由入力欄に入力すると、略し方、つづり、大文字小文字の使い方が人によってばらばらになります。図の登録フォーム（仮想のもの）には、2都市について7通りの表記があります。

クレンジングは、同じ意味の略語、つづり、大文字小文字をすべて同じ語に置き換えて、意味を変えずにデータをそろえます。5個の項目が書き換えられ、7通りの表記が2になります。これで、都市ごとの登録数を数えるプログラムが、正しく数えられます。

クレンジングでは、欠けているものを作り出せません。ある行には年齢がなく（不完全）、ある行には−4とあります（無効）。これらには印をつけ、確認するか、分析から外します。推測はしません。

2.3 · バイアスと規模

多いデータが、よいデータとは限らない

バイアスの問題は、集めるデータの種類や出どころによって生じることがよくあります。バイアスは、ただデータを多く集めるだけでは取り除けません。

図の世論調査（仮想のもの）は、集団の左側にしか届きません。たとえば、一つのウェブサイトの読者です。集団全体では41%が赤の意見です。30件の回答のあとでは調査は80%と示し、60件のあとでは78%と示します。回答が2倍になっても、間違った姿は同じです。すべての回答が、同じ偏った出どころから来ているからです。

それでも大きさは重要です。データセットの大きさは、そこから取り出せる情報の量に影響します。しかし、大きなデータセットは、1台のコンピュータでは処理しにくく、並列システム、つまりデータの各部分を同時に処理する多くのプロセッサが必要になることがあります。

データセットを扱うときは、システムのスケーラビリティが重要な検討事項です。システムの計算能力が、データセットをどのように処理し、保存できるかに影響するからです。

2.4 · フィルタリングと変換

リストを処理するプログラム

プログラムを使うと、データを処理して情報を得られます。検索ツールは情報を効率よく見つけるのに役立ち、データのフィルタリングシステムは、情報を見つけてデータのパターンを見分けるための重要な道具です。

フィルタリングは、条件を満たす要素だけを残します。たとえば、リストから正の数だけを残す、吹奏楽に登録した生徒だけを残す、といったことです。

data ← [4, -2, 7, 0, -5, 3] positives ← [] FOR EACH n IN data { IF(n > 0) { APPEND(positives, n) } }

図はそれを実行し、実行中の行を赤で示します。n が1つずつ調べられ、n > 0 を満たすものだけが追加されます。positives は最終的に[4, 7, 3]になります。0 > 0 は false なので、0は残りません。

変換は、すべての要素を変えます。たとえば、リストのすべての要素を2倍にする、すべての生徒の記録に保護者のメールアドレスを加える、といったことです。最初に doubled ← [] としておくと：

FOR EACH n IN data { APPEND(doubled, 2 * n) }

doubled は最終的に[8, −4, 14, 0, −10, 6]になります。データを変換したり加工したりすることで洞察が得られ、プログラムでデータを変換すると、パターンが現れることがあります。プログラマは、プログラムでデータをフィルタリングしたり、整えたりもします。

2.4 · 組み合わせと可視化

多くの値から一つの数へ、そしてグラフ

データを組み合わせたり比べたりすると、多くの値が一つの答えにまとまります。数のリストを合計する、GPAが最も高い生徒を見つける、といったことです。可視化は、データセットをグラフや図などの視覚的な表現で示します。

あるクラブが6週間の登録数を記録します（仮想のもの）：signups ← [12, 18, 9, 22, 15, 20]。

total ← 0 most ← signups[1] FOR EACH n IN signups { total ← total + n IF(n > most) { most ← n } } DISPLAY(total) DISPLAY(most)

表示されるのは 96 22 です。6週間で合計96人が登録し、最も多い週は22人でした。most は0ではなく、最初の値 signups[1] から始まるので、すべての値が負でも正しく動きます。実行されるにつれて、図は各週を棒として描きます。データが読み込まれるにつれて、グラフができあがります。

表、図、文章などの視覚的な道具を使うと、データから得た洞察や知識を伝えられます。表計算ソフトなどのプログラムは、情報を効率よく整理し、傾向を見つけるのに役立ちます。

プログラムは、反復的で対話的に使われます。グラフを見て、新しい問いを立て、またフィルタリングや変換をします。データ源を組み合わせること、データのクラスタリング（似たものをグループにすること）、データの分類（項目をカテゴリに振り分けること）は、プログラムを使ってデータから洞察や知識を得ることの一部です。