Mercurial > hg > Members > masakoha > seminar

comparison 2015/1127.html @ 44:b796a4f4c332

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add somefiles
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Fri, 27 Nov 2015 11:59:04 +0900
parents 2015/1113.html@f9293af3d474
children 37ae3e675c32
comparison
equal deleted inserted replaced
43:123b1f3a0833 44:b796a4f4c332
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">
105 <name>Masataka Kohagura</name>
106 </div></td>
107 </tr>
108 </tr>
109 </table>
110 </div>
111
112 <div id="cover">
113 <h1>研究目的</h1>
114 正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。<br>
115 この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。<br>
116 コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。<br>
117 本研究では正規表現を並列処理で実装することによってこの問題を解決し、Class NC問題 に対応するライブラリを作成する。
118 </ul>
119 </div>
120
121 <div id="cover">
122 <h1>今日までにしたこと</h1>
123 <ul>
124 <li>とりあえず動くところまではプログラムを直した(若干バグが)</li>
125 </ul>
126 <ul>
127 <li>正規表現木のノード内に一文字のアルファベットだけしか入らなかったが、単語をいれれるようにした</li>
128 </ul>
129 <p></p>
130 </div>
131
132 <div id="cover">
133 <h1>実装すること</h1>
134 <p>正規表現の parser tree から subset constraction に変換するプログラムを書く</p>
135 <ul>
136 <li>Parser Tree のノードに word や CharClass を挿れる(今は一文字のみ)</li>
137 </ul>
138 <p>CharClass を Binary Tree で表現する</p>
139 <ul>
140 <li>正規表現に Character Class (例 : [a-z])が含まれている場合、Character Class を二分木で表現する</li>
141 </ul>
142 <object data="images/vector/CharClassTree0.svg" type="image/svg+xml" style="width:50%"></object><br>
143 </div>
144
145 <div id="cover">
146 <h1>Character Class が正規表現内に複数含まれる場合</h1>
147 <p>複数の Character Class の範囲が重複する場合</p>
148 <ul>
149 <li>Character Class Tree を Merge し再構築する</li>
150 </ul>
151 </ul>
152 <object data="images/vector/CharClassTree1.svg" type="image/svg+xml" style="width:50%"></object><br>
153 <object data="images/vector/CharClassTreeMerge.svg" type="image/svg+xml" style="width:50%"></object><br>
154 </div>
155
156 <div id="cover">
157 <h1>直しているところ</h1>
158 <ul>
159 <li>'|' が複数含まれていると正しく正規表現木が構築されない</li>
160 <li>'()'や'*'直後の単語の先頭文字が Node に含まれない</li>
161 <pre>
162 <code>
163 % ./regexParser -regex "(ac|b|aa)*ac"
164 regex : (ac|b|aa)*ac
165 ---Print Node----
166 c(6)
167 +(7)
168 *(5)
169 aa(3)
170 |(4)
171 b(2)
172 |(8)
173 ac(1)
174 -----------------
175 </code>
176 </pre>
177 </ul>
178 <ul>
179 </ul>
180 </div>
181
182 <div id="cover">
183 <h1>どのようなリスト構造か</h1>
184 <pre>
185 <code>
186 typedef struct bitVector {
187 int arrayNum;
188 unsigned long *bitContainer;
189 }BitVector,*BitVectorPtr;
190
191 typedef struct bitVectorList {
192 bitVectorList *self;
193 BitVectorPtr bi;
194 bitVectorList* initBvl;
195 bitVectorList* next[256];
196 }BitVectorList, *BitVectorListPtr;
197 </code>
198 </pre>
199 <ul>
200 <li>BitVectorPtr-&gt;bitContainer に状態を格納する。 </li>
201 <li>BitVectorListPtr-&gt;next[c] は 'c' という文字が入力されたときの BitVectorListPtr の遷移先(アドレス)を格納している </li>
202 <li> </li>
203 </ul>
204 <img src="./images/sqrWave.png" width="50%" height="">
205 </div>
206
207 <!--
208 <div id="cover">
209 <pre>
210 <code>
211 NodePtr string() {
212 char c = *ptr;
213 NodePtr n = NULL;
214 if (isLiteral(c)) {
215 n = createNode(0,literal(),string());
216 } else {
217 n = createNode(0,0,0);
218 }
219 return n;
220 }
221 </code>
222 </pre>
223 <p>string なのか literal なのか判断しないで createNode をしてる</p>
224 </div>
225 -->
226
227
228 <!--
229 <div id="cover">
230 <h1>今週のしたこと</h1>
231 例題 : ab(ab)+
232 <ul>
233 <object data="images/vector/abab.svg" type="image/svg+xml"></object><br>
234 </ul>
235 テキストが abab の途中で分割される場合を考える
236 <ul>
237 <object data="images/vector/ababautomata.svg" type="image/svg+xml"></object><br>
238 </ul>
239 分割されたファイルの1コ前の終わりが状態(3)の場合で、分割されたファイルの先頭が b の場合状態(4)に遷移して受理される。(正規表現にマッチする)
240 <ul>
241 <object data="images/vector/ababtable.svg" type="image/svg+xml"></object><br>
242 </ul>
243 <ul>
244 <object data="images/vector/bitvectorTable.svg" type="image/svg+xml"></object><br>
245 </ul>
246 </div>
247 -->
248
249 <!--
250 <div id="cover">
251 <h1>prog</h1>
252 <ul>
253 <li>
254
255 </li>
256
257 <pre>
258 <code>
259 typedef struct SDL_AudioSpec {
260 int freq; /** DSP frequency samples per second */
261 Uint16 format; /** Audio data format */
262 Uint8 channels; /** Number of channels: 1 mono, 2 stereo */
263 Uint8 silence; /** Audio buffer silence value (calculated) */
264 Uint16 samples; /** Audio buffer size in samples (power of 2) */
265 Uint16 padding; /** Necessary for some compile environments */
266 Uint32 size; /** Audio buffer size in bytes (calculated) */
267 void (SDLCALL *callback)(void *userdata, Uint8 *stream, int len);
268 void *userdata;
269 } SDL_AudioSpec;
270 </code>
271 </pre>
272 <img src="./images/sqrWave.png" width="50%" height="">
273 </ul>
274 </div>
275
276 -->
277
278 </div> <!-- presentation -->
279 </body>
280 </html>