2개의 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭알고리즘 


45권  11호, pp. 1111-1116, 11월  2018
10.5626/JOK.2018.45.11.1111


PDF

  요약

순위패턴매칭문제는 길이가 각각 n, m인 텍스트 T와 패턴 P가 주어졌을 때, P와 순위가 같은 T의 모든 부분문자열을 찾는 문제이다. 최근 q-그램의 핑거프린트를 이용한 O(nm + nqlogq +q!) 시간 순위패턴매칭 알고리즘이 제시되었다. 본 논문에서는 2개의 q-그램에 대한 핑거프린트를 이용하여 수행시간을 개선한 순위패턴매칭 알고리즘을 제시한다. 실험 결과, 본 논문에서 제시하는 알고리즘은 기존의 알고리즘보다 무작위로 생성된 T(n = 5,000,000)와 P(m = 5,10,15)에 대해 최대 약 12% 빠르게 수행된다. 또한 다우존스지수 데이터를 이용한 T(n = 34,658)와 T에서 무작위로 추출한 P(m = 5,10,15)에 대해 최대 약 10% 빠르게 수행된다.


  통계
2022년 11월부터 누적 집계
동일한 세션일 때 여러 번 접속해도 한 번만 카운트됩니다. 그래프 위에 마우스를 올리면 자세한 수치를 확인하실 수 있습니다.
  논문 참조

[IEEE Style]

G. Yoo, Y. Kim, J. S. Sim, "An Order-Preserving Pattern Matching Algorithm using Fingerprints of Two q-grams," Journal of KIISE, JOK, vol. 45, no. 11, pp. 1111-1116, 2018. DOI: 10.5626/JOK.2018.45.11.1111.


[ACM Style]

Gwangmo Yoo, Youngho Kim, and Jeong Seop Sim. 2018. An Order-Preserving Pattern Matching Algorithm using Fingerprints of Two q-grams. Journal of KIISE, JOK, 45, 11, (2018), 1111-1116. DOI: 10.5626/JOK.2018.45.11.1111.


[KCI Style]

유광모, 김영호, 심정섭, "2개의 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭알고리즘," 한국정보과학회 논문지, 제45권, 제11호, 1111~1116쪽, 2018. DOI: 10.5626/JOK.2018.45.11.1111.


[Endnote/Zotero/Mendeley (RIS)]  Download


[BibTeX]  Download



Search




Journal of KIISE

  • ISSN : 2383-630X(Print)
  • ISSN : 2383-6296(Electronic)
  • KCI Accredited Journal

사무국

  • Tel. +82-2-588-9240
  • Fax. +82-2-521-1352
  • E-mail. chwoo@kiise.or.kr