정보처리학회 논문지 A
Current Result Document : 1 / 1
| 한글제목(Korean Title) |
스트링의 최대 서픽스를 계산하는 효율적인 외부 메모리 알고리즘 |
| 영문제목(English Title) |
Efficient External Memory Algorithm for Finding the Maximum Suffix of a String |
| 저자(Author) |
김성권
김수철
조정식
Sung Kwon Kim
Soocheol Kim
Jungsik Cho
|
| 원문수록처(Citation) |
VOL 15-A NO. 04 PP. 0239 ~ 0242 (2008. 08) |
한글내용
(Korean Abstract) |
외부 메모리 계산 모델에서 스트링의 최대서픽스를 찾는 문제를 고려한다. 외부메모리 모델에서는 디스크와 내부메모리 사이의 디스크 입출력 횟수를 줄이는 알고리즘을 설계하는 것이 중요 사항이다. 길이가 N인 스트링은 N개의 서픽스를 가지는데, 이중에서 사전 순서에 따라 가장 큰 것을 최대 서픽스라 부른다. 최대서픽스를 구하는 것은 여러 스트링 문제를 해결하는 데 중요한 역할을 한다. 본 논문에서는 길이가 N인 스트링의 최대 서픽스를 구하는 외부메모리 알고리즘을 제시한다. 이 알고리즘은 네 개의 내부 메모리 블록을 사용하고 최대 4(N/L)번의 디스크 입출력을 한다. 여기서 L은 블록의 크기이다. |
영문내용
(English Abstract) |
We study the problem of finding the maximum suffix of a string on the external memory model of computation with one disk. In this model, we are primarily interested in designing algorithms that reduce the number of I/Os between the disk and the internal memory. A string of length has suffixes and among these, the lexicographically largest one is called the maximum suffix of the string. Finding the maximum suffix of a string plays a crucial role in solving some string problems. In this paper, we present an external memory algorithm for computing the maximum suffix of a string of length. The algorithm uses four blocks in the internal memory and performs at most 4 disk I/Os, where is the size of a block. |
| 키워드(Keyword) |
스트링
최대 서픽스
외부메모리 알고리즘
External Memory Algorithms
Maximum Suffix
String
|
| 파일첨부 |
PDF 다운로드
|
