KCI등재
4-러시안 알고리즘 기반 편집거리계산의 전처리단계 개선 = An Improvement of the Preprocessing Step of the Four-Russians’ Algorithm for Computing Edit Distances
저자
김영호(Youngho Kim) ; 조석현(Sukhyeun Cho) ; 허성찬(Sungchan Hur) ; 심정섭(Jeong Seop Sim) 연구자관계분석
발행기관
학술지명
권호사항
발행연도
2014
작성언어
Korean
주제어
등재정보
KCI등재
자료형태
학술저널
발행기관 URL
수록면
87-92(6쪽)
KCI 피인용횟수
0
제공처
알파벳 Σ의 문자들로 구성된 길이가 각각 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배 빠른 수행시간을 보였다.
더보기The edit distance between two strings of length m and n 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 Ο((3|Σ|)<SUP>2t</SUP>t² time and Ο((3|Σ|)<SUP>2t</SUP>t) space where t is the length of strings used for the preprocess. The second step, called the computation step, runs in Ο(mn/t) time and Ο((3|Σ|)<SUP>2t</SUP>t+mn) 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 Ο(3<SUP>2t</SUP>(min(2t,|Σ|)!× |Σ|<SUP>max(2t-|Σ|,0)</SUP>t²) time and Ο(3<SUP>2t</SUP>(min(2t,|Σ|)!× |Σ|<SUP>max(2t-|Σ|,0)</SUP>t) 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(|Σ|=2 ) and every t , our algorithm is 2 times smaller than the previous algorithm. For a DNA alphabet(|Σ|=4 ), our algorithm is about 10 times smaller than the previous algorithm when t=4 . For the English alphabet(|Σ|=26), our algorithm is about 19,000 times smaller than the previous algorithm when t=2 . In terms of construction time of lookup table, for a binary alphabet(|Σ|=2 ), our algorithm is about 2 times faster than the previous algorithm when t=6 . For a DNA alphabet(|Σ|=4), our algorithm is about 10 times faster than the previous algorithm when t=4 . For the English alphabet(|Σ|=26), our algorithm is about 11,000 times faster than the previous algorithm when t=2 .
더보기분석정보
연월일 | 이력구분 | 이력상세 | 등재구분 |
---|---|---|---|
2014-09-01 | 평가 | 학술지 통합(기타) | |
2013-04-26 | 학술지명변경 | 한글명 : 정보과학회논문지 : 시스템 및 이론 </br>외국어명 : Journal of KIISE : Computer Systems and Theory | KCI등재 |
2011-01-01 | 평가 | 등재학술지 유지(등재유지) | KCI등재 |
2009-01-02 | 학술지명변경 | 한글명 : 정보과학회논문지 : 시스템 및 이론 </br>외국어명 : Journal of KISS : Computer Systems and Theory | KCI등재 |
2009-01-01 | 평가 | 등재학술지 유지(등재유지) | KCI등재 |
2007-01-01 | 평가 | 등재학술지 유지(등재유지) | KCI등재 |
2005-01-01 | 평가 | 등재학술지 유지(등재유지) | KCI등재 |
2002-01-01 | 평가 | 등재학술지 선정(등재후보2차) | KCI등재 |
서지정보 내보내기(Export)
닫기소장기관 정보
닫기권호소장정보
닫기오류접수
닫기오류 접수 확인
닫기음성서비스 신청
닫기음성서비스 신청 확인
닫기이용약관
닫기학술연구정보서비스 이용약관 (2017년 1월 1일 ~ 현재 적용)
학술연구정보서비스(이하 RISS)는 정보주체의 자유와 권리 보호를 위해 「개인정보 보호법」 및 관계 법령이 정한 바를 준수하여, 적법하게 개인정보를 처리하고 안전하게 관리하고 있습니다. 이에 「개인정보 보호법」 제30조에 따라 정보주체에게 개인정보 처리에 관한 절차 및 기준을 안내하고, 이와 관련한 고충을 신속하고 원활하게 처리할 수 있도록 하기 위하여 다음과 같이 개인정보 처리방침을 수립·공개합니다.
주요 개인정보 처리 표시(라벨링)
목 차
3년
또는 회원탈퇴시까지5년
(「전자상거래 등에서의 소비자보호에 관한3년
(「전자상거래 등에서의 소비자보호에 관한2년
이상(개인정보보호위원회 : 개인정보의 안전성 확보조치 기준)개인정보파일의 명칭 | 운영근거 / 처리목적 | 개인정보파일에 기록되는 개인정보의 항목 | 보유기간 | |
---|---|---|---|---|
학술연구정보서비스 이용자 가입정보 파일 | 한국교육학술정보원법 | 필수 | ID, 비밀번호, 성명, 생년월일, 신분(직업구분), 이메일, 소속분야, 웹진메일 수신동의 여부 | 3년 또는 탈퇴시 |
선택 | 소속기관명, 소속도서관명, 학과/부서명, 학번/직원번호, 휴대전화, 주소 |
구분 | 담당자 | 연락처 |
---|---|---|
KERIS 개인정보 보호책임자 | 정보보호본부 김태우 | - 이메일 : lsy@keris.or.kr - 전화번호 : 053-714-0439 - 팩스번호 : 053-714-0195 |
KERIS 개인정보 보호담당자 | 개인정보보호부 이상엽 | |
RISS 개인정보 보호책임자 | 대학학술본부 장금연 | - 이메일 : giltizen@keris.or.kr - 전화번호 : 053-714-0149 - 팩스번호 : 053-714-0194 |
RISS 개인정보 보호담당자 | 학술진흥부 길원진 |
자동로그아웃 안내
닫기인증오류 안내
닫기귀하께서는 휴면계정 전환 후 1년동안 회원정보 수집 및 이용에 대한
재동의를 하지 않으신 관계로 개인정보가 삭제되었습니다.
(참조 : RISS 이용약관 및 개인정보처리방침)
신규회원으로 가입하여 이용 부탁 드리며, 추가 문의는 고객센터로 연락 바랍니다.
- 기존 아이디 재사용 불가
휴면계정 안내
RISS는 [표준개인정보 보호지침]에 따라 2년을 주기로 개인정보 수집·이용에 관하여 (재)동의를 받고 있으며, (재)동의를 하지 않을 경우, 휴면계정으로 전환됩니다.
(※ 휴면계정은 원문이용 및 복사/대출 서비스를 이용할 수 없습니다.)
휴면계정으로 전환된 후 1년간 회원정보 수집·이용에 대한 재동의를 하지 않을 경우, RISS에서 자동탈퇴 및 개인정보가 삭제처리 됩니다.
고객센터 1599-3122
ARS번호+1번(회원가입 및 정보수정)