意思決定木と構文解析
意思決定木
意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。
((意思決定木の例:うちの子供が発熱した時)) 38.5℃以上の発熱がある？ no／ ＼yes 元気がある？ むねがひいひい？ yes／ ＼no no／ ＼yes 様子をみる 氷枕で病院 解熱剤で病院 速攻で病院
このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じであり、このような処理は以下のように記述ができる。
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 ) ;
scant( "%d" , &ans ) ;
if ( ans == 1 )
d = d->yes ;
else if ( ans == 0 )
d = d->no ;
}
printf( "%s¥n" , d->qa ) ;
}
コンパイラと言語処理系
高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により
- インタプリタ(interpreter:翻訳)
- ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
- コンパイラ(compiler:通訳)
- ソースプログラムから機械語を生成し、実行する際には機械語を実行
- トランスコンパイラ:ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
- バイトコードインタプリタ:ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
に分けられる。
コンパイラが命令を処理する際には、以下の処理が行われる。
- 字句解析(lexical analysys)
文字列を言語要素(token)に分解 - 構文解析(syntax analysys)
tokenの並び順に意味を反映した構造を生成 - 意味解析(semantics analysys)
命令に合わせた中間コードを生成 - 最適化(code optimization)
中間コードを変形して効率よいプログラムに変換 - コード生成(code generation)
実際の命令コードとして出力
バイトコードインタプリタとは
例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、特殊である。
(( Java の場合 )) foo.java (ソースコード) ↓ Java コンパイラ foo.class (中間コード) ↓ JRE(Java Runtime Engine)の上で 中間コードをインタプリタ方式で実行
あらかじめコンパイルされた中間コードを、JREの上で中間コードをインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。
ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラにより、中間コードを機械語に変換してから実行する。
また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。
しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。
トークンと正規表現(字句解析)
規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。
((正規表現の書き方)) 選言 「abd|acd」は、abd または acd にマッチする。 グループ化 「a(b|c)d」は、真ん中の c|b をグループ化 量化 パターンの後ろに、繰り返し何回を指定 ? 直前パターンが0個か1個 「colou?r」 * 直前パターンが0個以上繰り返す 「go*gle」は、ggle,gogle,google + 直前パターンが1個以上繰り返す 「go+gle」は、gogle,google,gooogle
正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。
[文字1-文字2...] 文字コード1以上、文字コード2以下 「[0-9]+」012,31415,...数字の列 ^ 行頭にマッチ $ 行末にマッチ ((例)) [a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現
構文とバッカス記法
言語の文法を表現する時、バッカス記法(BNF)が良く使われる。
((バッカス記法)) 表現 ::= 表現1... | 表現2... | 表現3... | ... ;
例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。
((加減乗除式のバッカス記法))
加算式 ::= 乗算式 '+' 乗算式
| 乗算式 '-' 乗算式
| 乗算式
;
乗算式 ::= 数字 '*' 乗算式
| 数字 '/' 乗算式
| 数字
;
数字 ::= [0-9]+
;
上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?
このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。
また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。
＋ ／ ＼ １ ＊ ／ ＼ 23 456
理解度確認
- インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
- 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。
北陸イノベーショントライアルにてキャンパス部門優秀賞🎉
11月7日(火)に石川県立音楽堂で行われたHIT2018(第5回ビジネスモデル発見＆発表会 北陸大会 および 起業家甲子園・起業家万博 北陸予選)に、福井高専の高専プロコンと専攻科学生による合同チームが参加し、キャンパス部門優秀賞と起業家甲子園挑戦権を獲得しました。
GROUP BY-HAVINGとCREATE VIEW
先週に引き続き、2つのSQLとそれと同じ処理のプログラム作成の課題に取り組む。
演習だけでは進度が少ないので、SQL で説明できなかった、GROUP BY-HAVING と CREATE VIEW の説明
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 優良業者.所在 = '福井' ;
ビューテーブルに対する SQL を実行すると、システムによっては予め実行しておいた CREATE VIEW の AS 以下の SQL の実行結果をキャッシュしておいて処理を行うかもしれない。システムによっては SQL の命令を 副クエリを組合せた SQL に変換し、処理を行うかもしれない。しかし、応用プログラマであれば、その SQL がどのように実行されるかは意識する必要はほとんど無いであろう。
ただし、ビューテーブルに対する 挿入・更新・削除といった演算を行うと、データによっては不整合が発生することもあるので注意が必要である。
debian で django を動かす
卒研で Django を debian なサーバで動かしたいので、メモ
Django をインストール
最初、起動に失敗したので、python3-pip を入れたら、無事に動き出した。
$ sudo aptitude install python3-django python3-pip
ユーザが Django を起動
$ cd # 自分のホームディレクトリに環境を構築 $ django-admin startproject myapp $ cd myapp $ python3 manage.py migrate $ python3 manage.py runserver 127.0.0.1:8000
卒研が進んで、うまく動くようになったら、service に登録して運用しよう。