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 기반의 압축패턴매칭문제를 해결하는 알고리즘을 제시한다. 또한, 기존의 압축패턴매칭 알고리즘들의 문자 비교 순서를 변경한 알고리즘들을 제시한다. 다양한 수행시간 비교 실험을 통해 알파벳의 크기와 같은 텍스트의 특성에 따라 가장 효과적인 압축패턴매칭 알고리즘이 달라질 수 있음을보인다.

목차

요약
 Abstract
 1. 서론
 2. 관련 연구
  2.1 LZ78, LZW알고리즘
  2.2 Boyer-Moore 알고리즘 기반의 압축패턴매칭 알고리즘
 3. 압축패턴매칭 알고리즘
 4. 실험 결과 및 분석
 5. 결론
 참고문헌

키워드

저자

• 허성찬 [ Sung Chan Hur | 인하대학교 컴퓨터정보공학과 ]
• 조석현 [ Sukhyeun Cho | 인하대학교 컴퓨터정보공학과 ]
• 심정섭 [ Jeong Seop Sim | 인하대학교 컴퓨터정보공학과 ] 교신저자

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국차세대컴퓨팅학회 논문지 [THE JOURNAL OF KOREAN INSTITUTE OF NEXT GENERATION COMPUTING]

• 간기

  격월간

• pISSN

  1975-681X

• 수록기간

  2005~2026

• 등재여부

  KCI 등재

• 십진분류

  KDC 566 DDC 004