<343989F D834F C2E696E6464>

Size: px

Start display at page:

Download "<343989F D834F C2E696E6464>"

うのすけおえづか
6 years ago
Views:

1 (DFA) DFA DFA tre DFA (NIDS) A compressed-array representaton of automata and ts applcaton to programmng language. MAEDA Atus and Kouta Mzushma Determnstc fnte automata (DFA) serves as a basc tool for wde varety of computer algorthms ncludng lexcal analyss of programmng languages and strng pattern matchng/searchng. Varous methods are proposed for representng DFA compactly, wthout sacrfcng emulaton speed. In ths paper, we descrbe a varaton of mult-array representaton of DFA transton tables. Lke Aoe s double-array method, whch stores a tre nto two lnear arrays, our method stores transton lnk of DFA nto two lnear arrays. Unlke double-array method, however, our method can express general graph structures, whch s requred to express DFA transtons. Authors developed ths method prmary for use n pattern matchng engnes n network ntruson detecton system (NIDS). In ths paper, we appled the method to lexcal analyzers and performed some performance measurement. Experments shows that our method has spece effcency comparatve to exstng methods, whle achevng superor performance. 1. (DFA) 4) DFA DFA DFA 7) 1) Graduate School of Systems and Informaton Engneerng, Unversty of Tsukuba DFA lex 5) flex 6) tre 3) tre 49

2 2. tre 1 1 f face fat h f a c e h t ( ) tre 2.1 Johnson tre Johnson 7) yacc lex 3 tre 2 next[k] next base[m] next check[k] 3 next check next 3 K tre tre tre 2 ( 2) base next node alphabet a b c d e f Tre 2 2 table[m][n](m N ) j table[][j] table[][j] check Johnson ( ) next[base[]] next[base[] + N - 1] 2 table[][j] next[base[]+j] check[base[]+j] 2.2 2) Johnson 2 next base Johnson next[n ]= n ( 50

3 0 ) >0 1 base[] b next base 4 next check n next[n ]+j b n n 4 table next n j next[n ]+j check[next[n ]+j] n 1 Johnson 2 dentfy n Johnson 3. DFA 3.1 Johnson DFA δ(s, a) 2 ( ) j δ(, j) 2 table[][j] DFA table [a-z] [a-z0-9] s 0 s 1 5 DFA (1) DFA 2) next base s 0 [a-z] [a-z0-9] s 1 Σ-[a-z0-9] Σ-[a-z] J Σ 6 jam (jam ) 5 [a z][a z0 9] DFA jam 6 Σ DFA jam J (2) DFA 6 s 0 s 1 [0 9] 2 2 (3) DFA 6 DFA a z Johnson base[m], next[k], check[k] def[m] def[] def[] next 2.1 flex accept[m] 7 Johnson DFA Flex -C 51

4 = start_state; do { j = *nput_ptr++; f (accept[]) { base[] b next ( 8) n b dentfy j last_pos = nput_ptr - 1; check[b + j] last_accept = ; next[b + j] b } whle (check[base[] + j]!= ) = def[]; = next[base[] + j]; } whle (!= JAMSTATE); Johnson table next 7 Johnson DFA next 3.2 Equvalent character class next Flex DFA (equvalent character class; EC) 0 ec ec[n] 2 table N EC Johnson 7 j = *nput ptr++; j = ec[*nput ptr++]; next check K Johnson check b j check EC meta EC flex (meta EC) meta EC meta b_ b_ = = start_state; do do { { j j = = *nput_ptr++; f f (next[b_ - -1]) 1]) { { last_pos = = nput_ptr - -1; 1; last_accept = = ; ; 4. } } whle (check[b_ + + j] j]!=!= j) j) b_ b_ = = check[b_ - -1]; 1]; Johnson base = = next[b_ + + j]; j]; } } whle (b_ (b_!=!= JAMSTATE); next[n ]= n 9 DFA DFA 9 Johnson next check b next[b + j] j 8 j accept[] def[] next[b - 1] check[b - 1] accept def accept def accept def next check Flex -CF 52

5 -CF jam ( ) meta EC 5. -Cn( ), -Cf ( 2 ) -CF(full speed table ) 4 -Ce(EC ) -Cm(meta EC ) -Ca ( 4 ) Flex 1 (B) (ms) (MB/s) -Cnem ,6 -Cem Cne Ce Cnm Cm C Cn Cfe CFe CF Cf CFa Cfa Athlon 64 X (2.4GHz), RAM 1.0GB, Deban/GNU Lnux 4.0, (amd64), gcc gcc -g -O2 Flex C ( 101, DFA 329) ruby ( 52MB) 8 (flex -8 ) (lex.yy.c) text bss 60 data 4 24 Flex -C(Johnson ), slowest & smallest -Cem -Cm -Ce -C -C{f,F}e -C{f,F} -C{f,F}a fastest & largest -Cnem, -Cne, -Cnm, -Cn x 6. (-Cn) 4 Johnson Johnson 3 -Cn -Cfe 1/2 Johnson 7. DFA DFA 53

6 9e+07 8e+07 F f Fa fa Speed(bytes/sec) 7e+07 6e+07 5e+07 4e+07 3e+07 n fe nm Fe nem ne m (none) e em 2e+07 1e Table Sze(bytes) 10 8) Johnson IT ( 456) ( ) 1) Aho, A.V. and Corasck, M.J.: Effcent strng matchng: an ad to bblographc search, Communcatons of the ACM, Vol. 18, No. 6, pp (1975). 2) Aoe, J.-I., Mormoto, K. and Sato, T.: An Effcent Implementaton of Tre Structures, Software Practce and Experence, Vol.22, No.9, pp (1992). 3) Fredkn, E.: Tre Memory, Communcatons of the ACM, Vol. 3, No. 9, pp (1960). 4) Hopcroft, J. E., Ullman, J. D. and Motowan, R.:, (2003). 5) Johnson, W. L., Porter, J. H., Ackley, S. I. and Ross, D. T.: Automatc generaton of effcent lexcal processors usng fnte state technques, Commun. ACM, Vol. 11, No. 12, pp (1968). 6) Paxson, V.: Flex a fast scanner generator, Free Software Foundaton (1990). 7) Ram,M.S.,Seth,R.,Ullman,J.D.andAho, A. V.: Complers: Prncples, Technques and Tools, Addson-Wesley, second edton (2006). 8),,, :, CPSY, Vol. 106, No. 436, pp (2006). 54

IPSJ SIG Techncal Report 2. RangeBased RangeFree. 2.1 Rangebased RangeBased TDOA(Tme Dfference Of Arrval) TOA(Tme Of Arrval) TDOA TDOA Actve Bat 2) Cr

IPSJ SIG Techncal Report 2. RangeBased RangeFree. 2.1 Rangebased RangeBased TDOA(Tme Dfference Of Arrval) TOA(Tme Of Arrval) TDOA TDOA Actve Bat 2) Cr IPSJ SIG Techncal Report 1 2 2 (SOM, Self Organzng Maps) 7). Self-Organzng Localzaton for Wreless Sensor Networks on Ansotropc Topology Yuto Takashma, 1 Naotosh Adach 2 and Yasuhsa Takzawa 2 On wreless