지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers Journal of KIISE Journal of KIISE Vol.49 No.8
- 발행연도
- 2022.8
- 수록면
- 585 - 592 (8page)
- DOI
- 10.5626/JOK.2022.49.8.585
이용수
초록· 키워드
오류제보하기
두 문자열의 길이가 같고 문자열 내에서 같은 위치의 문자들의 상대적 순위가 모두 동일하면 두 문자열은 순위동형이다. 순위패턴매칭문제는 길이가 n인 문자열 T와 길이가 m인 문자열 P가 주어졌을 때, P와 순위동형인 T의 모든 부분문자열을 찾는 문제이다. 순위패턴매칭은 주가지수 분석, 멜로디 분석과 같은 시계열데이터 분석에 활용될 수 있다. 본 논문에서는 순위패턴매칭을 확장한 k-배율 순위패턴매칭문제를 정의하고, 이 문제를 O(n+mlogm) 시간에 해결하는 알고리즘을 제시한다. 또한, O(n+m) 개의 스레드를 사용하여 O(m+k) 시간에 k-배율 순위패턴매칭문제를 해결하는 병렬알고리즘을 제시한다.
목차
요약
Abstract
1. 서론
2. 관련 연구
3. k-배율 순위패턴매칭 알고리즘
4. 실험 결과
5. 결론
References
참고문헌 (15)
참고문헌 신청
J. Kim, P. Eades, R. Fleischer, S.-H. Hong, C. S. Iliopoulos, K. Park, S. J. Puglisi, and T. Tokuyama, "Order-preserving matching," Theoretical Computer Science, Vol. 525, pp. 68-79, 2014.
M. Kubica, T. Kulczyński, J. Radoszewski, W. Rytter, and T. Waleń, "A linear time algorithm for consecutive permutation pattern matching," Information Processing Letters, Vol. 113, No. 12, pp. 430-433, 2013.
D. E. Knuth, J. H. Morris, and V. R. Pratt, "Fast Pattern Matching in Strings," SIAM Journal on Computing, Vol. 6, No. 2, pp. 323-350, 1977.
S. Cho, J.C. Na, K. Park, and J.S. Sim, "A fast algorithm for order-preserving pattern matching," Information Processing Letters, Vol. 115, No. 2, pp. 397-402, 2015.
R. N. Horspool, "Practical fast searching in strings," Software: Practice and Experience, Vol. 10, No. 6, pp. 501-506, 1980.
M. Kubica, T. Kulczyński, J. Radoszewski, W. Rytter, and T. Waleń, "A linear time algorithm for consecutive permutation pattern matching," Information Processing Letters, Vol. 113, No. 12, pp. 430-433, 2013.
D. E. Knuth, J. H. Morris, and V. R. Pratt, "Fast Pattern Matching in Strings," SIAM Journal on Computing, Vol. 6, No. 2, pp. 323-350, 1977.
S. Cho, J.C. Na, K. Park, and J.S. Sim, "A fast algorithm for order-preserving pattern matching," Information Processing Letters, Vol. 115, No. 2, pp. 397-402, 2015.
R. N. Horspool, "Practical fast searching in strings," Software: Practice and Experience, Vol. 10, No. 6, pp. 501-506, 1980.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
k-배율 순위패턴매칭
한국정보과학회 학술발표논문집
2021 .12
-
순위다중패턴매칭문제에 대한 공간효율적인 해싱기반 알고리즘
정보과학회 컴퓨팅의 실제 논문지
2018 .08
-
순위패턴매칭을 위한 랜덤 순열 분포 분석
한국정보과학회 학술발표논문집
2021 .06
-
k개의 오차를 허용하는 순위 패턴 매칭
스마트미디어저널
2020 .01
-
시계열 데이터의 순열 엔트로피에 따른 순위패턴매칭 알고리즘 성능 비교
한국차세대컴퓨팅학회 논문지
2024 .04
-
Parallel Computation of Z-Function for Order-Preserving Pattern Matching and Order-Preserving Multiple Pattern Matching
Journal of KIISE
2018 .08
-
3-분할순위패턴매칭
한국정보과학회 학술발표논문집
2024 .12
-
분할순위패턴매칭
한국정보과학회 학술발표논문집
2019 .12
-
A Hashing-Based Algorithm for Order-Preserving Multiple Pattern Matching
Journal of KIISE
2016 .05
-
An Order-Preserving Pattern Matching Algorithm using Fingerprints of Two q-grams
Journal of KIISE
2018 .11
-
순위다중패턴매칭을 위한 Z-함수 병렬 계산
한국정보과학회 학술발표논문집
2016 .12
-
효율적인 해싱기반 순위다중패턴매칭 알고리즘
한국정보과학회 학술발표논문집
2017 .12
-
Parallel Computation of Order-Preserving Periods and Order-Preserving Borders of a Set of Strings
Journal of KIISE
2019 .12
-
이진인코딩을 이용한 순위다중패턴매칭 알고리즘 병렬화
한국정보과학회 학술발표논문집
2020 .07
-
텍스트의 핑거프린트를 이용한 순위다중패턴매칭 알고리즘
한국정보과학회 학술발표논문집
2018 .12
-
텍스트 이진인코딩을 이용한 순위다중패턴매칭
한국정보과학회 학술발표논문집
2020 .12
-
극소불포함순위문자열을 찾는 알고리즘
한국정보과학회 학술발표논문집
2022 .12
-
이진인코딩 기반 순위다중패턴매칭 알고리즘의 개선
한국정보과학회 학술발표논문집
2022 .12
-
순열 엔트로피에 따른 순위패턴매칭 알고리즘 수행시간 비교
한국정보과학회 학술발표논문집
2020 .12
-
Parallel Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem
Journal of KIISE
2019 .04
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0