| 作成者 |
|
|
|
|
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
In this paper, we address the problem of approximate string matching on compressed text. We consider this problem for a text string described in terms of collage system, which is a formal system propo...sed by Kida et al. (1999) that captures various dictionary-based compression methods. We present an algorithm that exploits bit-parallelism, assuming that our problem fits in a single machine word, e.g., $ (m − k + 1)(k + 1) leq L $, where m is the pattern length, $ k $ is the number of allowed errors, and $ L $ is the length in bits of the machine word. For a class of simple collage systems, the algorithm runs in $ O(k^2 ( left |D\right |+ mid S mid)+ km) $ time using $ O(k^2 ( left |D\right |) $ space, where $ left |D\right | $ is the size of dictionary $ D $ and $ mid S mid $ is the number of tokens in $ S $. The LZ78 and the LZW compression methods are covered by this class. Since we can regard $ n = left |D\right | + mid S mid $ as the compressed length, the time and the space complexities are $ O(k^2n + km) $ and $ O(k^2n) $, respectively.続きを見る
|
Mendeley出力
trcs174.ps
trcs174