Mercurial > hg > Members > masakoha > seminar
annotate 2015/1113.html @ 48:1306b24dc707 default tip
fix
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 24 Feb 2016 22:23:31 +0900 (2016-02-24) |
parents | f9293af3d474 |
children |
rev | line source |
---|---|
28 | 1 <!DOCTYPE html> |
2 <html> | |
3 <head> | |
4 <meta http-equiv="content-type" content="text/html;charset=utf-8"> | |
5 <title>seminar</title> | |
6 | |
7 <!-- | |
8 Notes on CSS media types used: | |
9 | |
10 1) projection -> slideshow mode (display one slide at-a-time; hide all others) | |
11 2) screen -> outline mode (display all slides-at-once on screen) | |
12 3) print -> print (and print preview) | |
13 | |
14 Note: toggle between projection/screen (that is, slideshow/outline) mode using t-key | |
15 | |
16 Questions, comments? | |
17 - send them along to the mailinglist/forum online @ http://groups.google.com/group/webslideshow | |
18 --> | |
19 | |
20 <!-- styles --> | |
21 <style media="screen,projection"> | |
22 | |
23 html, | |
24 body, | |
25 .presentation { margin: 0; padding: 0; } | |
26 | |
27 .slide { display: none; | |
28 position: absolute; | |
29 top: 0; left: 0; | |
30 margin: 0; | |
31 border: none; | |
32 padding: 2% 4% 0% 4%; /* css note: order is => top right bottom left */ | |
33 -moz-box-sizing: border-box; | |
34 -webkit-box-sizing: border-box; | |
35 box-sizing: border-box; | |
36 width: 100%; height: 100%; /* css note: lets use border-box; no need to add padding+border to get to 100% */ | |
37 overflow-x: hidden; overflow-y: auto; | |
38 z-index: 2; | |
39 } | |
40 | |
41 .slide.current { display: block; } /* only display current slide in projection mode */ | |
42 | |
43 .slide .stepcurrent { color: black; } | |
44 .slide .step { color: silver; } /* or hide next steps e.g. .step { visibility: hidden; } */ | |
45 | |
46 .slide { | |
47 /* | |
48 background-image: -webkit-linear-gradient(top, blue, aqua, blue, aqua); | |
49 background-image: -moz-linear-gradient(top, blue, aqua, blue, aqua); | |
50 */ | |
51 } | |
52 </style> | |
53 | |
54 <style media="screen"> | |
55 .slide { border-top: 1px solid #888; } | |
56 .slide:first-child { border: none; } | |
57 </style> | |
58 | |
59 <style media="print"> | |
60 .slide { page-break-inside: avoid; } | |
61 .slide h1 { page-break-after: avoid; } | |
62 .slide ul { page-break-inside: avoid; } | |
63 </style> | |
64 | |
65 | |
66 <!-- add js lib (jquery) --> | |
67 <script src="js/jquery-1.7.min.js"></script> | |
68 | |
69 <!-- S6 JS --> | |
70 <script src="js/jquery.slideshow.js"></script> | |
71 <script src="js/jquery.slideshow.counter.js"></script> | |
72 <script src="js/jquery.slideshow.controls.js"></script> | |
73 <script> | |
74 $(document).ready( function() { | |
75 Slideshow.init(); | |
76 | |
77 // Example 2: Start Off in Outline Mode | |
78 // Slideshow.init( { mode: 'outline' } ); | |
79 | |
80 // Example 3: Use Custom Transition | |
81 // Slideshow.transition = transitionScrollUp; | |
82 // Slideshow.init(); | |
83 | |
84 // Example 4: Start Off in Autoplay Mode with Custom Transition | |
85 // Slideshow.transition = transitionScrollUp; | |
86 // Slideshow.init( { mode: 'autoplay' } ); | |
87 } ); | |
88 </script> | |
89 | |
90 </head> | |
91 <body> | |
92 | |
93 <div class="presentation"> | |
94 | |
95 <div class='slide cover'> | |
96 <table width="90%" height="90%" border="0" align="center"> | |
97 <tr> | |
98 <td><div align="center"> | |
99 <h1>Cerium 上での正規表現の実装</h1> | |
100 </div> | |
101 </td> | |
102 </tr> | |
103 <tr> | |
104 <td><div align="right"> | |
33
8a5b151da414
add 0804.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
105 <name>Masataka Kohagura 4th, August , 2015</name> |
28 | 106 </div></td> |
107 </tr> | |
108 </tr> | |
109 </table> | |
110 </div> | |
111 | |
112 <div id="cover"> | |
113 <h1>研究目的</h1> | |
29
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
114 正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。<br> |
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
115 この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。<br> |
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
116 コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。<br> |
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
117 本研究では正規表現を並列処理で実装することによってこの問題を解決し、Class NC に対応するライブラリを作成する。 |
28 | 118 </ul> |
119 </div> | |
120 | |
121 <div id="cover"> | |
33
8a5b151da414
add 0804.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
122 <h1>現在していること</h1> |
37
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
123 <p>正規表現の parser tree から subset constraction に変換するプログラムを書いている途中</p> |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
124 <ul> |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
125 <li>まずは parser tree から 決定性オートマトンへの変換</li> |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
126 <li>プログラム実行時に正規表現を入力すると、決定性オートマトンのリスト構造を返す</li> |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
127 <li>concatenation は実装した </li> |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
128 <li>'|'、'*' は書いている途中</li> |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
129 </ul> |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
130 <p></p> |
29
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
131 </div> |
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
132 |
37
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
133 <!-- |
35
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
134 <div id="cover"> |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
135 <h1>正規表現で生成された二分木を表示</h1> |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
136 <pre> |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
137 <code> |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
138 % ./regexParser -regex "test" |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
139 |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
140 t |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
141 + |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
142 s |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
143 + |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
144 e |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
145 + |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
146 t |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
147 |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
148 % ./regexParser -regex "a*bc" |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
149 |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
150 c |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
151 + |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
152 b |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
153 + |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
154 * |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
155 a |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
156 </code> |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
157 </pre> |
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
158 </div> |
37
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
159 --> |
35
18bbb4a5db60
add 0929.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
34
diff
changeset
|
160 |
30 | 161 |
34
60a678b8539c
add 0825.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
33
diff
changeset
|
162 <!-- |
30 | 163 <div id="cover"> |
164 <h1>問題点</h1> | |
31 | 165 <p>正規表現 a*b の tree 構造(本当はこうなってほしい)</p> |
30 | 166 |
31 | 167 <object data="images/vector/aastabtrue.svg" type="image/svg+xml"></object><br> |
168 <p>正規表現 a*b の tree 構造(現状)</p> | |
169 <object data="images/vector/aastabfalse.svg" type="image/svg+xml"></object><br> | |
29
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
170 </div> |
34
60a678b8539c
add 0825.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
33
diff
changeset
|
171 --> |
60a678b8539c
add 0825.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
33
diff
changeset
|
172 |
60a678b8539c
add 0825.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
33
diff
changeset
|
173 <div id="cover"> |
37
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
174 <h1>どのようなリスト構造か</h1> |
34
60a678b8539c
add 0825.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
33
diff
changeset
|
175 <pre> |
60a678b8539c
add 0825.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
33
diff
changeset
|
176 <code> |
37
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
177 typedef struct bitVector { |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
178 int arrayNum; |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
179 unsigned long *bitContainer; |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
180 }BitVector,*BitVectorPtr; |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
181 |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
182 typedef struct bitVectorList { |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
183 bitVectorList *self; |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
184 BitVectorPtr bi; |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
185 bitVectorList* initBvl; |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
186 bitVectorList* next[256]; |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
187 }BitVectorList, *BitVectorListPtr; |
34
60a678b8539c
add 0825.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
33
diff
changeset
|
188 </code> |
60a678b8539c
add 0825.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
33
diff
changeset
|
189 </pre> |
37
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
190 <ul> |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
191 <li>BitVectorPtr->bitContainer に状態を格納する。 </li> |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
192 <li>BitVectorListPtr->next[c] は 'c' という文字が入力されたときの BitVectorListPtr の遷移先(アドレス)を格納している </li> |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
193 <li> </li> |
f9293af3d474
add 1117.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
36
diff
changeset
|
194 </ul> |
34
60a678b8539c
add 0825.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
33
diff
changeset
|
195 </div> |
29
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
196 |
33
8a5b151da414
add 0804.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
197 <!-- |
34
60a678b8539c
add 0825.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
33
diff
changeset
|
198 <div id="cover"> |
31 | 199 <pre> |
200 <code> | |
201 NodePtr string() { | |
202 char c = *ptr; | |
203 NodePtr n = NULL; | |
204 if (isLiteral(c)) { | |
205 n = createNode(0,literal(),string()); | |
206 } else { | |
207 n = createNode(0,0,0); | |
208 } | |
209 return n; | |
210 } | |
211 </code> | |
212 </pre> | |
213 <p>string なのか literal なのか判断しないで createNode をしてる</p> | |
214 </div> | |
33
8a5b151da414
add 0804.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
32
diff
changeset
|
215 --> |
31 | 216 |
217 | |
29
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
218 <!-- |
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
219 <div id="cover"> |
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
220 <h1>今週のしたこと</h1> |
28 | 221 例題 : ab(ab)+ |
222 <ul> | |
223 <object data="images/vector/abab.svg" type="image/svg+xml"></object><br> | |
224 </ul> | |
225 テキストが abab の途中で分割される場合を考える | |
226 <ul> | |
227 <object data="images/vector/ababautomata.svg" type="image/svg+xml"></object><br> | |
228 </ul> | |
229 分割されたファイルの1コ前の終わりが状態(3)の場合で、分割されたファイルの先頭が b の場合状態(4)に遷移して受理される。(正規表現にマッチする) | |
230 <ul> | |
231 <object data="images/vector/ababtable.svg" type="image/svg+xml"></object><br> | |
232 </ul> | |
233 <ul> | |
234 <object data="images/vector/bitvectorTable.svg" type="image/svg+xml"></object><br> | |
235 </ul> | |
236 </div> | |
29
39f9309334f9
add 0714.html
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
28
diff
changeset
|
237 --> |
28 | 238 |
239 <!-- | |
240 <div id="cover"> | |
241 <h1>prog</h1> | |
242 <ul> | |
243 <li> | |
244 | |
245 </li> | |
246 | |
247 <pre> | |
248 <code> | |
249 typedef struct SDL_AudioSpec { | |
250 int freq; /** DSP frequency samples per second */ | |
251 Uint16 format; /** Audio data format */ | |
252 Uint8 channels; /** Number of channels: 1 mono, 2 stereo */ | |
253 Uint8 silence; /** Audio buffer silence value (calculated) */ | |
254 Uint16 samples; /** Audio buffer size in samples (power of 2) */ | |
255 Uint16 padding; /** Necessary for some compile environments */ | |
256 Uint32 size; /** Audio buffer size in bytes (calculated) */ | |
257 void (SDLCALL *callback)(void *userdata, Uint8 *stream, int len); | |
258 void *userdata; | |
259 } SDL_AudioSpec; | |
260 </code> | |
30 | 261 </pre> |
262 <img src="./images/sqrWave.png" width="50%" height=""> | |
28 | 263 </ul> |
264 </div> | |
265 | |
266 --> | |
267 | |
268 </div> <!-- presentation --> | |
269 </body> | |
270 </html> |