[논문]k개의 오차를 허용하는 순위 패턴 매칭

이인복

doi:10.30693/smj.2020.9.2.33

[국내논문] k개의 오차를 허용하는 순위 패턴 매칭
Order preserving matching with k mismatches 원문보기

스마트미디어저널 = Smart media journal, v.9 no.2, 2020년, pp.33 - 38

초록
AI-Helper

순위 패턴 매칭 문제는 패턴과 텍스트가 주어졌을 때, 텍스트의 부분 문자열 중 패턴과 순위 동형을 만족하는 것들을 찾는 문제이다. 이 논문에서는 순위 패턴 매칭에 k개의 오차를 허용하는 문제를 푸는 알고리즘을 제안한다. 제안하는 알고리즘은 기존의 알고리즘에 비하여 간단하고 구현이 쉬우며, 평균적인 경우 선형 시간 복잡도를 가진다. 또한 실험을 통해서, 제안된 알고리즘이 현실적인 데이터에 대해서 효율적으로 동작함을 보인다.

Abstract ▼ AI-Helper

Order preserving matching refers to the problem of reporting substrings of a given text where there exists order isomorphism with the pattern. In this paper, we propose a new algorithm based on filtering and evaluation. The proposed algorithm is simple and easy to implement, and runs in linear time ...

Keyword

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 k개의 오차를 허용하는 순위 패턴 매칭에서 길이 m인 패턴을 k+1개의 동일한 길이의 조각으로 나누어, 각 조각의 최소값/최대값 위치를 비교하여 여과를 수행하여 일부 검증을 생략하여 시간 복잡도를 줄이고, 보다 이해와 구현이 쉬운 방법을 제시하였다. 실험 결과에서는 패턴이 매우 짧고 k값이 큰 경우를 제외하고는 제안하는 알고리즘은 패턴 길이가 증가할수록 수행시간이 급격히 감소함을 보인다.

제안 방법

또한 실제 데이터를 통한 실험으로 알고리즘의 성능 평가를 시행한 결과가 없다. 본 논문에서는 따라서 실제 데이터에 적용할 수 있으며, [10]보다 쉽게 구현할 수 있으며 높은 성능을 보이는 알고리즘을 제시하고, 실험을 통하여 효율성을 검증한다.

대상 데이터

40GHz에 16GB RAM의 컴퓨터에서 C++로 구현하 였다. 여과 단계 없이 검증 단계만 실행한 브루트 포스, 슬라이딩 윈도우, 양방향 큐를 이용한 세 가지 경우를 길이10⁶의 랜덤 텍스트에서 실험하였다. 표 1은 k=1, 표 2는 k=2, 표 3는 k=3인 경우에 대한 실행 시간을 나타낸 표이다.

이론/모형

Gawrychowski 등은 [10]에서 처음으로 k개의 오차를 허용 하는 순위 패턴 매칭 문제에 대한 해법을 제시했다. 이 방법은 여과와 검증 과정으로 이루어지는데, 여과 과정은 vEB (van Emde Boas) 트리를 이용하여 각 문자와 그 문자의 알파벳 순서로 직전인 문자의 인덱스의 위치의 차이를 저장한 시그니처를 만든다. 부분 문자열 \(T\)[\(i\),\(i\) + m-1]와 P가 k개 이하의 오차가 있다면, \(T\)[\(i\),\(i\) + m-1]와 P의 시그니처는 3k이하의 오차가 있다는 성질을 이용한다.
먼저 검증 과정은 [10]과 같이 최장 증가 부분 서열 (Longest Increasing Subsequence, LIS) 기반 알고리즘으로 수행한다. 패턴 P에서 \(π\)를 구하려면 P의 글자들을 모두 정렬해야 하므로 O(mlogm)의 시간이 걸린다.

성능/효과

이론적으로는 슬라이딩 윈도우를 사용한 경우가 양방향 큐를이용한 경우보다 시간 복잡도가 좋지 않지만, 실제 실험 결과에서는 더 좋은 성능을 보였다. 그 원인은 랜덤 데이터에서 최악의 경우에 해당하는 경우의 수가 적고, 짧은 길이의 패턴에 대해 양방향 큐를 유지하는 부담이 크기 때문으로 보인다.
본 논문에서는 k개의 오차를 허용하는 순위 패턴 매칭에서 길이 m인 패턴을 k+1개의 동일한 길이의 조각으로 나누어, 각 조각의 최소값/최대값 위치를 비교하여 여과를 수행하여 일부 검증을 생략하여 시간 복잡도를 줄이고, 보다 이해와 구현이 쉬운 방법을 제시하였다. 실험 결과에서는 패턴이 매우 짧고 k값이 큰 경우를 제외하고는 제안하는 알고리즘은 패턴 길이가 증가할수록 수행시간이 급격히 감소함을 보인다.

후속연구

향후 연구를 통해 보다 다양한 형태의 여과 알고리즘을 생각해볼 수 있겠고, 여과 알고리즘의 조합을 통하여 더 효율적인 수행 시간을 보일 수도 있을 것으로 생각된다. 또한 다중 패턴 매칭에 대해서도 고려해볼 수 있겠다.

질의응답

핵심어	질문	논문에서 추출한 답변
	순위 패턴 매칭 문제란?	순위 패턴 매칭 문제는 패턴과 텍스트가 주어졌을 때, 텍스트의 부분 문자열 중 패턴과 순위 동형을 만족하는 것들을 찾는 문제이다. 이 논문에서는 순위 패턴 매칭에 k개의 오차를 허용하는 문제를 푸는 알고리즘을 제안한다.
	본 연구에서 사용한 여과 방법은 무엇인가?	최대값/최소값을 구하는 것은 RMQ (Range Minimum Query)를 이용한다. 본 연구에서는 두 가지 방법을 사용하였는 데, 하나는 평균적으로 O(n), 최악의 경우 O(nl) 시간이 걸리는 간단한 방법이며, 다른 하나는 최악의 경우에도 O(n) 을 보장하는 양방향 큐를 이용한 방법이다. 본 논문에서 제시하는 여과 방법의 근거는, 주어진 문자열을 k+1개의 동일한 크기로 나누었다면, 가능한 오류의 개수가 k이기 때문에 비둘기집 원리에 의해서 최소한 한 개의 조각은 오류를 포함하지 않기 때문이다.
	본 연구에서 제공하는 여과 방법을 사용하여 얻을 수 있는 효과는 무엇인가?	길이 m인 문자열의 LIS를 구하는데 O(mlogm)시간이 필요하기 때문에, 이 방법을 T의 길이 m인 모든 부분 문자열에 대해 적용하면 O(nmlogm)시간이 걸린다. 본 논문에서 제시하는 여과 방법을 사용하면, 생략가능한 시작점을 찾아 제거하고 그렇지 않은 부분에서만 검증을 수행함으로써, 평균 수행 시간을 단축시킨다.

참고문헌 (12)

Inbok Lee, "Mining Regular Expression Rules based on q-grams," Smart Media Journal, vol. 8, no.3, pp. 17-22, 2019.

원문보기 상세보기
허만우, 박기철, 홍지만, "사물인터넷 게이트웨이 보안을 위한 사용자 민감 데이터 분류," 스마트미디어저널, 제8권 제4호, 17-24쪽, 2019년 12월

원문보기 상세보기
권혁록, 홍택은, 김판구, "AMI시스템에서 유사도를 활용한 누락데이터 보정 방법," 스마트미디어저널, 제8권, 제4호, 80-84쪽, 2019년 12월

원문보기 상세보기
J. Kim, P. Eades, R. Fleischer, S.-H. Hong, C. S. Iliopoulos, K. Park, S. J. Puglisi, T. Tokuyama, "Order-preserving matching," Theoretical Computer Science, vol. 525, pp. 68-79, 2014.

상세보기
M. Kubica, T. Kulczynski, J. Radoszewski, W. Rytter, T. Walen, "A linear time algorithm for consecutive permutation pattern matching," Information Processing Letters, vol. 113, no. 12, pp. 430-433, 2013.

상세보기
S. Cho, J. C. Na, K. Park, J. S. Sim, "A fast algorithm for order-preserving pattern matching," Information Processing Letters, vol. 115, pp. 397-402, 2015.

상세보기
T. Nakamura, S. Inenaga, H. Bannai, M. Takeda, "Order preserving pattern matching on trees and DAGs," Proc of SPIRE, pp. 271-277, 2017.
T. Chhabra, Jorma Tarhio, "A filtration method for order-preserving matching," Information Processing Letters, vol. 116, pp. 71-74, 2016.

상세보기
J. C. Na, I. Lee, "A Simple Heuristic for Order-Preserving Matching," IEICE Transaction on Information and Systems, vol. 102, no. D(3), pp. 502-504, 2019.
P. Gawrychowski, P. Uznanski, "Order-preserving pattern matching with k mismatches," Theoretical Computer Science, vol. 638, pp. 136-144, 2016.

상세보기
T. Chhabra, E. Giaquinta, J. Tarhio, "Filtration Algorithms for Approximate Order-Preserving Matching," Proc of SPIRE, pp. 177-187, 2015.
G. Jacobson, K.-P. Vo, "Heaviest increasing/common subsequence problems," Proc of CPM, pp. 52-66, 1992.

저자의 다른 논문 :

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증