Earticle

초록

영어

순위다중패턴매칭문제는 길이가 인 텍스트 와 패턴들의 집합 가 주어졌을 때, 에 속한 패턴들과 순위동형인 의 모든 부분문자열들을 찾는 문제이다. 개의 연속적인 문자인 -그램, 에서 가장 짧은 패턴의 길이를 , 가장 긴 패턴의 길이를 , 모든 패턴들의 길이의 합을 이라 할 때, -그램과 계승수체계를 이용하여 시간에 순위다중패턴매칭문제를 해결하는 알고리즘이 제시되었다. 본 논문에서는 이진인코딩된 텍스트의 핑거프린트를 이용하여 시간에 순위다중패턴매칭문제를 해결하는 알고리즘을 제시한다. 또한, 시간에 탐색 과정을 수행하는 병렬 구현 방법을 제시한다. 실험 결과, 가 커질수록 제시한 알고리즘의 기존 알고리즘보다 수행시간이 느려지지만 공간사용량은 적어졌다. 제시한 병렬 구현 방법은 기존 알고리즘보다 공간효율적이면서 수행시간은 유사하다.

한국어

순위다중패턴매칭문제는 길이가 n인 텍스트 T와 패턴들의 집합 가 주어졌을 때, 에 속한 패턴들과 순위동형인 의 모든 부분문자열들을 찾는 문제이다. 개의 연속적인 문자인 -그램, 에서 가장 짧은 패턴의 길이를 , 가장 긴 패턴의 길이를 , 모든 패턴들의 길이의 합을 이라 할 때, -그램과 계승수체계를 이용하여 시간에 순위다중패턴매칭문제를 해결하는 알고리즘이 제시되었다. 본 논문에서는 이진인코딩된 텍스트의 핑거프린트를 이용하여 시간에 순위다중패턴매칭문제를 해결하는 알고리즘을 제시한다. 또한, 시간에 탐색 과정을 수행하는 병렬 구현 방법을 제시한다. 실험 결과, 가 커질수록 제시한 알고리즘의 기존 알고리즘보다 수행시간이 느려지지만 공간사용량은 적어졌다. 제시한 병렬 구현 방법은 기존 알고리즘보다 공간효율적이면서 수행시간은 유사하다.

목차

요약
Abstract
1. 서론
2. 용어 및 관련 연구
3. 이진인코딩을 이용한 순위다중패턴매칭 알고리즘
4. 실험 결과
Acknowledgements
참고문헌

키워드

저자

• 공준호 [ Junho Kong | 인하대학교 컴퓨터공학과 ]
• 김영호 [ Youngho Kim | 인하대학교 컴퓨터공학과 ]
• 심정섭 [ Jeong seop Sim | 인하대학교 컴퓨터공학과 ] 교신저자

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

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

• 간기

  격월간

• pISSN

  1975-681X

• 수록기간

  2005~2026

• 등재여부

  KCI 등재

• 십진분류

  KDC 566 DDC 004