http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
- 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
- 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
RISS 인기검색어
- 검색키워드
- 저자 : 허성찬(Sungchan Hur) (검색결과 3 건)
- 무료
- 기관 내 무료
- 유료
-
-
4-러시안 알고리즘 기반 편집거리계산의 전처리단계 개선
김영호(Youngho Kim),조석현(Sukhyeun Cho),허성찬(Sungchan Hur),심정섭(Jeong Seop Sim) 한국정보과학회 2014 정보과학회논문지 : 시스템 및 이론 Vol.41 No.2
알파벳 Σ의 문자들로 구성된 길이가 각각 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 .
-
ScienceON연관 검색어 추천
이 검색어로 많이 본 자료
활용도 높은 자료
