4-러시안 알고리즘 기반 편집거리계산의 전처리단계 개선 (An Improvement of the Preprocessing Step of the Four-Russians’ Algorithm for Computing Edit Distances)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 시스템 및 이론 / 41권 / 2호 / 87 ~ 92페이지
· 저자명 : 김영호, 조석현, 허성찬, 심정섭

초록

알파벳 의 문자들로 구성된 길이가 각각 , 인 두 문자열의 편집거리는 4-러시안 알고리즘을 이용하여 계산할 수 있다. 편집거리를 계산하기 위한 4-러시안 알고리즘은 두 단계로 구성된다. 첫 번째 단계인 전처리단계는 전처리를 위해 사용되는 문자열들의 길이가 일 때, 시간과 공간을 이용하여 수행된다. 두 번째 단계인 계산단계는 시간과 공간을 이용하여 수행된다. 본 논문에서는 4-러시안 알고리즘 기반 편집거리 계산의 전처리단계를 개선하는 알고리즘을 제시한다. 제시한 알고리즘은 전처리를 위해 사용되는 문자열들의 수를 줄임으로써 시간과 공간을 이용하여 수행된다. 실험결과, 제시한 알고리즘은 기존의 알고리즘보다 룩업테이블의 메모리 크기에 대해서는 일 때 모든 에 대해 2배, , 일 때 약 10배, , 일 때 약 19,000배 축소하였고, 룩업테이블을 생성하는 시간은 , 일 때 약 2배, , 일 때 약 10배, , 일 때 약 11,000배 빠른 수행시간을 보였다.

영어초록

The edit distance between two strings of length and over an alphabet can be computed using the Four-Russians’ algorithm. The Four-Russians’ algorithm for computing edit distances consists of two steps. The first step, called the preprocessing step, runs in time and space where is the length of strings used for the preprocess. The second step, called the computation step, runs in time and space. In this paper, we propose an improved algorithm of the preprocessing step of the Four-Russians’ algorithm for computing edit distances. Our algorithm runs in time and space by reducing the number of strings used for the preprocess. In terms of memory sizes of lookup tables, experimental results show that for a binary alphabet() and every , our algorithm is 2 times smaller than the previous algorithm. For a DNA alphabet(), our algorithm is about 10 times smaller than the previous algorithm when . For the English alphabet(), our algorithm is about 19,000 times smaller than the previous algorithm when . In terms of construction time of lookup table, for a binary alphabet(), our algorithm is about 2 times faster than the previous algorithm when . For a DNA alphabet(), our algorithm is about 10 times faster than the previous algorithm when . For the English alphabet(), our algorithm is about 11,000 times faster than the previous algorithm when .

참고자료

· 없음