지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 정보과학회논문지 : 시스템 및 이론 정보과학회논문지 : 시스템 및 이론 제32권 제5·6호
- 발행연도
- 2005.6
- 수록면
- 260 - 267 (8page)
이용수
이 논문의 연구 히스토리 (2)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
길이가 n 인 알파벳 Σ 상의 텍스트 T 에서 패턴 P 를 효율적으로 검색하기 위해 접미사 트리와 접미사 배열이 널리 쓰이고 있다. 접미사 배열이 접미사 트리보다 더 적은 공간을 사용하기 때문에 텍스트의 길이가 긴 경우에는 접미사 배열이 더 선호되고 있다. 최근에는 접미사 배열을 이용한 O(|P|ㆍ|Σ|) 시간과 O( |P |ㆍlog |Σ|) 시간 검색 알고리즘들이 개발되었다.
본 논문에서는 접미사 배열을 이용한 시간과 공간 효율적인 알고리즘들을 제시한다. 하나의 알고리즘은 O(|P|ㆍ|Σ|) 비트 공간을 사용하여 O(|P|) 시간에 수행되고, 다른 하나는 O( nㆍlog |Σ | + |Σ |ㆍn log log n/ log n)비트 공간을 사용하여 O( |P |ㆍ log |Σ|) 시간에 수행되는데, 두 번째 알고리즘은 보다 효율적인 공간을 사용하면서 여전히 빠른 알고리즘이다. 본 논문이 제시하는 알고리즘들이 시간과 공간에 있어 기존의 알고리즘들보다 더 효율적인 알고리즘들임을 실험을 통해 보여주고 있다.
본 논문에서는 접미사 배열을 이용한 시간과 공간 효율적인 알고리즘들을 제시한다. 하나의 알고리즘은 O(|P|ㆍ|Σ|) 비트 공간을 사용하여 O(|P|) 시간에 수행되고, 다른 하나는 O( nㆍlog |Σ | + |Σ |ㆍn log log n/ log n)비트 공간을 사용하여 O( |P |ㆍ log |Σ|) 시간에 수행되는데, 두 번째 알고리즘은 보다 효율적인 공간을 사용하면서 여전히 빠른 알고리즘이다. 본 논문이 제시하는 알고리즘들이 시간과 공간에 있어 기존의 알고리즘들보다 더 효율적인 알고리즘들임을 실험을 통해 보여주고 있다.
목차
요약
Abstract
1. Introduction
2. Preliminaries
3. Backward search
4. O(|P|) - time algorithm
5. O(|P|ㆍlog |Σ|) - time algorithm
6. Experimental results
7. Conclusion
References
저자소개
참고문헌 (14)
참고문헌 신청
[학술지(정기간행물)] - McCreight / 1976 / A space-economical suffix tree construction algorithm
[학술지(정기간행물)] - Weiner / 1973 / of 14th IEEE Symposium on Switching and Automata Theory
[학술지(정기간행물)] - U / 1993 / A new method for on-line string searches SIAM Journal on Computing
[학술지(정기간행물)] - Farach-Colton, P. Ferragina and S. Muthukrishnan / 2000 / On the sorting-complexity of suffix tree construction
[학술지(정기간행물)] - R. Grossi and J.S. Vitter / 2000 / Compressed suffix arrays and suffix trees with applications to text indexing and string matching
[학술지(정기간행물)] - Weiner / 1973 / of 14th IEEE Symposium on Switching and Automata Theory
[학술지(정기간행물)] - U / 1993 / A new method for on-line string searches SIAM Journal on Computing
[학술지(정기간행물)] - Farach-Colton, P. Ferragina and S. Muthukrishnan / 2000 / On the sorting-complexity of suffix tree construction
[학술지(정기간행물)] - R. Grossi and J.S. Vitter / 2000 / Compressed suffix arrays and suffix trees with applications to text indexing and string matching
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
접미사 배열을 이용한 선형시간 탐색
정보과학회논문지 : 시스템 및 이론
2005 .06
-
접미사 배열에서의 패턴 검색 알고리즘
한국정보과학회 학술발표논문집
2004 .04
-
A New Suffix Tree Clustering Algorithm
ITC-CSCC :International Technical Conference on Circuits Systems, Computers and Communications
2006 .07
-
A Generalization of the Linearized Suffix Tree to Square Matrices
멀티미디어학회논문지
2010 .12
-
Suffix Array를 구축하는 새로운 알고리즘
정보과학회논문지(A)
1997 .07
-
Suffix Array를 구축하는 새로운 알고리즘
한국정보과학회 학술발표논문집
1996 .10
-
Practical Suffix Sorting 알고리즘의 개선
한국정보과학회 학술발표논문집
2008 .10
-
실용적인 접미사 정렬 알고리즘의 개선
정보과학회논문지 : 시스템 및 이론
2009 .04
-
Improving Lookup Time Complexity of Compressed Suffix Arrays using Multi-ary Wavelet Tree
Journal of Computing Science and Engineering
2009 .03
-
써픽스 배열 합병을 이용한 일반화된 써픽스 배열의 효율적인 구축 알고리즘
정보과학회논문지 : 시스템 및 이론
2005 .06
-
Comparisons of Practical Performance for Constructing Compressed Suffix Arrays
정보과학회논문지 : 시스템 및 이론
2007 .06
-
실시간 속기 자막 환경에서 멀티미디어 정보 검색을 위한 Prefix Array
대한전기학회 학술대회 논문집
2006 .10
-
Dynamic Compressed Representation of Texts with Rank/Select
Journal of Computing Science and Engineering
2009 .03
-
Suffix Tree를 이용한 웹 문서 클러스터의 제목 생성 방법 성능 비교 ( Performance Comparing of Keyword Extraction Methods for Web Document Cluster using Suffix Tree Clustering )
한국지능정보시스템학회 학술대회논문집
2002 .11
-
Exact Matching Using the Suffix Tree on Disk
ITC-CSCC :International Technical Conference on Circuits Systems, Computers and Communications
2005 .07
-
Merge 기법을 이용한 Suffix tree의 구성
한국통신학회 학술대회논문집
2005 .06
-
블록정렬압축을 이용한 접미사배열의 효율적인 저장
정보과학회논문지 : 시스템 및 이론
2001 .08
-
써픽스 배열 합병을 위한 선형 시간 알고리즘
한국정보과학회 영남지부 학술발표논문집
2003 .12
-
Gene Sequences Clustering and Identifying Functional Domain Using a Suffix Tree Algorithm
제어로봇시스템학회 국제학술대회 논문집
2006 .10
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-569-015189943