<テクニカルレポート>
A Fast Matching Algorithm for Patterns with Pictures

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 The pattern matching problem is to find a13 occurrences of patterns in a text string. In this paper, we consider patterns with pictures. For example, let A be a picture for a, b, . . . z, and N for 0,...1, . . ., 9, Then we consider patterns such as abNN, a7N N N N A., . .. etc. For multiple string patterns, the Ahocorasick algorithm, which uses a finite state pattern matching machine, is widely known to be quite efficient, As a natural extension of this algorithm, we present an efficient matching algorithm for multiple patterns with pictures. A pattern matching machine can be built easily and quickly, and then it runs in linear time proportional to the text length as the Aho-Corasick achieves. Moreover, we give a validity proof of our algorithm.続きを見る

本文情報を非表示

rifis-tr-11 pdf 1.51 MB 129  

詳細

レコードID
査読有無
関連情報
タイプ
登録日 2009.04.22
更新日 2017.01.20