기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
Time and Space Efficient Search with Suffix Arrays
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • Time and Space Efficient Search with Suffix Arrays
  • Time and Space Efficient Search with Suffix Arrays
저자명
최용욱,심정섭,박근수,Choi. Yong-Wook,Sim. Jeong-Seop,Park. Kun-Soo
간행물명
정보과학회논문지. Journal of KIISE. 시스템 및 이론
권/호정보
2005년|32권 5호|pp.260-267 (8 pages)
발행정보
한국정보과학회
파일정보
정기간행물|ENG|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

영문초록

길이가 n인 알파벳 $Sigma$상의 텍스트 T에서 패턴 P를 효율적으로 검색하기 위해 접미사 트리와 접미사 배열이 널리 쓰이고 있다. 접미사 배열이 접미사 트리보다 더 적은 공간을 사용하기 때문에 텍스트의 길이가 긴 경우에는 접미사 배열이 더 선호되고 있다. 최근에는 접미사 배열을 이용한 O(${mid}P{mid}{codt}{mid}{Sigma}{mid}) 시간과 O(${mid}P{mid}{codt}log{mid}{Sigma}{mid}$) 시간 검색 알고리즘들이 개발되었다. 본 논문에서는 접미사 배열을 이용한 시간과 공간 효율적인 알고리즘들을 제시한다. 하나의 알고리즘은 O(${mid}P{mid}{codt}{mid}{Sigma}{mid}$) 비트 공간을 사용하여 O(${mid}P{mid}$) 시간에 수행되고, 다른 하나는 O($n{cdot}log{mid}{Sigma}{mid}+{mid}{Sigma}{mid}{cdot}$nlog log n/logn)비트 공간을 사용하여 O(${mid}P{mid}{codt}log{mid}{Sigma}{mid}$) 시간에 수행되는데, 두 번째 알고리즘은 보다 효율적인 공간을 사용하면서 여전히 빠른 알고리즘이다. 본 논문이 제시하는 알고리즘들이 시간과 공간에 있어 기존의 알고리즘들보다 더 효율적인 알고리즘들임을 실험을 통해 보여주고 있다.

기타언어초록

To search efficiently a text T of length n for a pattern P over an alphabet 5, suffix trees and suffix arrays are widely used. In case of a large text, suffix arrays are preferred to suffix trees because suffix ways take less space than suffix trees. Recently, O(${mid}P{mid}{codt}{mid}{Sigma}{mid}$-time and O(${mid}P{mid}P{cdot}log{mid}{Sigma}{mid}$)-time search algorithms in suffix ways were developed. In this paper we present time and space efficient search algorithms in suffix arrays. One algorithm runs in O(${mid}P{mid}$) time using O($n{cdot}{mid}{Sigma}{mid}$)-bits space, and the other runs in O($n{cdot}{mid}{Sigma}{mid}$ time using O($nlog{mid}{Sigma}{mid}+{mid}{Sigma}{mid}{cdot}$nlog log n/logn)-bits space, which is more space efficient and still fast. Experiments show that our algorithms are efficient in both time and space when compared to previous algorithms.