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

• 영문명: Order preserving matching with k mismatches
• 발행기관: 한국스마트미디어학회
• 저자명: 이인복(Inbok Lee)
• 간행물 정보: 『스마트미디어저널』Vol9, No.2, 33~38쪽, 전체 6쪽
• 주제분류: 공학 > 컴퓨터학
• 파일형태: PDF
• 발행일자: 2020.06.30

국문 초록

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

영문 초록

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 on average. Experimental results show that it works efficiently with real world data.

목차

Ⅰ. 서 론

Ⅱ. 본 론

Ⅲ. 실험 결과

Ⅳ. 결 론

REFERENCES

키워드

문자열 매칭 근사 패턴 매칭 시계열 데이터 분석 string matching approximate pattern matching time series data analysis