Earticle

다중순위패턴매칭 문제는 주어진 패턴 집합에 속한 패턴 중 하나와 일치하는 텍스트 내의 모든 부분문자열을 찾는 문제이다. 이 문제에 대한 연구는 금융, 기후, 환경 등 다양한 분야에서 측정된 시계열 데이터 분석에 응용될 수 있 다. 본 논문에서는 다중순위패턴매칭 문제를 해결하는 알고리즘들에서 사용되는 핵심 연산들을 순위통계트리, 스플 레이트리, 세그먼트트리, 해시테이블과 같은 다양한 자료구조를 사용하여 구현한 후. 여러 시계열 데이터에 대한 실 험을 통해 시계열 데이터의 특성에 따라 어떤 자료구조 기반의 구현이 가장 적합한지를 분석한다.

The multiple order-preserving pattern matching problem is to find all substrings in a text that match any of the patterns in a given set of patterns. Research on this problem can be applied to the analysis of time series data measured in various fields such as finance, climate, and the environment. In this paper, we implement the core operations used in algorithms that solve the multiple order-preserving pattern matching problem using various data structures such as orderstatistic trees, splay trees, segment trees, and hash tables. Furthermore, through experiments on various time series datasets, we analyze which data structure-based implementation is most appropriate depending on the characteristics of the time series data.

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

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