지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 정보과학회논문지 : 시스템 및 이론 정보과학회논문지 : 시스템 및 이론 제40권 제6호
- 발행연도
- 2013.12
- 수록면
- 290 - 295 (6page)
이용수
이 논문의 연구 히스토리 (2)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
근사패턴매칭은 패턴매칭을 불일치를 허용하도록 확장한 문제이며 데이터압축, 컴퓨터보안, 생물정보학 등 다양한 분야에서 연구되고 있다. 해밍거리는 길이가 n인 두 문자열 사이의 불일치 정도를 나타내기 위한 잘 알려진 거리함수로서 O(n) 시간에 계산할 수 있다. 본 논문에서 다룰 (해밍거리 기반) 근사패턴매칭은 길이 m 인 패턴 P와 길이 n 인 텍스트 T가 주어졌을 때 길이 m 인 T의 모든 부분문자열과 P사이의 해밍거리를 구하는 문제이다. 이 문제는 단순비교 기반의 알고리즘으로 O (mn) 시간에 간단히 해결할 수 있다. 알파벳의 크기를 │∑│라 할 때, Amir 등은 패턴매칭 문제를 다항식 곱셈 문제로 변환하여 O(│∑│nlogm) 시간에 근사패턴매칭 문제를 해결하는 알고리즘(이하 PM 알고리즘)을 제시하였다. 본 논문에서는 PM 알고리즘을 CUDA를 이용하여 병렬 구현한 O(│∑│logm) 시간 알고리즘(이하 PPM 알고리즘)을 제시한다. 수행시간을 측정한 결과, PPM 알고리즘은 PM 알고리즘에 비해 약 40～2,000 배 빨랐으며, 단순비교 기반 알고리즘에 비해서는 최대 7,000배 정도 빠른 성능을 보였다.
목차
요약
Abstract
1. 서론
2. 관련 연구
3. PPM 알고리즘 및 CUDA 구현
4. 실험 결과 및 분석
5. 결론 및 향후 연구
References
참고문헌 (23)
참고문헌 신청
1. [단행본] - D. Gusfield / 1997 / Algorithms on Strings, Tree, and Sequences / Cambridge University Press
2. [학술지(정기간행물)] - J. Cleary / 1984 / Data compression using adaptive coding and partial string matching / IEEE Trans. Commun. 32 : 396 ~ 402
3. [학술지(정기간행물)] - T. Luczak / 1997 / A Suboptimal Lossy Data Compression Based in Approximate Pattern Matching / IEEE Trans. Inform. Theory 43 : 439 ~ 1451
4. [학술대회논문] - S. Kumar / 1994 / A pattern-matching model for intrusion detection / Proc. of the National Computer Security Conference : 11 ~ 21
5. [학술지(정기간행물)] - L. Tan / 2005 / A High Throughput String Matching Architecture for Intrusion Detection and Prevention / ACM SIGARCH Computer Architecture News 33 (2) : 112 ~ 122
2. [학술지(정기간행물)] - J. Cleary / 1984 / Data compression using adaptive coding and partial string matching / IEEE Trans. Commun. 32 : 396 ~ 402
3. [학술지(정기간행물)] - T. Luczak / 1997 / A Suboptimal Lossy Data Compression Based in Approximate Pattern Matching / IEEE Trans. Inform. Theory 43 : 439 ~ 1451
4. [학술대회논문] - S. Kumar / 1994 / A pattern-matching model for intrusion detection / Proc. of the National Computer Security Conference : 11 ~ 21
5. [학술지(정기간행물)] - L. Tan / 2005 / A High Throughput String Matching Architecture for Intrusion Detection and Prevention / ACM SIGARCH Computer Architecture News 33 (2) : 112 ~ 122
이 논문의 저자 정보
이 논문과 함께 이용한 논문
Iz4s : 스왑아웃된 데이터를 위한 압축알고리즘
권세준
,
김진수
한국정보과학회 학술발표논문집
2013
.11
중력파와 상대성이론
김찬주
우리교육
2016
.03
RDF 문서의 중복을 고려한 효율적인 RDF 데이터 압축 기법
한지은
,
정지원
,
육미선
외 6명
한국정보과학회 학술발표논문집
2015
.12
패턴매칭에 의한 고속 호프만 알고리즘 ( A Fast Huffman Decoding Algorithm Using pattern Matching Method )
최승배
,
이문호
,
이광재
대한전자공학회 학술대회
1994
.01
고성능 허프만 코덱의 VLSI 구조
최현준
,
서영호
,
김동욱
한국정보통신학회논문지
2011
.02
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2015-560-001062708