Mercurial > hg > Members > masakoha > masa

comparison May-2013/21th.html @ 0:c9b2998eb516

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add slide
author Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
date Tue, 10 Dec 2013 15:25:07 +0900
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:c9b2998eb516
1 <!DOCTYPE html>
2
3 <!--
4 Google HTML5 slide template
5
6 Authors: Luke Mahé (code)
7 Marcin Wichary (code and design)
8
9 Dominic Mazzoni (browser compatibility)
10 Charles Chen (ChromeVox support)
11
12 URL: http://code.google.com/p/html5slides/
13 -->
14
15 <html>
16 <head>
17 <title>2013-05-21</title>
18
19 <meta charset='utf-8'>
20 <script
21 src='http://html5slides.googlecode.com/svn/trunk/slides.js'></script>
22 </head>
23
24 <style>
25 /* Your individual styles here, or just use inline styles if that’s
26 what you want. */
27 .slides article { background-image: none !important; background-color: white; }
28
29
30 </style>
31
32 <body style='display: none'>
33
34 <section class='slides layout-regular template-default'>
35
36 <!-- Your slides (<article>s) go here. Delete or comment out the
37 slides below.-->
38
39 <article>
40 <h1>
41 Ceriumによる
42 <br>
43 正規表現マッチャの実装
44 </h1>
45 <p>
46 Masataka Kohagura
47 <br>
48 14th May , 2013
49 </p>
50 </article>
51
52 <article>
53 <h3>
54 研究目的
55 </h3>
56 <p>
57 本研究室では、Cell用に作られたCeriumにて並列プログラミングを行なっている。様々な例題を実装することにより、どのような問題でも並列処理ができることを証明する。
58 </p>
59 <p>
60 現在は文字列サーチを実装している段階で、ボイヤームーア法を実装している。
61 セミグループという、分割したファイルに対して並列処理をさせるような手法によって、既存の文字列サーチと処理速度を比較し、どれだけ速くなるのかを測定する。
62 </p>
63 </article>
64
65 <article class='smaller'>
66 <h3>
67 ボイヤームーア法とは(1)
68 </h3>
69 <p>
70 </p>
71 <div align="center">
72 <IMG SRC="BM1.jpg" ALT="BM1">
73 </div>
74 <p>
75 検索したい文字列(pattern data)の長さをmとする。
76 </p>
77 <p>
78 pattarn dataとtext dataを、pattern dataの末尾から比較を行なっていく。<br>比較したtext dataの文字列がpattern dataの要素に含まれていない場合は、pattern dataをm個ずらし、再比較を行う。
79 </p>
80 </article>
81
82
83 <article class='smaller'>
84 <h3>
85 ボイヤームーア法とは(2)
86 </h3>
87 <p>
88 </p>
89 <div align="center">
90 <IMG SRC="BM2.jpg" ALT="BM1">
91 </div>
92 <p>
93 比較したtext dataの文字がpattern dataの要素に含まれている場合は、pattern dataの末尾からその要素がどれだけ離れているかで決定される。この図であれば、末尾から2個離れているので、pattern dataを2個ずらし、最比較。
94 </p>
95 </article>
96
97 <article class='smaller'>
98 <h3>
99 BM法をCで実装
100 </h3>
101 <section>
102 <pre>
103 int BM_method(char *text,char *pattern,unsigned long long *match_string){
104 int skip[256];
105 int i,j,text_len,pattern_len;
106 int k = 0;
107 text_len = strlen(text);
108 pattern_len = strlen(pattern);
109
110 for (i = 0; i < 256; ++i){
111 skip[i] = pattern_len;
112 }
113 for (i = 0; i < pattern_len-1 ; ++i){
114 skip[(int)pattern[i]] = pattern_len - i - 1;
115 }
116
117 i = pattern_len - 1;
118 while ( i < text_len){
119 j = pattern_len - 1;
120 while (text[i] == pattern[j]){
121 if (j == 0){
122 match_string[k] = text[i];
123 k++;
124 }
125 --i,--j;
126 }
127 i = i + max((int)skip[(int)text[i]],pattern_len - j);
128 }
129 return -1;
130 }
131 </pre>
132 </article>
133
134 <article class>
135 <h3>
136 分割時の処理について
137 </h3>
138 <p>現在実装している処理</p>
139 <div align="center">
140 <IMG SRC="search_idata.jpg" ALT="sid">
141 </div>
142 <p>
143 i_dataを1文字だけ多く取ってきて、abが分割されたときでも結果が返ってきてくれるように設定している。
144 </p>
145 </article>
146
147 <article class>
148 <h3>
149 現在の問題点
150 </h3>
151 <p>
152 分割回りで結果が返ってこない。(上手く処理されていない）
153 </p>
154 <p>
155 taskが2個以上になるとき、cpuの個数を2個以上に設定しないと結果が返ってこない。
156 </p>
157 </article>
158
159 </body>
160 </html>