본문 바로가기
KERD
논문KCI 등재

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

Order preserving matching with k mismatches

이인복
(사)한국스마트미디어학회 (Korean Institute of Smart Media)|2020.06|스마트미디어저널 (Smart Media Journal)|제9권 제2호|pp. 33-38|DOI http://dx.doi.org/10.30693/smj.2020.9.2.33

0

조회

0

다운로드

3

인용

0

참고문헌

키워드

문자열 매칭string matching근사 패턴 매칭시계열 데이터 분석approximate pattern matchingtime series data analysis
주제분류컴퓨터학

초록

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

Abstract

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.

참고문헌 (12)

  1. 이인복, "Mining Regular Expression Rules based on q-grams", 스마트미디어저널, 8(3), pp.17~22 (2019), (사)한국스마트미디어학회[DOI]
  2. 허만우, "사물인터넷 게이트웨이 보안을 위한 사용자 민감 데이터 분류", 스마트미디어저널, 8(4), pp.17~24 (2019), (사)한국스마트미디어학회[DOI]
  3. 권혁록, "AMI시스템에서 유사도를 활용한 누락데이터 보정 방법", 스마트미디어저널, 8(4), pp.80~84 (2019), (사)한국스마트미디어학회[DOI]
  4. J. Kim, "Order-preserving matching", Theoretical Computer Science, 525, pp.68~79 (2014)
  5. M. Kubica, "A linear time algorithm for consecutive permutation pattern matching", Information Processing Letters, 113(12), pp.430~433 (2013)
  6. S. Cho, "A fast algorithm for order-preserving pattern matching", Information Processing Letters, 115, pp.397~402 (2015)
  7. T. Nakamura, "Order preserving pattern matching on trees and DAGs", Proc of SPIRE, pp.271~277 (2017)
  8. T. Chhabra, "A filtration method for order-preserving matching", Information Processing Letters, 116, pp.71~74 (2016)
  9. J. C. Na, "A Simple Heuristic for Order-Preserving Matching", IEICE Transaction on Information and Systems, 102(D(3)), pp.502~504 (2019)
  10. P. Gawrychowski, "Order-preserving pattern matching with k mismatches", Theoretical Computer Science, 638, pp.136~144 (2016)
  11. T. Chhabra, "Filtration Algorithms for Approximate Order-Preserving Matching", Proc of SPIRE, pp.177~187 (2015)
  12. G. Jacobson, "Heaviest increasing", common subsequence problems, 1992, 52~66

관련 논문AI추천

이진인코딩을 이용한 순위다중패턴매칭 알고리즘공준호, 김영호, 심정섭한국차세대컴퓨팅학회 · 한국차세대컴퓨팅학회 논문지2022 · 제18권 제6호시계열 데이터의 순열 엔트로피에 따른 순위패턴매칭 알고리즘 성능 비교심정섭, 이상준한국차세대컴퓨팅학회 · 한국차세대컴퓨팅학회 논문지2024 · 제20권 제2호다중순위패턴매칭을 위한 자료구조 비교 분석강석철, 심정섭, 안상훈한국차세대컴퓨팅학회 · 한국차세대컴퓨팅학회 논문지2025 · 제21권 제5호사전기반으로 압축된 텍스트에 대한 압축패턴매칭심정섭, 조석현, 허성찬한국차세대컴퓨팅학회 · 한국차세대컴퓨팅학회 논문지2016 · 제12권 제1호k-오차문제를 위한 4-러시안 알고리즘의 계산 단계 병렬화김영호, 김진욱, 심정섭한국차세대컴퓨팅학회 · 한국차세대컴퓨팅학회 논문지2013 · 제9권 제2호극대 증가 부분서열을 찾는 선형 알고리즘나중채(사)한국스마트미디어학회 · 스마트미디어저널2023 · 제12권 제6호

이 간행물의 다른 논문 (11건)

오브젝트 중심점-마스크를 사용한 instance segmentation김형석, 이종혁pp. 9-15시뮬레이션 기반 5G 통신 환경에서 성능향상을 위한 스몰셀 기술 적용 분석김윤환, 김태연, 배상현, 이대영pp. 16-21One Step Measurements of hippocampal Pure Volumes from MRI Data Using an Ensemble Model of 3-D Convolutional Neural NetworkAbol Basher, 정호엽, Samsuddin Ahmedpp. 22-32A Survey on Face-based Cryptographic Key Generation최덕재, Thao Dangpp. 39-50전력 비즈니스 플랫폼 기반의 전력 도메인 온톨로지 구축 및 추론 방법유경호, 김판구, 홍택은pp. 51-62
원문 보기