정수문자열의 δ-근사주기와 γ-근사주기를 찾는 병렬알고리즘 


44권  8호, pp. 760-766, 8월  2017
10.5626/JOK.2017.44.8.760


PDF

  요약

반복적인 문자열은 데이터압축, 생물정보학 등 여러 분야에서 연구되어 왔다. 본 논문에서는 음악서열이나 주가지수와 같이 정수로 표현될 수 있는 문자열에 대한 반복에 대해 연구한다. 최근 정수문자열의 최소 δ-근사주기와 최소 γ-근사주기를 찾는 문제들이 소개되었고, 문자열의 길이가 n일 때, 두 문제를 각각 O(n²)시간에 해결하는 알고리즘들이 제시되었다. 본 논문에서는 위의 두 문제에 대해 각각 O(n²)개의 스레드를 이용하여 O(n) 시간에 해결하는 병렬알고리즘을 제시한다. 실험결과, n = 10,000일 때, 본 논문에서 제시하는 병렬알고리즘은 순차알고리즘보다 최소 δ-근사주기를 계산하는데 약 19.7배, 최소 γ-근사주기를 계산하는데 약 40.08배 빠른 수행시간을 보였다.


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

[IEEE Style]

Y. Kim and J. S. Sim, "Parallel Algorithms for Finding δ-approximate Periods and γ-approximate Periods of Strings over Integer Alphabets," Journal of KIISE, JOK, vol. 44, no. 8, pp. 760-766, 2017. DOI: 10.5626/JOK.2017.44.8.760.


[ACM Style]

Youngho Kim and Jeong Seop Sim. 2017. Parallel Algorithms for Finding δ-approximate Periods and γ-approximate Periods of Strings over Integer Alphabets. Journal of KIISE, JOK, 44, 8, (2017), 760-766. DOI: 10.5626/JOK.2017.44.8.760.


[KCI Style]

김영호, 심정섭, "정수문자열의 δ-근사주기와 γ-근사주기를 찾는 병렬알고리즘," 한국정보과학회 논문지, 제44권, 제8호, 760~766쪽, 2017. DOI: 10.5626/JOK.2017.44.8.760.


[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