이진인코딩을 이용한 순위다중패턴매칭 알고리즘
An Order-Preserving Multiple Pattern Matching Algorithm Using Binary Encoding
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
순위다중패턴매칭문제는 길이가 인 텍스트 와 패턴들의 집합 가 주어졌을 때, 에 속한 패턴들과 순위동형인 의 모든 부분문자열들을 찾는 문제이다. 개의 연속적인 문자인 -그램, 에서 가장 짧은 패턴의 길이를 , 가장 긴 패턴의 길이를 , 모든 패턴들의 길이의 합을 이라 할 때, -그램과 계승수체계를 이용하여 시간에 순위다중패턴매칭문제를 해결하는 알고리즘이 제시되었다. 본 논문에서는 이진인코딩된 텍스트의 핑거프린트를 이용하여 시간에 순위다중패턴매칭문제를 해결하는 알고리즘을 제시한다. 또한, 시간에 탐색 과정을 수행하는 병렬 구현 방법을 제시한다. 실험 결과, 가 커질수록 제시한 알고리즘의 기존 알고리즘보다 수행시간이 느려지지만 공간사용량은 적어졌다. 제시한 병렬 구현 방법은 기존 알고리즘보다 공간효율적이면서 수행시간은 유사하다.
Abstract
Given a text and a set of patterns , the order-preserving multiple pattern matching problem is to find all substrings of that are order-isomorphic to any pattern in . An -time algorithm using -grams and factorial number system for the problem was proposed where is the length of the shortest pattern, is the length of the longest pattern, and is the sum of lengths of all patterns in , respectively. In this paper, we propose an -time algorithm using fingerprints of binary-encoded texts. We also present a parallel implementation performing the search process in time. Experimental results show that as grows, our algorithm becomes slower than the previous algorithm, but uses less space. The proposed parallel implementation is similar in execution time to the previous algorithm and is more space-efficient.
참고문헌 (18)
- D. E. Knuth, "Fast pattern matching in strings", SIAM journal on computing, 6(2), pp.323~350 (1977)
- M. Kubica, "A linear time algorithm for consecutive permutation pattern matching", Information Processing Letters, 113, pp.430~433 (2013)
- J. Kim, "Order-preserving matching", Theoretical Computer Science, 525, pp.68~79 (2014)
- R. N. Horspool, "Practical fast searching in strings", Software : Practice and Experience, 10(6), pp.501~506 (1980)
- S. Cho, "A fast algorithm for order-preserving pattern matching", Information Processing Letters, 115, pp.397~402 (2015)
- T. Chhabra, "A filtration method for order-preserving matching", Information Processing Letters, 116, pp.71~74 (2016)
- 김영준, "이진인코딩을 이용한 Horspool 알고리즘 기반 순위패턴매칭 알고리즘", 한국정보과학회 학술발표논문집, pp.2112~2214 (2018)
- A. V. Aho, "Efficient string matching : an aid to bibliographic search", Communications of the ACM, 18(6), pp.333~340 (1975)
- M. Han, "Fast multiple order preserving matching algorithms", International Workshop on Combinatorial Algorithms, 9538, pp.248~259 (2016)
- 유광모, "텍스트의 핑거프린트를 이용한 순위다중패턴매칭 알고리즘", 한국정보과학회학술발표논문집, pp.1214~1216 (2018)
- 신유건, "Ζ-함수를 이용한 순위패턴매칭과 순위다중패턴매칭 병렬계산", 정보과학회논문지, 45(8), pp.778~785 (2018), 한국정보과학회[DOI]
- 박정훈, "순위다중패턴매칭문제에 대한 공간효율적인 해싱기반 알고리즘", 정보과학회 컴퓨팅의 실제 논문지, 24(8), pp.399~404 (2018), 한국정보과학회[DOI]
- R. M. Karp, "Efficient randomized pattern-matching algorithms", IBM journal of research and development, 31, pp.2~ (1987)
- 박경빈, "Karp-Rabin 알고리즘을 이용한 순위다중패턴매칭 알고리즘의 병렬 구현", 정보과학회논문지, 48(3), pp.249~256 (2021), 한국정보과학회[DOI]
- 허성찬, "사전기반으로 압축된 텍스트에 대한 압축패턴매칭", 한국차세대컴퓨팅학회 논문지, 12(1), pp.67~74 (2016), 한국차세대컴퓨팅학회
- 김영호, "k-오차문제를 위한 4-러시안 알고리즘의 계산 단계 병렬화", 한국차세대컴퓨팅학회 논문지, 9(2), pp.78~88 (2013), 한국차세대컴퓨팅학회
- 쟌 느앗-프엉, "Cache Conscious Parallel Pattern Matching for Aho-Corasick Algorithm on a GPU", 한국차세대컴퓨팅학회 논문지, 8(1), pp.64~75 (2012), 한국차세대컴퓨팅학회
- H. Cormen, "Introduction to Algorithms, 3rd Ed" (2009), The MIT press