Mercurial > hg > Members > masakoha > seminar
comparison 2015/1117.html @ 38:0d280684e31f
add some files
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Sat, 21 Nov 2015 14:57:09 +0900 |
parents | f9293af3d474 |
children |
comparison
equal
deleted
inserted
replaced
37:f9293af3d474 | 38:0d280684e31f |
---|---|
100 </div> | 100 </div> |
101 </td> | 101 </td> |
102 </tr> | 102 </tr> |
103 <tr> | 103 <tr> |
104 <td><div align="right"> | 104 <td><div align="right"> |
105 <name>Masataka Kohagura 4th, August , 2015</name> | 105 <name>Masataka Kohagura 17th, November , 2015</name> |
106 </div></td> | 106 </div></td> |
107 </tr> | 107 </tr> |
108 </tr> | 108 </tr> |
109 </table> | 109 </table> |
110 </div> | 110 </div> |
112 <div id="cover"> | 112 <div id="cover"> |
113 <h1>研究目的</h1> | 113 <h1>研究目的</h1> |
114 正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。<br> | 114 正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。<br> |
115 この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。<br> | 115 この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。<br> |
116 コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。<br> | 116 コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。<br> |
117 本研究では正規表現を並列処理で実装することによってこの問題を解決し、Class NC に対応するライブラリを作成する。 | 117 本研究では正規表現の問題を並列処理で実装し、速く処理できるようにする。 |
118 </ul> | 118 </ul> |
119 </div> | 119 </div> |
120 | 120 |
121 <div id="cover"> | 121 <div id="cover"> |
122 <h1>これまで実装しているところ</h1> | |
123 <ul> | |
124 <li>与えられたから正規表現から正規表現の parser tree に変換することはできている。</li> | |
125 </ul> | |
122 <h1>現在していること</h1> | 126 <h1>現在していること</h1> |
123 <p>正規表現の parser tree から subset constraction に変換するプログラムを書いている途中</p> | 127 <p>正規表現の parser tree から subset constraction に変換するプログラムを書いている途中</p> |
124 <ul> | 128 <ul> |
125 <li>まずは parser tree から 決定性オートマトンへの変換</li> | 129 <li>まずは parser tree から 決定性オートマトンへの変換</li> |
126 <li>プログラム実行時に正規表現を入力すると、決定性オートマトンのリスト構造を返す</li> | 130 <li>parser tree を入力すると、リスト構造で構成された決定性オートマトンを返す</li> |
127 <li>concatenation は実装した </li> | 131 <li>concatenation は実装した </li> |
128 <li>'|'、'*' は書いている途中</li> | 132 <li>'|'、'*' は書いている途中</li> |
129 </ul> | 133 </ul> |
130 <p></p> | 134 <p></p> |
131 </div> | 135 </div> |
190 <ul> | 194 <ul> |
191 <li>BitVectorPtr->bitContainer に状態を格納する。 </li> | 195 <li>BitVectorPtr->bitContainer に状態を格納する。 </li> |
192 <li>BitVectorListPtr->next[c] は 'c' という文字が入力されたときの BitVectorListPtr の遷移先(アドレス)を格納している </li> | 196 <li>BitVectorListPtr->next[c] は 'c' という文字が入力されたときの BitVectorListPtr の遷移先(アドレス)を格納している </li> |
193 <li> </li> | 197 <li> </li> |
194 </ul> | 198 </ul> |
199 </div> | |
200 | |
201 <div id="cover"> | |
202 <h1>図解</h1> | |
203 <p>正規表現の parser tree を決定性オートマトンに変換する</p> | |
204 <p>例) 正規表現 "(a|b)c"</p> | |
205 <ul> | |
206 <object data="images/vector/automaton.svg" width="20%" type="image/svg+xml"></object><br> | |
207 </ul> | |
208 <p>この決定性オートマトンをリスト構造で表現し出力する</p> | |
209 <ul> | |
210 <object data="images/vector/BitVectorList.svg" width="40%" type="image/svg+xml"></object><br> | |
211 </ul> | |
212 </div> | |
213 | |
214 <div id="cover"> | |
215 <h1>'|' が含まれた parser tree をうまく決定性オートマトンに変換できていない問題</h1> | |
216 <p>例) 正規表現 "(a|b)c"</p> | |
217 <ul> | |
218 <object data="images/vector/automaton.svg" width="20%" type="image/svg+xml"></object><br> | |
219 </ul> | |
220 <p> 状態 0100 から 0001 に遷移先がなくなっている</p> | |
221 <ul> | |
222 <object data="images/vector/BitVectorListMiss.svg" width="20%" type="image/svg+xml"></object><br> | |
223 </ul> | |
195 </div> | 224 </div> |
196 | 225 |
197 <!-- | 226 <!-- |
198 <div id="cover"> | 227 <div id="cover"> |
199 <pre> | 228 <pre> |