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