earticle

영어

Given a pattern P and a compressed text Z generated from a text T , the compressed pattern matching problem is to find all occurrences of pattern P in T , using P and Z . We present an algorithm for the compressed pattern matching problem based on the Boyer-Moore-Horspool algorithm when text T is compressed by dictionary-based compression algorithms such as LZ78 or LZW compression. We also present modified algorithms changing orders of character comparisons for previous compressed pattern matching algorithms. Then we show, by various experiments, that the most effective compressed pattern matching algorithms can be different according to properties of texts such as the size of alphabets.

한국어

압축패턴매칭문제는 원본 텍스트 T 를 압축한 압축 텍스트 Z 와 찾으려는 패턴 P 가 주어질 때, T 안에 발생하는 모든 P 의 위치를 찾는 문제이다. 본 논문에서는 LZ78 알고리즘이나 LZW 알고리즘과 같이 사전을 기반으로 압축된 텍스트에 대한 Boyer-Moore-Horspool 기반의 압축패턴매칭문제를 해결하는 알고리즘을 제시한다. 또한, 기존의 압축패턴매칭 알고리즘들의 문자 비교 순서를 변경한 알고리즘들을 제시한다. 다양한 수행시간 비교 실험을 통해 알파벳의 크기와 같은 텍스트의 특성에 따라 가장 효과적인 압축패턴매칭 알고리즘이 달라질 수 있음을보인다.