Mercurial > hg > Papers > 2016 > masa-master
view paper/c6.tex @ 62:0d13c52a54fd
remove bm_search explain
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 15 Feb 2016 20:56:13 +0900 |
parents | 4efa1c7604f5 |
children | f8c66cefe63e |
line wrap: on
line source
\chapter{結論} \subsection{一つのノードに Word を含める} これまでの正規表現は一文字ずつ参照して状態を割り振っていった。この状態割り振りの問題として文字列の長さの分だけ状態ができてしまう。 状態が長くなればなるほど、ファイルと正規表現のマッチング時の状態遷移数もそれだけ多くなってしまう。 状態遷移数が多くなると、それだけ状態と入力を見て次の状態に遷移するという動作を何度も繰り返すことになってしまうので、処理的にも重くなってしまう。 同じ正規表現でも状態を少なくすればそのような繰返し処理も減っていくので、状態数を減らせばマッチングするまでの処理を軽減することができる。 状態数を減らす工夫として、文字列を一つの状態として見ることによって状態数を減らす。 図\ref{fig:wordstate}は、`word' という文字列の正規表現の正規表現木、DFA 及び状態遷移テーブルである。 一文字ずつそれぞれに状態を割り振った場合、状態数 5 のオートマトンが構成される。 これを一つの文字列に対して状態を割り振った場合、状態数 2 のオートマトンが構成され、状態数を削減することができる。 \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.17]{images/regex/wordstate.pdf} \end{center} \caption{文字単位の状態割り振りを文字列単位での状態割り振りに変更} \label{fig:wordstate} \end{figure} 実際にファイルに対して文字列を検索するときは、Boyer-Moore String Search と呼ばれる 1977 年に Robert S. Boyer と J Strother Moore が開発した文字列検索アルゴリズムを採用して高速化を図ろうとする。\cite{bmsearch}