2024-03-28T20:21:57Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000915202024-01-31T07:46:25Z06164:06805:06807:07146
オートマトンの圧縮配列表現と言語処理系への応用A compressed-array representation of automata and its application to programming language.jpnhttp://id.nii.ac.jp/1001/00091503/Conference Paperhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=91520&item_no=1&attribute_id=1&file_no=1Copyright (c) 2008 by the Information Processing Society of Japan筑波大学大学院システム情報工学研究科筑波大学大学院システム情報工学研究科前田, 敦司水島, 宏太決定性有限状態オートマトン(DFA)は言語処理系の字句解析器や文字列のパターンマッチ・検索アルゴリズムなどの基礎として広く用いられている。DFAをエミュレートする速度を落とすことなくメモリ効率よく表現する手法もさまざまに工夫されてきた。本稿では、DFAの状態遷移表を、複数の配列を用いて効率よく表現する手法のバリエーションを紹介する。この手法は、trieを2つの一次元配列に圧縮して格納する青江のダブル配列と似て、状態遷移表の遷移リンクを2つの一次元配列に圧縮して格納する。ただし、ダブル配列とは違って木構造だけでなく、DFAの遷移を表現するのに必要な一般のグラフ構造も表現できる。筆者らはこの手法を、ネットワークを経由する攻撃を検知する侵入検知システム(NIDS)のパターン検索エンジンに用いるために開発したが、本稿では同様の手法を言語処理系の字句解析器に応用し、その効果を実験に用いて確かめた。実験の結果、提案手法は、従来の圧縮手法と同等のメモリ効率を持ちながら、より高速であった。Deterministic finite automata (DFA) serves as a basic tool for wide variety of computer algorithms including lexical analysis of programming languages and string pattern matching/searching. Various methods are proposed for representing DFA compactly, without sacrificing emulation speed.In this paper, we describe a variation of multi-array representation of DFA transition tables. Like Aoe’s double-array method, which stores a trie into two linear arrays, our method stores transition link of DFA into two linear arrays. Unlike double-array method, however, our method can express general graph structures, which is required to express DFA transitions. Authors developed this method primary for use in pattern matching engines in network intrusion detection system (NIDS). In this paper, we applied the method to lexical analyzers and performed some performance measurement.Experiments shows that our method has spece efficiency comparative to existing methods,while achieving superior performance.第49回プログラミング・シンポジウム予稿集200849542008-01-082013-04-05