Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Multiple Pattern Matching Algorithms on Collage System

Takuya KidaContact Information, Tetsuya Matsumoto Contact Information, Masayuki Takeda Contact Information, Ayumi Shinohara Contact Information and Setsuo Arikawa Contact Information

(6)  Department of Informatics, Kyushu University 33, Fukuoka 812-8581, Japan
Abstract
Compressed pattern matching is one of the most active top- ics in string matching. The goal is to find all occurrences of a pattern in a compressed text without decompression. Various algorithms have been proposed depending on underlying compression methods in the last decade. Although some algorithms for multipattern searching on compressed text were also presented very recently, all of them are only for Lempel-Ziv family compressions. In this paper we propose two types of multipattern matching algorithms on collage system, which simulate the AC algorithm and a multipattern version of the BM algorithm, the most important algorithms for searching in uncompressed files. Collage system is a formal framework which is suitable to capture the essence of compressed pattern matching according to various dictionary based compressions. That is, we provide the model of multipattern matching algorithm for any compression method covered by the framework.

Contact Information Takuya Kida
Email: kida@i.kyushu-u.ac.jp

Contact Information Tetsuya Matsumoto
Email: tetsuya@i.kyushu-u.ac.jp

Contact Information Masayuki Takeda
Email: takeda@i.kyushu-u.ac.jp

Contact Information Ayumi Shinohara
Email: ayumi@i.kyushu-u.ac.jp

Contact Information Setsuo Arikawa
Email: arikawa@i.kyushu-u.ac.jp
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb16
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)