Z-함수를 이용한 순위패턴매칭과 순위다중패턴매칭 병렬계산 


45권  8호, pp. 778-785, 8월  2018
10.5626/JOK.2018.45.8.778


PDF

  요약

순위패턴매칭문제는 길이가 각각 n, m 인 텍스트 T와 패턴 P가 주어졌을 때, P와 순위동형인 T의 모든 부분문자열의 위치를 찾는 문제이다. 순위다중패턴매칭문제는 길이가 n인 텍스트 T와 패턴 집합 W={P₁, P₂,…, Pb}가 주어졌을 때 W의 패턴들과 순위동형인 T의 모든 부분문자열의 위치를 찾는 문제이다. 본 논문에서는 Z-함수를 기반으로, 순위패턴매칭문제를 O(n+hm)개의 스레드를 사용하여 O(m) 시간에 해결하는 병렬알고리즘과 순위다중패턴매칭문제를 O(b(n+M))개의 스레드를 사용하여 O(n+M) 시간에 해결하는 병렬알고리즘을 제시한다. 이때, h는 블록의 개수이며, M은 W에서 가장 긴 패턴의 길이를 나타낸다. 실험 결과, 순위패턴매칭문제에 대한 병렬알고리즘은 순차알고리즘보다 m=10, n=1,000,000일 때 약 71.2배 빠르게 수행되었다. 또한 순위다중패턴매칭문제에 대한 병렬알고리즘은 b=1,000, m=10, n=1,000일 때 순차알고리즘보다 약 12.2배 빠르게 수행되었다.


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

[IEEE Style]

Y. Shin, Y. Kim, J. S. Sim, "Parallel Computation of Z-Function for Order-Preserving Pattern Matching and Order-Preserving Multiple Pattern Matching," Journal of KIISE, JOK, vol. 45, no. 8, pp. 778-785, 2018. DOI: 10.5626/JOK.2018.45.8.778.


[ACM Style]

Youkun Shin, Youngho Kim, and Jeong Seop Sim. 2018. Parallel Computation of Z-Function for Order-Preserving Pattern Matching and Order-Preserving Multiple Pattern Matching. Journal of KIISE, JOK, 45, 8, (2018), 778-785. DOI: 10.5626/JOK.2018.45.8.778.


[KCI Style]

신유건, 김영호, 심정섭, "Z-함수를 이용한 순위패턴매칭과 순위다중패턴매칭 병렬계산," 한국정보과학회 논문지, 제45권, 제8호, 778~785쪽, 2018. DOI: 10.5626/JOK.2018.45.8.778.


[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