13. 連想リスト、ハッシュ表

1. 初めに

球団名	ホームグラウンド名
千葉ロッテマリーンズ	千葉マリンスタジアム
福岡ソフトバンクホークス	福岡Yahoo!JAPANドーム
西武ライオンズ	インボイスSEIBUドーム
オリックス・バファローズ	大阪ドーム
北海道日本ハムファイターズ	札幌ドーム
東北楽天ゴールデンイーグルス	フルキャストスタジアム宮城
阪神タイガース	阪神甲子園球場
中日ドラゴンズ	ナゴヤドーム
横浜ベイスターズ	横浜スタジアム
ヤクルトスワローズ	明治神宮野球場
読売ジャイアンツ	東京ドーム
広島東洋カープ	広島市民球場

連想リストを取り扱う関数は R⁶RS の List utilities で、また、ハッシュ表は Hashtables で定義されています。

ハッシュ表は SRFI-69 でも、規定されています。処理系によっては、R⁶RS ではなく SRFI に準拠しているのもあるかもしれません。

この文書では R⁶RS に沿って記述します。

2. 連想リスト

連想リストはペアからなるリストで、関連を表現する基本的な方法です。キーにはシンボル、文字、数値などが使われます。文字列をキーに使う時は、シンボルに変換したほうが早く検索できます。

以下は連想リストの例です。ペアになっていれば必ずしもドット対でなくても差し支えありません。

'((hi . 3) (everybody . 5) (nice . 3) (to . 10) (meet . 4) (you . 8))
'((1 2 3) (4 5 6) (7 8 9))

連想リストを検索する関数には、 assq, assv, assoc , assp (R⁶RS のみ) があります。これらの関数は連想リストを逐次検索し、 car 部がキーと等しいペアを返します。ペアがない場合は #f が返ります。また、assq, assv, assoc はキーの比較にそれぞれ eq?, eqv?, equal? を使用しています。また、assp は car 部を proc で処理し、#f にならないものを返します。従って、assq が最も高速に検索でき、assoc が最も低速になります。このことから文字列、ベクトル、リストはシンボルや数値に変換してからキーにしたほうが速度的に有利です。また、多くのデータを検索するときは後述するハッシュ表を利用したほうが高速です。

以下に例を示します。

(require rnrs/lists-6)
(define wc '((hi . 3) (everybody . 5) (nice . 3) (to . 10) (meet . 4) (you . 8)))
⇒ wc

(assq 'hi wc)
⇒  (hi . 3)

(assq 'you wc)
⇒  (you . 8)

(assq 'i wc)
⇒  ()


(define n '((1 2 3) (4 5 6) (7 8 9)))
⇒  n

(assv 1 n)
⇒  (1 2 3)

(assv 8 n)
⇒  ()

3. ハッシュ表

ハッシュ表はキーをハッシュ関数で整数に変換し、配列のその番地に値を保持する表です。表が十分すいているときは、検索、挿入、更新が O(1) オーダーでできる高速なデータ型です。R⁶RS のハッシュ表に関する主な関数を以下に挙げます。詳しくは R⁶RS Hashtablesを参照してください。

(make-eq-hashtable size), (make-eqv-hashtable size), (make-hashtable hash_function equiv size),

ハッシュ表を作成します。size はハッシュ表の初期サイズです。通常は指定する必要はありません。
make-eq-hashtable はキーの比較に eq? を使い、また、make-eqv-hashtable はキーの比較に eqv? を使います。
make-hashtable を使うと、任意のハッシュ関数と比較関数をもつハッシュ表を作れます。例えば、リストをキーにとるハッシュテーブルは

(make-hashtable equal-hash equal?)

で作ります。equal-hash はリストなどからハッシュ値を求める関数です。 R⁶RS では equal-hash, string-hash などのハッシュ関数が規定されています。 eq-hashtable はアドレスを比較するだけのでもっとも高速です。

(hashtable-ref hashtable key default)

hashtable の key に対応する値を返します。 hashtable 中に key が無ければ default を返します。

(hashtable-set! hashtable key datum)

hashtable の key に対応する値を datum にセットします。

(hashtable-size hashtable)

hashtable に含まれる要素の数を返します。

(hashtable? hashtable)

hashtable がハッシュ表なら #t を返します。

(hashtable-delete! hashtable key)

hashtable から key のエントリーを削除します。

(hashtable-contains? hashtable key)

key が hashtable に含まれるときは #t を返します。

(hashtable-keys hashtable)

hashtable のキーからなるベクトルを返します。ベクトルについては次章で説明します。

(hashtable-entries hashtable)

hashtable のキーからなるベクトルと、それに対応する値のベクトルの２つのベクトルを返します。 R⁶RS では複数の値を返すことができるようになりました。これらの値は let-values などで取り出します。

4. パスワード自動生成プログラム

連想リストとハッシュ表を使ったプログラム例として、パスワード自動生成プログラムを書いてみました。

辞書に載っているようなパスワードだと破られる危険が大きいですし、一方、グラフィック文字を全くランダムに並べたパスワードは覚えることはおろか、入力も非常に手間取ります。このプログラムは、部分的にありうる綴りのパスワードを 10 個生成するプログラムです。パスワードはなるべく頻繁に変えたほうが良いのですが、自分の頭で考えるのはかなり億劫です。このプログラムを使えば気軽にパスワードを変更することができます。

このプログラムは２つの部分からなり、１つは英語のテキストから文字のつながりの頻度のデータを生成するプログラム (stat-spell.scm)、もうひとつはそのデータに基づいてパスワードを作るプログラム (make-pw.scm) です。

4.1. stat-spell.scm

このプログラムは、英語の文書を読みこんで、ある文字の次に来る文字とその頻度を関連付けます。途中のデータはハッシュ表で保持し、最後に連想リストに変換し、ファイル (statspell.dat) に保存します。

ソースは [code 1] の様になります。

[code 1]

001:   ;;; make an alist of probable spelling from a given english text
002:   
003:   
004:   ;; モジュールを読み込みます
005:   (require rnrs/base-6)         ; vector-for-each を使うため
006:   (require rnrs/hashtables-6)   ; hashtable
007:   (require rnrs/control-6)      ; when を使うため
008:   (require rnrs/files-6)        ; ファイルシステム
009:   
010:   
011:   
012:   
013:   
014:   ;; スキップする文字列なら #t を返します
015:   (define (skip-char? c)
016:     (case c
017:       ((#\: #\; #\' #\" #\`) #t)
018:       (else (not (char<=? #\Space c #\~)))))
019:   
020:   
021:   
022:   ;; filename のファイルから一文字ずつ読み込み、連続する文字のハッシュ表を作ります
023:   (define (pw-read-text filename)
024:     (let ((char-hash (make-eqv-hashtable)))       ; 全体のハッシュ表です
025:       (with-input-from-file filename
026:         (lambda ()
027:   	(let loop ((c #\Space))
028:   	  (let ((c1 (read-char)))                                      ; 一文字読み込んで、
029:                    (when (not (eof-object? c1))                          ; EOF でなければ、以下の処理を行う
030:                        (if (skip-char? c1)                               ; 
031:                            (loop c)                                      ; スキップする文字なら、スキップして繰り返し。
032:                            (let ((c1 (char-downcase c1))                 ; そうでなければ、小文字に変換し、
033:   			       (h (hashtable-ref char-hash c #f)))     ; その文字のあとの文字の頻度のハッシュ表を char-hash から取り出す。
034:   			   (if (hashtable? h)                          ; 文字 c の後に続く文字のハッシュ表がすでにあれば、
035:   			       (hashtable-set! h c1 (+ 1 (hashtable-ref h c1 0)))  ; 次の文字 c1 の頻度に 1 を加える
036:   			       (let ((h1 (make-eqv-hashtable)))        ; ハッシュ表がまだなければ作成する。
037:   				 (hashtable-set! h1 c1 1)
038:   				 (hashtable-set! char-hash c h1)))
039:   			   (loop c1))))))))                            ; 繰り返し
040:       char-hash))
041:   
042:   
043:   
044:   ;; 個々の文字の後ろの文字の頻度を連想リストにして書き出します。
045:   (define (write-each c h)
046:     (display "(")
047:     (write c)
048:     (display " ")
049:     (let ((n (hashtable-size h)))
050:       (let-values (((vec-c vec-count) (hashtable-entries h))) ; ハッシュ表 h から 文字と頻度のベクトル vec-c, vec-count を取り出します。
051:          (vector-for-each                                     ; vector にわたって (lambda ...  を作用させます。
052:   	(lambda (k v)                                       ; 文字と頻度を書き出します。
053:   	  (display " (")
054:   	  (write k)
055:   	  (display " . ")
056:   	  (write v)
057:   	  (display ") "))
058:   	vec-c vec-count)))
059:     (display ")")
060:     (newline))
061:   
062:   
063:   
064:   ;; 頻度のハッシュ表 char-hash を連想リストにして書き出します。
065:   (define (write-alist filename char-hash)
066:     (when (file-exists? filename)              ; データファイルがすでにあれば削除します
067:       (delete-file filename))
068:     (with-output-to-file filename              ; filename のファイルを開いて、
069:       (lambda ()                               ; データを書き出していきます。
070:         (display "(define *stat-spell* \'(")
071:         (newline)
072:         (let-values(((keys values) (hashtable-entries char-hash)))
073:   	 (vector-for-each
074:   	  (lambda (k v) (write-each k v)) keys values))
075:         (display "))")
076:         (newline))))
077:   
078:   
079:   ;; テキストファイルを読み込んで、連続する文字の頻度データを作ります。
080:   (define (stat-spell input-filename)
081:     (write-alist "statspell.dat" (pw-read-text input-filename)))

実行方法:

> (load/cd "stat-spell.scm")
> (stat-spell "avg.txt")    ; 英語のテキストファイルを読み込ませて頻度データを作る

以下のようなファイル statspell.dat が生成します。

(define *stat-spell* '(
(#\8  (#\0 . 2)  (#\4 . 1) )
.....
(#\k  (#\. . 1)  (#\, . 2)  (#\e . 54)  (#\t . 3)  (#\s . 10)  (#\a . 1)  (#\space . 25)  (#\n . 18)  (#\- . 1)  (#\l . 2)  (#\i . 24) ) *
.....
))

* の行は、文字 #\k のあとには #\., #\e, #\t, #\s, #\a, #\space, #\n, #\-, #\l, #\i がそれぞれ
1, 2, 54, 3, 10, 1, 25, 18, 1, 2, 2, 24 回あったことを示しています。

4.2. make-pw.scm

statspell.dat をもとにしてパスワードを 10 個生成します。生成規則は以下の通りです。

#\Space で終わる、9--13 文字のリストを statspell.dat のデータをもとにしてランダムに生成する。
それに 00--99 の数字をランダムに選んで付け足す。
#\Space をランダムに、#\- #\_ #\/ #\Space #\. #\, で置き換える。
アルファベットの 30% をランダムに大文字にする。

コードは [code 2] の様になります。
random-integer などの乱数に関する関数は SRFI-27 に規定されています。

[code 2]

001:   ;;; make password from the alist of probable spelling
002:   
003:   (require srfi/27)
004:   (require rnrs/hashtables-6)
005:   (require rnrs/control-6)
006:   
007:   
008:   
009:   (load/cd "statspell.dat") ; *stat-spell* (alist for following characters) is in.
010:   
011:   
012:   (define (alist->hash al)
013:     (let ((h (make-eqv-hashtable)))
014:       (for-each (lambda (p)
015:                   (hashtable-set! h (car p) (cdr p)))
016:                 al)
017:       h))
018:   
019:   
020:   
021:   (define (pw-random-select vec)
022:     (vector-ref vec (random-integer (vector-length vec))))
023:   
024:   (define (random00)
025:     (let loop ((i 0) (acc '()))
026:       (if (= i 2)
027:           (list->string acc)
028:         (loop (+ 1 i) (cons (pw-random-select '#(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9)) acc)))))
029:   
030:   (define (occasional-upcase c)
031:     (if (< (random-integer 10) 3)
032:         (char-upcase c)
033:       c))
034:   
035:   (define (pw-enhance ls)
036:     (list->string
037:      (map (lambda (c)
038:             (cond
039:              ((char=? c #\Space)
040:               (pw-random-select  '#(#\- #\_ #\/  #\Space  #\. #\, #\@ #\? #\( #\))))
041:              ((char-alphabetic? c)
042:               (occasional-upcase c))
043:              (else c)))
044:           (cdr (reverse ls)))))
045:       
046:   
047:   (define (random-following alist)
048:     (let ((n (random-integer (apply + (map cdr alist)))))
049:       (let loop ((j 0) (alist alist))
050:         (when (pair? alist)
051:   	  (let* ((pair (car alist))
052:   		 (k (+ j (cdr pair))))
053:   	    (if (> k n)
054:   		(car pair)
055:   		(loop k (cdr alist))))))))
056:   
057:   (define (make-pw h n)
058:     (let loop ((i 0) (c #\Space) (acc '()))
059:       (if (= i n)
060:           (string-append
061:            (pw-enhance (cons #\Space (cons c acc)))
062:            (random00))
063:         (loop (+ 1 i)
064:           (random-following (hashtable-ref h c '((#\Space . 1))))
065:           (cons c acc)))))
066:       
067:   (define (pw-candidates)
068:     (let loop ((i 0))
069:       (when (< i 10)
070:   	  (display i)
071:   	  (display ": ")
072:   	  (write (make-pw (alist->hash *stat-spell*) (+ 9 (random-integer 4))))
073:   	  (newline)
074:   	  (loop (+ 1 i)))
075:         'done))

(alist->hash al mode): al を mode のハッシュ表に変換します。
(pw-random-select vec): vec の要素をランダムに選びます。この関数は次回説明するベクトルを使っています。ランダムにアクセスする場合はリストよりベクトルの方が高速です。
(random00): 文字列 "00" -- "99" をランダムに作ります。
(occasional-upcase c): 30% の確率で c をランダムに大文字にします。
(pw-enhance ls): 文字のリスト ls を加工してパスワードを破られにくくします。
(random-following alist): 連想リスト alist の中から、頻度に基づいて文字をランダムに選びます。
(make-pw h n): ハッシュ表 h を使って n+3 文字のパスワードを作ります。パスワードの最後はランダムな２桁の数字です。
(pw-candidates): 長さが 12--15 のパスワードを 10 個生成します。

次のように使用します。それらしいパスワードの候補が 10 個表示されますので気に入ったのを使用します。stat-spell は一回だけ実行すればよく、２回目からは make-pw をロードして、 (pw-candidate) を実行すればパスワードの候補が表示されます。

> (load/cd "make-pw.scm")
> (pw-candidates)
0: "S.bowAtof.t_)13"
1: "igIf@t)yO?61"
2: "icOFEAnly?98"
3: "prabER)Y_in(96"
4: "He@lat,Ms@74"
5: "SrtoRepASti)96"
6: "y?s)pmP m,_-52"
7: "tEmm(kIo)sT@51"
8: "AilITheRviS/.08"
9: "TObe-INy,,p 86"
done
>

5. 終わりに

パスワード生成プログラムは付録に付けておきますので遊んでみてください。次回はベクトルについて説明します。