著者

浦谷則好

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.30, no.9, pp.1119-1125, 1989-09-15

被引用文献数

1

---

コンピュータによる文書処理にとって文字列の照合は最も基本的な操作である.文書処理の高速化への寄与が大きいので 効率の良い照合手法が求められている.パターンが1つの場合にはBoyer-Moore法が最も効率の良い手法として知られているが この方法では複数パターンを同時に照合することはできない.複数パターンを同時に照合する方法としてはAho-Corasick法が有名であるが 効率は Boyer-Moore 法より劣る.筆者らは「パターンの後方からの照合」というBoyer-Moore法の基本的なアイデアと 「パターン照合機械による照合」というAho-Corasick法の基本的なアイデアを結合して FAST法(A Flying Algorithm for Searching Terms)を考案した.FAST法では複数のパターンを同時に効率良く照合することができる.この輪文ではFAST法の基本的な発想と具体的なアルゴリズムについて述べる.FAST法の効率についても考察し 実験による結果も示す.文字種が多いときやパターンが長いときには高い照合効率が得られることを確認した.例えば パターン長が2と短くても文字種が94のときには パターン数60以下ではAho-Corasick法より効率がまさっている.また この方法は多大なメモリを必要とする欠点を有しているが この軽減方法についてもふれた.