사전기반으로 압축된 텍스트에 대한 압축패턴매칭
Compressed pattern matching for dictionary-based compressed text
0
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
압축패턴매칭문제는 원본 텍스트 를 압축한 압축 텍스트 와 찾으려는 패턴 가 주어질 때, 안에 발생하는모든 의 위치를 찾는 문제이다. 본 논문에서는 LZ78 알고리즘이나 LZW 알고리즘과 같이 사전을 기반으로 압축된 텍스트에 대한 Boyer-Moore-Horspool 기반의 압축패턴매칭문제를 해결하는 알고리즘을 제시한다. 또한, 기존의 압축패턴매칭 알고리즘들의 문자 비교 순서를 변경한 알고리즘들을 제시한다. 다양한 수행시간 비교 실험을 통해 알파벳의 크기와 같은 텍스트의 특성에 따라 가장 효과적인 압축패턴매칭 알고리즘이 달라질 수 있음을보인다.
Abstract
Given a pattern and a compressed text generated from a text , the compressed pattern matching problem is to find all occurrences of pattern in , using and . We present an algorithm for the compressed pattern matching problem based on the Boyer-Moore-Horspool algorithm when text 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.
참고문헌 (19)
- Boyer, Robert S., "A fast string searching algorithm", Communications of the ACM, 20(10), pp.762~772 (1977)
- Horspool, R. Nigel, "Practical fast searching in strings", Software: Practice and Experience, 10(6), pp.501~506 (1980)
- Knuth, Donald E, "Fast pattern matching in strings", SIAM journal on computing, 6(2), pp.323~350 (1977)
- McCreight, Edward M., "A space-economical suffix tree construction algorithm", Journal of the ACM, 23(2), pp.262~272 (1976)
- Manber, Udi, "Suffix arrays:a new method for on-line string searches, siam", Journal on Computing, 22(5), pp.935~948 (1993)
- S. B. Needleman, "A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins", J. Mol. Biol., 48(3), pp.443~453 (1970)
- Approximate String Matching in DNA Sequences, "L. L. Cheng", IEEE, 303~310 (2003)
- 나중채, "샘플링 비율 조정을 통한 Clark의 Select 함수의 효율적 구현", 한국차세대컴퓨팅학회 논문지, 5(1), pp.24~29 (2009), 한국차세대컴퓨팅학회
- T. F. Smith, "Identification of Common Molecular Subsequences", J. Mol. Biol, 147, pp.195~197 (1981)
- S. Forrest, "Self-nonself discrimination in a computer", Proc.IEEE Symp. Res. Security Privacy, pp.202~212 (1994)
- 윤현철, "동적 최장공통비상위문자열 문제 해결 알고리즘", 한국차세대컴퓨팅학회 논문지, 6(6), pp.35~43 (2010), 한국차세대컴퓨팅학회
- 심순보, "무선센서 네트워크에서의 패킷 손실 확률에 따른 압축 기법 이득 분석", 한국차세대컴퓨팅학회 논문지, 5(4), pp.56~64 (2009), 한국차세대컴퓨팅학회
- Ziv, Jacob, "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, 23(3), pp.337~343 (1977)
- Ziv, Jacob, "Compression of individual sequences via variable-rate coding", IEEE Transactions on Information Theory, 24(5), pp.530~536 (1978)
- Terry A. Welch, "A Technique for High-Performance Data Compression", Computer, 17(6), pp.8~19 (1984)
- Amir, Amihood, "Efficient Two-Dimensional Compressed Matching", Data Compression Conference, DCC’92, pp.279~288 (1992)
- Navarro Gonzalo, "LZgrep:a Boyer–Moore string matching tool for Ziv–Lempel compressed text", Software: Practice and Experience, 35(12), pp.1107~1130 (2005)
- Kida Takuya, "A unifying framework for compressed pattern matching", String Processing and Information Retrieval Symposium, 1999 and International Workshop on Groupware, pp.89~96 (1999), IEEE
- Ricardo A. Baeza-Yates, "Analysis of Boyer-Mooretype string searching algorithms", Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, pp.328~343 (1990)