他校生との共同作品でふくいソフトウェア大賞受賞
福井県産業支援センター主催のふくいソフトウェアコンペティション2017にて、他校の学生さんと共同作品で5EI野村くんらのグループが、ふくいソフトウェア大賞を受賞しました。
WWWとhttp
前回の DNS とメールで紹介の抜けていた点を補足。内容は前回の講義録に追記。
WWWとhttp
WWWとは、ティム・バーナーズ=リーによって作られたサービスであり、元々は研究データの論文やデータの共有のために作られた。この際のWebサーバのデータのやり取りのためのプロトコルがhttp(Hyper Text Transfer Protocol)であり、ポート番号80のTCPを用いたものであり、最近では通信を暗号化したhttps(ポート番号443)も多く使われる。
httpでは、文字データの中に画像や音声といった情報に加え、他のデータへのリンクを埋め込むことができる HTML(Hyper Text Markup Language) のデータがやりとりされる。このHTML形式のデータを表示するためのソフトは、ブラウザと呼ばれる。
URL
WWWのデータの場所を示すものが、URL(Uniformed Resource Locator)であるが、最近ではインターネットが複雑化しLocator という表現が難しいため、URI(Uniformed Resource Identifier)と呼ぶようになってきた。
URLは基本的に、スキーマ://コンピュータ名/サーバ内ファイル位置 といった文字で構成される。URL は、HTTP だけでなく、インターネットの情報の場所を記述するために使われており、httpやhttps以外にも使う。
http
httpのサーバ(Webサーバ)とブラウザでは、以下のような手順で処理が行われる。例えば http://www.ei.fukui-nct.ac.jp/~t-saitoh/index.html のページが表示されるまでを考えると、
- ブラウザのURL欄に、目的サイトのURLを入力。
- 基本的には、スキーマ欄に記載されたプロトコル(http)名から、ポート番号と通信方法(http)を決める。
- コンピュータ名部分(www.ei.fukui-nct.ac.jp)を DNS に問合せして、得られたIPアドレスのコンピュータに接続。
- httpの最も簡単な GET メソッドでは、Webサーバに、サーバ内のファイル位置(/~t-saitoh/index.html)を伝えると、Webサーバは指定された場所のファイルを返送する。
- HTML形式のデータが指定された場合、ブラウザはその HTML をどの様に表示するか判断しながら表示する。
このような予め保存されているWebページを返送する場合は静的ページと呼ばれる。サーバのデータベースなどを参照しながらページ内容を返送する場合は、動的ページと呼ばれ、CGI(Common Gateway Interface) という手法が使われたり、動的なページを表示するためのプログラム言語(例えばPHP)が使われる。
サーチエンジン
インターネットでは、大量のWebページが出現してきたため、自分の目的に応じてWebページを探す機能が必要となってきた。このような目的のWebページを検索してくれるシステムは、サーチエンジンと呼ばれる。
ディレクトリ型
最初に現れた検索システムは、ページ作者が自分のページのURLと内容となるキーワードを登録しておき、内容のカテゴリー別に、ページの紹介文章が表示されるディレクトリ型であった。(初期のYahoo)
しかし、登録するキーワード以外の文字で探そうとすると、情報を見つけることができない。
ロボット型
これらの問題を解決すべく登場したのが、Google のようなロボット型サーチエンジンである。
ロボット型の検索システムでは、クローラーとかロボットとか呼ばれるプログラムを使い、Webページの内容をダウンロードし、そこに記載された文字を使ってURLのデータベースを作成する。クローラーは、リンクが貼られていると、そのページでも同様の処理を行い、大量の情報を次々と取得していく。
直接サーバと接続
サーバの動作を知るために、メールサーバやWebサーバと直接通信をしてみよう。
この実験をするには、telnet コマンドを使う。telnet コマンドは、タイプされた文字をサーバに送り、サーバから返答された文字を画面に表示するだけの単純なコマンドである。
使い方： telnet 相手サーバ ポート番号 (例1) メールサーバに接続 $ nslookup -query=MX fukui-nct.ac.jp # 自組織メールサーバを探す : Non-authoritative answer: fukui-nct.ac.jp mail exchanger = 10 smtp.ip.fukui-nct.ac.jp. $ telnet smtp.ip.fukui-nct.ac.jp 25 # メールサーバに接続 Trying 10.10.21.55... Connected to smtp.ip.fukui-nct.ac.jp. Escape character is '^]'. 220 ews.ip.fukui-nct.ac.jp EGVA/SMTP Ready. HELO ei.fukui-nct.ac.jp # 送信開始 250 Requested mail action okay, completed. MAIL FROM: foo@ei.fukui-nct.ac.jp # 送信元の設定 250 Requested mail action okay, completed. RCPT TO: bar@example.jp # 送信先の設定 250 Requested mail action okay, completed. DATA # メールデータ 354 Enter mail, end with "." on a line by itself. From: foo@ei.fukui-nct.ac.jp Subject: test test . 250 Requested mail action okay, completed. QUIT # 送信中止 (例2) Webサーバに接続 # http://www.ei.fukui-nct.ac.jp/~t-saitoh/ を参照 $ telnet www.ei.fukui-nct.ac.jp 80 Trying 104.215.24.241... Connected to fnctei.ei.fukui-nct.ac.jp. Escape character is '^]'. GET /~t-saitoh/ http/1.1 # GET ファイル位置 プロトコル <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" id="sixapart-standard"> ：
文字をキーとするハッシュ値
前回のハッシュ法では、数値(電話番号)をキーとする検索であった。 このためハッシュ関数は、数値の不規則性の部分を取り出すだけでよかった。 それでは、文字をキーとしてデータを探す場合はどのようにすればよいか？
文字列をキーとするハッシュ
文字の場合は、文字コードを用いてハッシュ値を作れば良い。
int hash_func( char* s ) {
int sum = 0 ;
for( int i = 0 ; s[i] != '¥0' ; i++ )
sum += s[i] ;
return sum % HASE_SIZE ;
}
しかし、この方法では、文字の並び順が違うだけ(“ABC”,”CBA”,”BBB”)に対して、 同じハッシュ値となってしまう。 英文字の場合は文字数も限られ、文字コード的には末尾4bitが変化するだけであり、 上位ビットは文字数に左右されることになる。 この場合、同じような文字数であれば、末尾4bitの不規則性も平均化されて、 近いハッシュ値になることが懸念される。
そこで、文字コード的に変化のある部分が、数値的に全体に影響を及ぼし、 最終的な値が広く分布するように以下のような計算とする場合が多い。
// 積算部のみ sum = ( sum * (小さめの素数) + s[i] ) % (大きめの素数) ;
このような考え方は、疑似乱数を生成する方式と近い部分が多い。
共有のあるデータの取扱い問題
struct List* join( struct List* p , struct List* q )
{ struct List* ans = p ;
for( ; q != NULL ; q = q->next )
if ( !find( ans , q->data ) )
ans = cons( q->data , ans ) ;
return ans ;
}
void list_del( struct List* p )
{ // ダメなプログラムの例
while( p != NULL ) { // for( ; p != NULL ; p = p->next )
struct List* d = p ; // free( p ) ;
p = p->next ;
free( d ) ;
}
}
void main() {
// リストの生成
struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
struct List* b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
struct List* c = join( a , b ) ; // c = { 4, 1, 2, 3 }
// ~~~~~~~ ここは a
// a,b,cを使った処理
// 処理が終わったのでa,b,cを捨てる
list_del( c ) ;
list_del( b ) ;
list_del( a ) ; // list_del(c)ですでに消えている
} // このためメモリー参照エラー発生
参照カウンタ法
上記の問題の簡単な解決方法は、参照カウンタ法である。
参照カウンタ法は、データを指すポインタ数を一緒に保存し、
- データ生成時は、refc = 1
- 共有が発生する度に、refc++
データを消す場合は、
- refc–
- refc が 0 の時は、本当に消す
struct List {
int refc ; // 参照カウンタ
int data ; // データ
struct List* next ; // 次のポインタ
} ;
void list_del( strcut List* p ) { // 再帰で全廃棄
if ( p->refc <= 0 ) { // 参照カウンタを減らし
list_del( p->next ) ; // 0ならば本当に消す
free( p ) ;
}
}
ただし、参照カウンタ法は、循環リストではカウンタが0にならないので、取扱いが苦手。
G空間×ICT北陸まちづくりトライアルコンクール
12月16日に「G空間×ICT北陸まちづくりトライアルコンクール」の最終審査会が開催され、小越研究室の5EI田中さん(発表),北本くん,高島くん,三田くん,1PS西塚くんで応募した「快適なバリアフリーツアーのためのガイドマップアプリ：さぽっち」が、(株)PFUより奨励賞を頂きました。
