<テクニカルレポート>
A Boyer-Moore type algorithm for compressed pattern matching

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 Recently the compressed pattern matching problem has attracted special concern, where the goal is to find a pattern in a compressed text without decompression. In previous work, we proposed an Aho-Cor...asick (AC) type algorithm for searching in text files compressed by the so-called byte pair encoding (BPE). The searching time is reduced at the same rate as the compression ratio compared with AC. In this paper, we show a Boyer-Moore (BM) type algorithm for pattern matching in BPE compressed files. Experimental results show that the algorithm runs about 1.5 ∼ 3.0 times faster than the exact match routines based on the BM algorithm in the software package Agrep, which is known as the fastest pattern matching tool.続きを見る

本文情報を非表示

trcs170 pdf 139 KB 34  
trcs170.ps gz 205 KB 34  

詳細

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