2分木の応用(意思決定木と演算子)
データをO(log N)で検索するための2分探索木以外の2分木のデータ構造について解説を行う。
意思決定木
意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。
((意思決定木の例:小さい子供が発熱した時)) 38.5℃以上の発熱がある？ no／ ＼yes 元気がある？ むねがひいひい？ yes／ ＼no no／ ＼yes 様子をみる 氷枕で病院 解熱剤で病院 速攻で病院
このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じである。左右に枝のあるものは質問であり、yesの枝もnoの枝もない末端は最終決断を表す。このようなデータ構造は意思決定木と呼ばれ、質問と決断の処理は以下のように記述ができる。
import java.util.* ;
import java.util.Scanner ;
class TreeNode {
String qa ;
TreeNode yes ;
TreeNode no ;
TreeNode( String s , TreeNode y , TreeNode n ) {
this.qa = s ;
this.yes = y ;
this.no = n ;
}
} ;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner( System.in ) ;
TreeNode top =
new TreeNode( "38.5℃以上の発熱がある?" ,
new TreeNode( "胸がひぃひぃ?" ,
new TreeNode( "速攻で病院" , null , null ) ,
new TreeNode( "解熱剤で病院" , null , null ) ) ,
new TreeNode( "元気がある?" ,
new TreeNode( "様子をみる", null , null ) ,
new TreeNode( "氷枕で病院", null , null ) ) ) ;
TreeNode p = top ;
while( p.yes != null || p.no != null ) {
System.out.println( "Question:" + p.qa ) ;
if ( sc.nextInt() == 1 ) {
System.out.println( "yes" ) ;
p = p.yes ;
} else {
System.out.println( "no" ) ;
p = p.no ;
}
}
System.out.println( "Answer:" + p.qa ) ;
}
}
- 意思決定木(Paiza.io)
struct Tree {
char *qa ;
struct Tree* yes ;
struct Tree* no ;
} ;
struct Tree* dtree( char *s ,
struct Tree* l , struct Tree* r )
{ struct Tree* n ;
n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
if ( n != NULL ) {
n->qa = s ;
n->yes = l ;
n->no = r ;
}
return n ;
}
void main() {
struct Tree* p =
dtree( "38.5℃以上の発熱がある?" ,
dtree( "胸がひぃひぃ?" ,
dtree( "速攻で病院", NULL,NULL ) ,
dtree( "解熱剤で病院",NULL,NULL ) ) ,
dtree( "元気がある?" ,
dtree( "様子をみる", NULL,NULL ) ,
dtree( "氷枕で病院", NULL,NULL ) ) ) ;
// 決定木をたどる
struct Tree* d = p ;
while( d->yes != NULL || d->no != NULL ) {
printf( "%s¥n" , d->qa ) ;
scanf( "%d" , &ans ) ;
// 回答に応じてyes/noの枝に進む。
if ( ans == 1 ) // yesを選択
d = d->yes ;
else if ( ans == 0 ) // noを選択
d = d->no ;
}
// 最終決定を表示
printf( "%s¥n" , d->qa ) ;
}
2分木の応用として次週以降に式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。
逆ポーランド記法
一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。
演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。
中置記法 1+2*3 前置記法 +,1,*,2,3 後置記法 1,2,3,*,+ # 1と「2と3をかけた値」をたす。
後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式をコンピュータで実行する際の処理と似ている。
演算子の右結合・左結合
例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか？3/2だろうか？
一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。
ただしC言語やJavaでは、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。
理解度確認
以下の式を指定された書き方で表現せよ。
逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。 中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。
以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。
ネットワーク層とIPアドレス
ネットワーク層とIPアドレス(IPv4)
(前回の復習)
サブネットに分割し、隣接するサブネット、さらには上流のインターネットと通信をするためには、IPアドレスを用いた通信が行われる。
ネットワークに接続する機器には、それぞれユニークな32bitの番号(IPv4アドレス)を割り振る。
コンピュータへのIPアドレスの設定には、(a)IPアドレス,(b)サブネットマスク,(c)ゲートウェイの情報が必要となる。
- IPアドレス: 192.156.145.100 といった、0～255の8bitの値をピリオド区切りで4つ並べて表記するのが一般的。
- サブネットマスク: 255.255.255.0 といった値で、IPアドレスを2進数で書き並べた32bitと、サブネットマスクの32bitで、2進数の論理積をとった値は、ネットワーク番号と呼ばれ、機器が存在する場所を表す。
また、IPアドレスとサブネットマスクの否定と論理積をとった値は、ホスト番号と呼ばれる。
サブネットマスクは、先行する1のbit数で書き表すことも多い。255.255.255.0は、”/24″のように書く。 - ゲートウェイ: 自分自身のネットワーク番号と通信相手のネットワーク番号が異なる場合は、異なるサブネットにいるので、パケットを中継してもらう機器(ルータ,ゲートウェイ)にパケットを送る。
- IPアドレスとクラス: IPアドレスは、先頭8bit をネットワーク番号とするクラスA,16bitのクラスB,24bitのクラスCに分類されている。以前は、IPアドレスを割り当てる企業規模に応じて、大規模な大学だからクラスA、中規模ならクラスB(福井大学は133.7.0.0/16 ←このような書き方はCIDR記法という)、小規模ならクラスCを割り当てていた。(福井高専はCクラスを5本192.156.145～149.0/24 : 福井高専のIPアドレスでは3つのCIDR記法で表現できる。 192.156.145.0/24, 192.156.146.0/23, 192.156.148.0/23)
しかし、最近では IPv4 アドレスの不足から、大きな組織に割り振られた クラスA を再分配しているため、先頭が0～126で始まるアドレスでも大きなネットワーク組織とは限らない。
ユニキャスト、マルチキャスト、ブロードキャスト通信
通信では、機器が1対1でデータを送る(ユニキャスト通信)だけでなく、複数の機器に同時にデータを送りたいこともある。
同じサブネット内の全てにデータを送る時には、ブロードキャスト通信が用いられる。この際には、IPアドレスのサブネットにおけるホスト番号部分が全て1のアドレスを使う。Cクラスの 192.168.11.x/24 のネットワークであれば、192.168.11.255 がブロードキャスト通信用のアドレスとなる。一般的にホスト番号部分が全て0のアドレスは、サブネット全体を表すために使われることから、192.168.11.0 のIPアドレスも通常の通信には使えない。このため、Cクラス(サブネットマスク24bit)であれば、256台-2台(全て0と全て1のホスト番号)を引いた254台の機器が設置できる。(実際には、他のネットワークに接続するためのゲートウェイアドレスも必要なので 253台)
動画などの配信では、ユニキャスト通信が使われると、サーバから通信相手までのルータまでに同じデータが送られてくる。こういった方式では大量の視聴者がいる場合、ネットワークの帯域が埋まってしまい、効率の良い配信ができない。同じデータを同じタイミングで複数の機器に配信したい場合はマルチキャスト通信を使う。IPv4では 224.0.0.0/4 を使う。
ARP(IPアドレスとMACアドレスの橋渡し)
同じサブネットの中では、データリンク層でMACアドレスを用いて通信相手を指定するが、ネットワーク層ではIPアドレスを用いて通信相手を指定する。この違いを埋めるためのプロトコルがARPである。
サブネット内に相手先IPアドレスの指定されたパケット(10.10.22.102)が届くと、通信機器はサブネット内の全ての機器相手に ARPリクエストを送信する。(10.10.22.102はいますか？ブロードキャスト通信を使う)
この時、10.10.22.102 のコンピュータは、自分宛てのパケットがあることを知るので、送信元のコンピュータに、自分のMACアドレスを付けたARPリプライを送り返す。(10.10.22.102は、私 “FE:DC:BA:98:76:54” です!)。送信元は、ARP通信をへらすために、その情報を記憶して、2度目以降は覚えたMACアドレスですぐに通信を始める。
ルータとRIP
ルータは、隣接するサブネットの間に入る機器で、各サブネットにゲートウェイとなるインタフェースを持つ。ルータの内部では受け取ったパケットをどこに流すか…という経路情報が重要となる。
- 静的ルーティング – 末端のルータの設定で、管理者が経路を設定
- 動的ルーティング – 上流ルータでRIPにより設定
経路設定には2種類あり、(a)末端のルータではこのネットワーク番号はどのルータに送るという情報をルータに直接設定する静的ルーティングがとられる。(b)上流のルータでは、末端のルータの設定が変更されることがあるので、ルータ同士がルーティング情報を送りあう動的ルーティングがとられる。動的ルーティングでは、RIPというプロトコルにより、各サブネットのつながっている経路情報が送られてくる。この経路情報を見て、パケットのIPアドレスを見て、パケットの送り先を判断する。(ネットワークの上流では、複数のネットワーク経路を操る BGP などが使われる)
((Windows の場合))
C:> ipconfig
インタフェース名:
IPv4アドレス............192.168.xx.xx
サブネットマスク.........255.255.255.0
デフォルトゲートウェイ....192.168.xx.1
C:> arp -a
インタフェース:
192.168.xx.xx 74-03-xx-xx-xx-xx 動的
192.168.xx.yy B0-05-xx-xx-xx-xx 動的
C:> netstat -r
ネットワーク宛先 ネットマスク ゲートウェイ インタフェース メトリック
0.0.0.0 0.0.0.0 192.168.xx.1 192.168.xx.xx 45
192.168.xx.0 255.255.255.0 ....
((Unix の場合))
$ ifconfig -a # もしくは ip addr
en1: ....
inet 192.168.xx.xx netmask 0xffffff00 ...
$ arp -an # もしくは ip neigh
.... (192.168.xx.xx) at 74:03:xx:xx:xx:xx ...
.... (192.168.xx.yy) at b0:05:xx:xx:xx:xx ...
$ netstat -rn # もしくは ip route
Destination Gateway ...
default 192.168.xx.1 ...
192.168.xx ...
プライベートアドレス
IPv4 では、32bit でコンピュータを識別することから、最大でも 232台≒40億台(4×103×3台)しか識別できない。実際、IPアドレスの管理団体では、2017年度には IPv4 アドレスは使い切った状態となっている。この対応として、その組織やその家庭内だけで使われる IPアドレス である、プライベートアドレスが用いられる。
- 10.0.0.0～10.255.255.255 / 8 – 大きな機関向け
- 172.16.0.0～172.31.255.255 / 12
- 192.168.0.0～192.168.255.255 /16 – 個人向け
プライベートアドレスを利用する組織では、インターネットに接続するルータでは NAT(もしくはNAPT) という機能を内蔵し、プライベートアドレスとグローバルアドレスの変換を行う。
ローカルループバックアドレス
ネットワーク通信では、1つのコンピュータの中でもプロセスとプロセスの間でデータ通信を行うことも多い。この時に使われるIPアドレスは、ローカルループバックアドレスと呼ばれ、IPv4では 127.0.0.1 のIPアドレスを使う。このアドレスには localhost というドメイン名が割り振られる。
IPv6アドレス
IPv4の32bit の IP アドレスでは、40億台のコンピュータを区別することしかできない。そこで、最近では 128bit の IPv6 アドレスが用いられる(256×102412台≒340×1036台)。 IPv6 では、2004:6800:4004:0826:0000:0000:0000:2003 (www.google.co.jp) といった16進数4桁(16bit)を8個を”:”区切りで書き連ねる書き方をする。ただし16進4桁の先行する0や、全部”0000″ は省略して、”2404:6800:4004:826::2003″ と書く。IPv6 は最近では普及がかなり進んでいるが、途中のルータなどがすべて IPv6 に対応する必要があり IPv4 しか使えない組織も多い。
IPv6でも、同じサブネット内だけで使えるIPv6リンクローカルアドレス(fe80::/10)や、同じ組織内だけで使えるIPv6サイトローカルアドレス(fec0::/10)、ループバックアドレス(::1)などが規定されている。
DNS と nslookup
IPアドレスみたいな数字の羅列は覚えることが難しい。このためコンピュータの名前からIPアドレスを調べるサービスがあり、Domain Name Service(DNS) と呼ばれる。詳しい仕組みは ドメイン名の説明の際に行うが、IP アドレスの調べ方を説明する。
ドメイン名から、IP アドレスを調べるには、nslookup (もしくは dig) を使用する。
$ nslookup www.fukui-nct.ac.jp : Non-authoritative answer: Name: www.fukui-nct.ac.jp Address: 104.215.53.205 $ nslookup -query=A www.fukui-nct.ac.jp # IPv4 アドレスの取得 (同上) # もしくは dig www.fukui-nct.ac.jp A +short $ nslookup -query=AAAA www.google.co.jp # IPv6 アドレスの取得 : # もしくは dig www.google.co.jp AAAA +short Non-authoritative answer: Name: www.google.co.jp Address: 2404:6800:4004:826::2003
理解確認
- Formsによる理解度確認問題
- 192.168.11.2/24 のコンピュータから、192.168.1.50にデータを送る場合、どのような処理が行われるか、IPアドレス、サブネットマスク、ゲートウェイ、ネットワーク番号を使って説明せよ。
- 同じサブネット内で相手のIPアドレスが与えられた時、どのようにパケットが送られるか、MACアドレスとARPを交えて説明せよ。
GROUP BY HAVINGとビューテーブル
GROUP BY HAVING
GROUP BY-HAVING では、指定されたカラムについて同じ値を持つレコードがグループ化される。SELECT 文に指定される集約関数は、グループごとに適用される。HAVING は、ある条件を満たす特定のグループを選択するための条件で、WHERE と違い、集約関数が使える。
SELECT SG.商品番号, SUM(SG.在庫量) FROM SG GROUP BY SG.商品番号 HAVING SUM(SG.在庫量) >= 500 ;
このSQLを実行すると、SG のテーブルから、商品番号が同じものだけをあつめてグループ化される。そのグループごとに在庫量のデータの合計SUMを集約し、合計が500以上のデータが出力される。
|
⇒ |
|
⇒ |
|
CREATE VIEW
今までで述べてきたSQLでは、実際のテーブルを対象に、結合・選択・射影を行う命令であり、これは概念スキーマと呼ばれる、対象となるデータベース全体を理解したプログラマによって扱われる。
しかし、プログラムの分業化を行い、例えば結果の表示だけを行うプログラマにしてみれば、全てのデータベースの表を考えながらプログラムを作るのは面倒である。そこで、結合・選択・射影の演算の結果で、わかりやすい単純な表となったものであれば、初心者のデータベースプログラマでも簡単に結果を扱うことができる。このような外部スキーマを構成するための機能が、ビューテーブルである。
-- 優良業者テーブルを作る --
CREATE VIEW 優良業者 ( 業者番号 , 優良度 , 所在 )
AS SELECT S.業者番号, S.優良度, S.所在
FROM S
WHERE S.優良度 >= 15 ;
-- 優良業者テーブルから情報を探す --
SELECT *
FROM 優良業者
WHERE 優良業者.所在 = '福井' ;
-- 文房具データベース --
CREATE VIEW 文房具データベース ( 業者名 , 商品名 , 在庫量 )
AS SELECT S.業者名, G.商品名, SG.在庫量
FROM S, SG, G
WHERE S.業者番号 = SG.業者番号 and SG.商品番号 = G.商品番号 ;
-- VIEWの確認 --
SELECT * FROM 文房具データベース ; -- 串刺ししたデータベースに見える
----- 実行結果 -----
業者名 商品名 在庫量
ABC社 赤鉛筆 300
ABC社 ノート 200
ABC社 消しゴム 400
ABC社 消しゴム 200
ABC社 筆箱 100
ABC社 バインダ 100
LMN社 赤鉛筆 300
LMN社 ノート 400
PQR社 ノート 200
STU社 ノート 200
STU社 消しゴム 300
STU社 筆箱 400
ビューテーブルに対する SQL を実行すると、システムによっては予め実行しておいた CREATE VIEW の AS 以下の SQL の実行結果をキャッシュしておいて処理を行うかもしれない。システムによっては SQL の命令を 副クエリを組合せた SQL に変換し、処理を行うかもしれない。しかし、応用プログラマであれば、その SQL がどのように実行されるかは意識する必要はほとんど無いであろう。
ただし、ビューテーブルに対する 挿入・更新・削除といった演算を行うと、データによっては不整合が発生することもあるので注意が必要である。
SQL言語
教科書の流れに沿ってSQLの言語について、再掲
- スキーマ定義
- CREATE – 実テーブル、ビューテーブルの定義
- GRANT – 権限の定義
- スキーマ操作
- DROP – 実テーブル、ビューテーブルの削除
- REVOKE – 権限の削除
- ALTER – テーブルの変更
- ADD – カラムの追加
- データ操作
- SELECT, INSERT, DELETE, UPDATE – レコードの検索、追加・削除・更新
- トランザクション処理
- データベースでは、原子性などを満たすためにデータベースへの更新履歴を保持している。これらの更新履歴をデータベースに反映させ確定する処理がトランザクション処理。
- COMMIT – データベースの更新処理を確定
- ROLLBACK – データベースの更新処理を取り消す
ホスト言語とのインタフェースとSQLインジェクション
プログラミング言語によっては、その言語の中でSQLを使うために「組み込み型のSQL」が使えるものがある。
(COBOL,PL/Iなど)
動的メモリ管理が得意な最近のPythonやPHPなどの言語であれば、データベース参照の関数が利用できる。
SQLインジェクション
例えば、PHPでは、SQLからデータを取り出す処理は、以下のようになる。
// 検索するユーザID
$id = "t-saitoh" ;
$pdo = new PDO( '...' ) ; // データベースに接続する関数
$sql = "select name from usertable where id='$id'" ;
$query = $pdo->prepare( $sql ) ;
// 取り出せたデータに関する処理 id がプライマリキーならforeachは1回ループのはず
foreach( $query->fetcAll() as $name ) {
// $name に取り出した名前が入っている
}
しかし、$id の部分を、Web の入力フォームなどの値であれば、名前以外の情報が入力される場合もある。
この際に、「 $id = ” ‘ or 1==1 — ‘ ” 」といった値が入っていた場合、SQLで実行される命令は、
$id = "' or 1==1 --'" の場合 $sql = "select name from usertable where id='' or 1==1 -- ''" ;
となってしまい、本来なら1人のデータを抽出する select 命令が、全テーブルに対して該当してしまい、情報漏洩が発生するかもしれない。
「 $id = “‘; drop usertable ; — ‘” 」であれば、usertable が消されてしまい、システムが動かなくなる(サービスを提供できなくする攻撃 = DoS攻撃 – Denial-of-service attack)ことも考えられる。
他にもSQLインジェクションを使う技がある。こちらの CTF の WriteUp などが参考になる。
こういった攻撃手法は、SQLに本来の意図ではないSQL命令を紛れ込ませる攻撃ということで、SQLインジェクションという。
SQLインジェクションで発生した有名な事件では、以下のようなものがある。
- Yahoo! BB 顧客情報漏洩事件 – 100億円を超える被害
- PlayStation Network個人情報流出事件
対策としては、ユーザが入力したデータを用いて SQL 命令を実行する場合は、ユーザ入力をSQLとして悪用されないように、シングルクオートなどをエスケープするなどの処理が必要となる。さまざまな手法があるので、SQL無効化の専用関数を用いるべき。
また、データベースシステムは、ネットワーク経由でSQLによる処理を行うが、データベースサーバ自体がインターネットに接続されていて、パスワード攻撃によりデータベース本体に不正アクセスが行われる場合もある。一般的なデータベースを用いたシステムは、フロントエンドのWebサーバ、スレーブDBサーバ、マスタDBサーバの三層構成をとることが多いが、バックエンドのデータベースは、インターネットから隔離しフロントエンドのWebサーバのみ接続できるようにするのが一般的である。
データベースに接続する場合はパスワードにより利用者を限定することができるが、データベースシステム自体がインターネットに接続されていると、パスワード総当たり攻撃(ブルートフォース攻撃)や、パスワードスプレー攻撃(総当たり攻撃は、短時間でパスワード失敗が多発するのでシステムで接続拒否するのが一般的。これを回避するために時間をかけて総当たり攻撃をする手法)により、情報漏洩が発生する。