%===================================================================== % 秋田高専 2E 情報工学概論 テキスト %　　テーマ マップとハッシュ % 本テキストの内容 % ・ % ・ % ・ % ・ %　　　 　・ % % last updated 2006.1.28 % created by Masashi Yamamoto % e-mail yamamoto@akita-nct.jp %===================================================================== \documentclass[10pt,a4paper]{jarticle} \usepackage{graphicx,amsmath,amssymb,ascmac,float} \usepackage{html, listings, jlisting} \usepackage{url} \oddsidemargin 0mm %左の余白 25.4mm-0mm　奇数ページ \evensidemargin 0mm %左の余白 25.4mm-0mm　偶数ページ \textwidth 160mm \newcommand{\command}[1]{「\texttt{#1}」} \newcommand{\cl}[1]{\texttt{#1}} \newcommand{\tw}[1]{\texttt{#1}} % \newcounter{toi_num} \newcommand{\toi}{\textbf{\texttt [問\arabic{toi_num}]} \addtocounter{toi_num}{1}} % \newcommand{\qbox}[2]{ {\fboxsep=0pt \fboxrule=0.4pt\fbox{\hspace{#1}#2\hspace{#1}}} } % \renewcommand{\lstlistingname}{リスト} \lstset{language=C,% basicstyle=\footnotesize,% commentstyle=\textit,% classoffset=1,% keywordstyle=\bfseries,% frame=tRBl,framesep=5pt,% showstringspaces=false,% numbers=left,stepnumber=1,numberstyle=\footnotesize% }% % \begin{htmlonly} \usepackage{verbatimfiles} \providecommand{\lstinputlisting}[2][]{\verbatimlisting{#2}} \end{htmlonly} % \begin{document} \title{マップとハッシュ} \author{山本昌志\thanks{独立行政法人　秋田工業高等専門学校　電気情報工学科}} \date{2006年1月30日} \maketitle % % %===================================================================== \section{本日の学習内容} %===================================================================== %--------------------------------------------------------------------- \subsection{前回の復習} %--------------------------------------------------------------------- ツリー構造をC言語で実装する方法を学習した．ツリー構造のノードを示すポインターは， 次のようになっていた． \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} typedef struct _tag_tree_node { int value; struct _tag_tree_node *left; struct _tag_tree_node *right; } tree_node; \end{verbatim} \end{quote} このノードを用いて，ツリー構造を取り扱うためには，次の関数が必要であった． \begin{itemize} \item ノードの作成 \item ノードの追加 \item ノードのサーチ(探索) \item ノードの削除 \item メモリーの解放 \end{itemize} % %--------------------------------------------------------------------- \subsection{本日の学習内容} %--------------------------------------------------------------------- 本日は教科書~\cite{text_algorithm_data}の第7章である．以下のことを学ぶ． \begin{itemize} \item 2分木を用いたマップ \item ハッシュ法 \begin{itemize} \item ハッシュ法の基本的な考え方 \item ハッシュ表の意味 \item ハッシュ関数の作り方 \item ハッシュ値の衝突(重複)が生じた場合の回避の仕方 \end{itemize} \end{itemize} % %===================================================================== \section{解決したい問題} %===================================================================== 英単語のデータベースを作ることを考える．表\ref{table:word}のようにスペルと和訳の 組があり，探索(サーチ)と削除，追加ができるようにする．もちろん，これはコンピュー ターのメモリー上で実現させるのである． \begin{center} \begin{minipage}{60mm} \begin{table}[H] \caption{単語データベース} \label{table:word} \begin{center} \begin{tabular}{ll} \hline スペル & 和訳\\ \hline \hline orange & みかん \\ apple & リンゴ \\ peach & 桃 \\ pineapple & パイナップル \\ pear & 梨 \\ grape & ぶどう \\ \quad$\vdots$ &\quad$\vdots$ \\ \hline \end{tabular} \end{center} \end{table} \end{minipage} \begin{minipage}{60mm} \begin{figure}[H] \begin{center} \includegraphics[keepaspectratio,scale=0.8] {figure/word_in_memory.eps} \caption{データはメモリーに入れる} \label{fig:list} \end{center} \end{figure} \end{minipage} \end{center} 単語は，スペルと和訳が組になっている．このような場合，構造体を使うのが常套手段で ある．複数の単語を表す単純なデータ構造として，教科書~\cite{text_algorithm_data} では以下の2つの方法が示されている． \begin{itemize} \item リスト \item 配列 \end{itemize} リストを探索する場合，必ず先頭から順番に調べる．そのため，予めソートしても探索ス ピードは変わらない．したがって，ソートする必要がなく，データの追加はリストの末尾 に接続することになる．このような場合，探索には$O(N)$，削除には$O(N)$,追加には $O(N)$の計算量が必要となる．実際，ソートすると実行スピードは変わるが，オーダーは 変わらないことに注意しよう． 配列の場合，バイナリーサーチが使えるので，予めソートしておくと探索スピードを向上 させることができる．しかし，データの追加と削除を行う場合，配列の入れ替えが必要と なり，そこでの計算量が増加する．この場合，探索には$O(\log_2 N)$，削除には$O(N)$， 追加には$O(N)$の計算量が必要となる．ソートしない配列の場合，計算量のオーダーはリ ストと変わらない． まとめると，表\ref{table:list_array}のようになる．いずれにしても，データ数$N$が 大きくなると，かなりの計算量が必要となる． \begin{table}[H] \caption{計算量のオーダー} \label{table:list_array} \begin{center} \begin{tabular}{llll} \hline 方法 & 探索 & 削除 & 追加 \\ \hline \hline リスト & $O(N)$ & $O(N)$ & $O(N)$ \\ ソートされた配列 & $\log_2 N$ & $O(N)$ & $O(N)$ \\ \hline \end{tabular} \end{center} \end{table} リストや配列を使うと$O(N)$のオーダーの計算量が必要になってくる．もう少し，スピード アップしたい場合，マップというものが使われる．通常は， \begin{itemize} \item 「2分木」をつかった「ツリーマップ」 \item 「ハッシュ表」をつかった「ハッシュマップ」 \end{itemize} が使われる． % %===================================================================== \section{2分木を使ったツリーマップ} %===================================================================== 以前学習した2分木を使ったツリーであれば，探索と追加，削除が$O(\log_2N)$程度とな り，リストやソートされた配列よりも高速である．そのためには，英単語のスペルの大小 関係の比較が出来ることが条件で，C言語では\tw{strcmp()}という関数が用意されている． この関数は，次のようになっている． % \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} #include int strcmp(char *s1, char *s2); \end{verbatim} \end{quote} % ヘッダーファイル\tw{string.h}が必要で，ポインター\tw{s1}と\tw{s2}が示す文字列を 比較する．文字列の大小は辞書順となる．比較の結果は，戻り値により表され，以下のようになる． \begin{table}[H] \caption{\tw{strcomp}の戻り値} \label{table:return_strcmp} \begin{center} \begin{tabular}{p{20mm}c} \hline \tw{s1 > s2} & 正 \\ \tw{s1 = s2} & 0 \\ \tw{s1 < s2} & 負 \\ \hline \end{tabular} \end{center} \end{table} % 後は今まで学習したとおりであるが，もう一度，C言語のプログラムの書き方の復習をし ておく．まずは，構造体であるが，次のように定義する． \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} typedef struct tag_word{ char *english; char *japanese; struct tag_word *left; struct tag_word *right; }word_node; \end{verbatim} \end{quote} メモリーの確保とデータの代入とデータの取り出しは，次のようにする． \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} word_node *cc; cc=(word_node *)malloc(sizeof(word_node)); cc->english="apple"; cc->japanese="リンゴ"; cc->left=NULL; cc->right=NULL; printf("%s\t%s\n",cc->english,cc->japanese); \end{verbatim} \end{quote} 後は，学習したとおりで，2分木で表すと図\ref{fig:map_B_tree}のようになる． \begin{figure}[H] \begin{center} \includegraphics[keepaspectratio,scale=0.9] {figure/map_B_tree.eps} \caption{2分木を用いたマップ．アルファベット順にソートしている．} \label{fig:map_B_tree} \end{center} \end{figure} %===================================================================== \section{ハッシュマップ} %===================================================================== %--------------------------------------------------------------------- \subsection{基本的な考え方} %--------------------------------------------------------------------- 単語のスペルから直に配列の添え字の値が導くことが出来れば，$O(1)$の計算量で済む． これはとても高速である．たとえば，表\ref{table:word}に示した単語データベースのよ うなものを配列に格納することを考える．ただし，以下の条件を課す． \begin{itemize} \item スペルが同じで意味の異なる単語は無いものとする． \item スペルは最大，アルファベットで9文字とする． \end{itemize} 次のようにすれば，スペルから配列の値を求めることができる． \begin{itemize} \item アルファベットに対して，整数を割り当てる．\tw{a}が\tw{1}，\tw{b}が\tw{2}， \tw{c}が\tw{3},$\cdots$,\tw{z}が\tw{26}のようにである．もうひとつアルファ ベット長い場合(空白)が必要で，それは\tw{0}を割り当てる．このようにすれば， 英単語は整数$(a_1a_2a_3a_4a_5a_6a_7a_8a_9)$で表現できる．\\ \qquad apple$\rightarrow$(1,16,16,12,5,0,0,0,0)\qquad\qquad pineapple$\rightarrow$(16,9,14,5,1,16,16,12,5) \item これを9次元配列に格納することもできるが，少し工夫して1次元配列\tw{a[i]}に格納する ことを考える．つぎの演算により，添え字\tw{i}を求めれば1次元配列とすることができ る． \begin{align*} i=a_1\times27^0+a_2\times27^1+a_3\times27^2+a_4\times27^3+a_5\times27^4+a_6\times27^5+a_7\times27^6+a_8\times27^7+a_9\times27^8 \end{align*} \end{itemize} このようにスペルから直接添え字の値が計算できる配列に英単語を格納すると，とても高 速に探索，削除，追加ができるデータ構造となる．すべて，計算量のオーダーは$O(1)$で ある．しかし，この方法をよく考えると大きな問題がある．巨大なメモリー空間が必要な のである．配列の最大の添え字は，$1\times27^9-1=7625597484986$となりとても現在のコンピューター で取り扱うことができない． このような配列に単語を格納すると，ほとんどその中は空になる．単語の数はそれほど多 くない．諸君の英和辞典の単語数を調べてもよく分かる．そこで，この配列の添え字を \tw{0}〜\tw{99999}に圧縮することを考える．新たな添え字を\tw{j}とすると， % \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} j=i%100000; \end{verbatim} \end{quote} % とすれば良い．\tw{100000}で割った余りとすれば，\tw{0}〜\tw{99999}の値が得られる． このようにして，データにアクセスする方法をハッシュ法と言う．得られた値(\tw{0}〜 \tw{99999})をハッシュ値と言い，キーを変数として，それを求める関数をハッシュ関数 と言う． このようにすると，明らかに以下の問題点がある． \begin{itemize} \item 異なるキーで同じハッシュ値となる場合がある． \end{itemize} これについて，以降，教科書に沿って説明する． % %--------------------------------------------------------------------- \subsection{ハッシュ値の決め方} %--------------------------------------------------------------------- ハッシュを使う場合，配列にそのままデータを入れないで，データを表すポインターを入 れる方が便利である．ポインターが表すものを構造体とすれば，かなり柔軟に対応できる． 後で述べるがハッシュ値の重複(衝突)対策でリストやツリー構造を使う場合も対応が容易 である． ハッシュ法を使うためには，教科書に書いてあるとおり，以下のような動作が必要である． \begin{itemize} \item ハッシュ表を用意する．これは，ポインターを格納する配列である． \item ハッシュ関数(ハッシュ値)を決める． \end{itemize} ハッシュ表は，データを示すポインターを入れる配列である．キーを決めるとハッシュ関 数を計算してハッシュ値が決まる．このハッシュ値がこの配列の添え字の値となる．そし て，そこに格納されている配列の値(ポインター)により，データにアクセスする． ハッシュ表を作るときにはデータ数よりも大きいことが望ましい．そうしないと，異なっ たキーでも同じハッシュ値となり，衝突が発生し，データの探索スピードが落ちてしまう． 衝突の問題は後で述べるので，ここではハッシュ関数の作り方を説明する．ハッシュ表の 大きさは素数とすることが望ましい．こうすることにより，キーのどのビットが変化して もハッシュ値の値を変化させることができる． ハッシュ関数は，一般に，次の2つの手順により成り立っている． \begin{itemize} \item キーからなにがしかの演算を行い整数値を導き出す． \item 導き出された整数をなにがしかの演算により，ハッシュ表(配列)の大きさの整数に直 す． \end{itemize} 最初のキーから整数値を導き出す方法は，いろいろある．これについては，教科書の方法 を説明する．一方，これをハッシュ表の大きさの整数に直す方法は，大体決まっている． キーから導き出された整数をハッシュ表の大きさで割って，その余りとするのである． % %--------------------------------------------------------------------- \subsection{ハッシュ値の重複対策} %--------------------------------------------------------------------- 異なるキーであっても，同じハッシュ値となることがある．これが多いとハッシュ法の効 果が薄いのであるが，どうしても避けることができない．プログラマーはその対策を講じ なくてはならない．教科書に書かれている方法は，次の通りである． \begin{itemize} \item リストを用いる方法(教科書 p.222 Fig.7-7) \item 2分木を用いる方法(教科書 p.224 Fig.7-9) \item 再ハッシュ(教科書 p.222 Fig.7-8　p.224 Fig.7-10) \end{itemize} これらについては，教科書を用いて説明する． % %===================================================================== \section{練習問題} %===================================================================== \setcounter{toi_num}{1} \begin{quote} \begin{itemize} \item[\toi]6桁の整数$(a_1a_2a_3a_4a_5a_6)$をハッシュを用いて配列に格納することを 考える．ハッシュ関数を$mod(a_1+a_2+a_3+a_4+a_5+a_6,17)$とする． $mod(x,y)$は$x$を$y$で割った余りとする．C言語では，\tw{x\%y}である． 以下の問いに答えよ． \begin{itemize} \item ハッシュ値の取りうる値の範囲を述べよ． \item 以下の場合のハッシュ値を述べよ．\\ (ア) 246801\qquad(イ) 986532\qquad(ウ) 123456\qquad(エ) 654321 \end{itemize} \item[\toi]ハッシュ関数を$mod(a_1+a_2+a_3+a_4+a_5+a_6,17)$とした場合，123456と 654321は同じハッシュ値になる．これを防ぐためには，ハッシュ関数をど のようにすれば良いかのべよ． \end{itemize} \end{quote} %--------------------------------------------------------------------- \subsection{レポート提出要領} %--------------------------------------------------------------------- 提出方法は，次の通りとする． % \begin{quote} \begin{tabular}{ll} 期限 & 2月6日(月) AM 10:40 \\ 用紙 & A4 \\ 提出場所 & 山本研究室の入口のポスト \\ 表紙 & 表紙を1枚つけて，以下の項目を分かりやすく記述すること．\\ & \qquad 授業科目名「情報工学」\\ & \qquad 課題名「課題　ハッシュ」\\ & \qquad 2E\quad 学籍番号\quad 氏名\\ & \qquad 提出日\\ 内容 & 2ページ以降に問いに対する答えを分かりやすく記述すること． \end{tabular} \end{quote} % \newpage %===================================================================== \section{付録} %===================================================================== %--------------------------------------------------------------------- \subsection{アスキーコード} %--------------------------------------------------------------------- % 教科書にアスキーコード表が載っていないので，表\ref{table:asci_code}に載せておく． この表から数字(10進数)を計算する方法は，次のようにする． % \begin{enumerate} \item 対応する文字の上位3ビットの値を探す． \item 次に下位4ビットを探す． \item 対応する整数の計算を行う．計算方法は$16\times(\text{上位3ビット})+(\text{下 位4ビット})$である．ただし，A=10, B=11,$\cdots$,F=15である\footnote{よう するに16進数}． \end{enumerate} 具体的な例で表すと，大文字の'd'は，\texttt{64}なので \begin{equation} 16\times6+4=100 \end{equation} となる． % \begin{ttfamily} \begin{table}[H] \caption{アスキーコード表．表の行(0〜7)は上位3ビットで，列(0〜F)は下位4ビット を表す．表中の2文字以上のものは文字ではなく，制御コードと呼ばれる特殊文字である．} \label{table:asci_code} \begin{center} \begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline \hline 0 & NUL & DLE & SP & 0 & @ & P & ` & p \\ \hline 1 & SOH & DC1 & ! & 1 & A & Q & a & q \\ \hline 2 & STX & DC2 & " & 2 & B & R & b & r \\ \hline %" 3 & ETX & DC3 & \# & 3 & C & S & c & s \\ \hline 4 & EOT & DC4 & \$ & 4 & D & T & d & t \\ \hline 5 & ENQ & NAK & \% & 5 & E & U & e & u \\ \hline 6 & ACK & SYN & \& & 6 & F & V & f & v \\ \hline 7 & BEL & ETB & ' & 7 & G & W & g & w \\ \hline 8 & BS & CAN & ( & 8 & H & X & h & x \\ \hline 9 & HT & EM & ) & 9 & I & Y & i & y \\ \hline A & LF & SUB & * & : & J & Z & j & z \\ \hline B & VT & ESC & + & ; & K & [ & k & \{ \\ \hline C & FF & FS & , & \texttt{<} & L & \textbackslash & l & \texttt{|} \\ \hline D & CR & GS & - & = & M & ] & m & \} \\ \hline E & SO & RS & . & \texttt{>} & N & \texttt{\^} & n & \texttt{\~}\\ \hline F & SI & US & / & ? & O & \_ & o & DEL \\ \hline \end{tabular} \end{center} \end{table} \end{ttfamily} % %===================================================================== % 参考文献 %===================================================================== \bibliographystyle{jplain} \bibliography{reference} %===================================================================== \end{document}