지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 정보과학회논문지 : 시스템 및 이론 정보과학회논문지 : 시스템 및 이론 제41권 제2호
- 발행연도
- 2014.4
- 수록면
- 87 - 92 (6page)
이용수
초록· 키워드
오류제보하기
알파벳 Σ의 문자들로 구성된 길이가 각각 m, n 인 두 문자열의 편집거리는 4-러시안 알고리즘을 이용하여 계산할 수 있다. 편집거리를 계산하기 위한 4-러시안 알고리즘은 두 단계로 구성된다. 첫번째 단계인 전처리단계는 전처리를 위해 사용되는 문자열들의 길이가 t 일 때, Ο((3｜Σ｜)<SUP>2t</SUP>t²시간과 Ο((3｜Σ｜)<SUP>2t</SUP>t) 공간을 이용하여 수행된다. 두 번째 단계인 계산단계는 Ο(mn/t)시간과 Ο((3｜Σ｜)<SUP>2t</SUP>t+mn)는 공간을 이용하여 수행된다. 본 논문에서는 4-러시안 알고리즘 기반 편집거리 계산의 전처리단계를 개선하는 알고리즘을 제시한다. 제시한 알고리즘은 전처리를 위해 사용되는 문자열들의 수를 줄임으로써 Ο(3<SUP>2t</SUP>(min(2t,｜Σ｜)!× ｜Σ｜<SUP>max(2t-｜Σ｜,0)</SUP>t²)시간과 Ο(3<SUP>2t</SUP>(min(2t,｜Σ｜)!× ｜Σ｜<SUP>max(2t-｜Σ｜,0)</SUP>t) 공간을 이용하여 수행된다. 실험결과, 제시한 알고리즘은 기존의 알고리즘보다 룩업테이블의 메모리 크기에 대해서는 ｜Σ｜=2일 때 모든 t 에 대해 2배, ｜Σ｜=4, t=4일 때 약 10배, ｜Σ｜=26, t=2 일 때 약 19,000배 축소하였고, 룩업테이블을 생성하는 시간은 ｜Σ｜=2, t=6일 때 약 2배, ｜Σ｜=4, t=4일 때 약 10배, ｜Σ｜=26, t=2일 때 약 11,000배 빠른 수행시간을 보였다.
목차
요약
Abstract
1. 서론
2. 관련 연구
3. 편집거리계산을 위한 4-러시안 알고리즘의 문자열 변환
4. 실험결과
5. 결론
References
참고문헌 (13)
참고문헌 신청
1. [학술지(정기간행물)] - A. V. Aho / 1975 / Efficient String Matching: An Aid to Bibliographic Search / Communications of the ACM 18 (6)
2. [학술대회논문] - J. R. Wen / 2001 / Clustering User Queries of a Search Engine / Proceedings of the 10th international conference on World Wide Web : 162 ~ 168
3. [학술대회논문] - S. Forrest / 1994 / Self-nonself discrimination in a computer / Proc. IEEE Symp. Res. Security Privacy : 202 ~ 212
4. [학술대회논문] - M. Roesch / 1999 / Snort - Lightweight Intrusion Detection for Networks / Proc. of the 1999 USENIX LISA Systems Administration Conference
5. [학술지(정기간행물)] - N. Tuck / 2004 / Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection
2. [학술대회논문] - J. R. Wen / 2001 / Clustering User Queries of a Search Engine / Proceedings of the 10th international conference on World Wide Web : 162 ~ 168
3. [학술대회논문] - S. Forrest / 1994 / Self-nonself discrimination in a computer / Proc. IEEE Symp. Res. Security Privacy : 202 ~ 212
4. [학술대회논문] - M. Roesch / 1999 / Snort - Lightweight Intrusion Detection for Networks / Proc. of the 1999 USENIX LISA Systems Administration Conference
5. [학술지(정기간행물)] - N. Tuck / 2004 / Deterministic Memory-Efficient String Matching Algorithms for Intrusion Detection
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2015-560-001429276