http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
일반화접미사배열을 이용한 선형시간 최장공통비상위문자열 알고리즘
조석현(Sukhyeun Cho),윤현철(Hyunchul Yoon),나중채(Joong Chae Na),심정섭(Jeong Seop Sim) 한국정보과학회 2011 정보과학회논문지 : 시스템 및 이론 Vol.38 No.5
상수크기의 알파벳 Σ에 대해 정의된 문자열 집합 F가 주어질 때, 주어진 문자열 집합 F 내의 어떤 문자열도 포함하지 않는 문자열을 F에 대한 공통비상위문자열이라 하고 공통비상위문자열 중에서 가장 긴 유한길이의 문자열을 최장공통비상위문자열이라 한다. 접미사 그래프 모델 또는 접두사 그래프 모델을 이용하여 F 내의 모든 문자열들의 길이의 합에 대해 선형시간에 최장공통비상위문자열을 찾는 알고리즘들이 최근 제시되었다. 이중 접미사 그래프 모델을 이용하는 알고리즘은 일반화접미사트리를 이용한다. 본 논문에서는 일반화접미사배열을 이용하여 접미사 그래프 모델을 생성함으로써 최장공통비상위문자열을 찾는 새로운 알고리즘을 제시한다. 또한, 기존의 두 알고리즘들과 새로이 제시된 알고리즘을 구현하여 성능을 실험한 결과를 제시한다. Given a set F of strings over constant size alphabet Σ, the common nonsuperstring of F is a string that is not a superstring of any string in F. Among the common nonsuperstrings of F, the longest one with finite length is the longest common nonsuperstring of F. Recently, two O(??F??)-time algorithms for finding the longest common nonsuperstring were proposed where ??F??denotes the sum of the lengths of the strings in F. One algorithm was based on the suffix graph model and the other was based on the prefix graph model. Especially, the former algorithm used generalized suffix trees to construct the suffix graph model. In this paper, we propose another linear-time algorithm based on suffix graph model. Our algorithm uses generalized suffix arrays to construct the suffix graph model. Also, we propose some experimental results to show the performance of our algorithm.
강문성(Munseong Kang),조석현(Sukhyeun Cho),심정섭(Jeong Seop Sim) 한국정보과학회 2016 정보과학회논문지 Vol.43 No.5
순위패턴매칭문제는 텍스트 T와 패턴 P가 주어질 때, P와 각 문자들의 순위가 동일한 순서로 나타나는 T의 모든 부분문자열을 찾는 문제이다. 순위패턴매칭문제는 주가지수분석과 음악의 유사성분석과 같이 문자 자체를 비교하는 것보다 값의 변화순서가 중요한 분야에서 연구가 진행되었다. 순위다중패턴매칭문제는 텍스트 T와 여러 개의 패턴들로 이루어진 패턴집합 ℙ가 주어질 때, ℙ에 속한 패턴과 각 문자들의 순위가 동일한 순서로 나타나는 T의 모든 부분문자열을 찾는 문제이다. 본 논문에서는 순위다중 패턴매칭문제를 해결하는 해싱기반 알고리즘을 제시한다. Given a text Tand a pattern P, the order-preserving pattern matching problem is to find all substrings in T which have the same relative orders as P. The order-preserving pattern matching problem has been studied in terms of finding some patterns affected by relative orders, not by their absolute values. Given a text T and a pattern set ℙ, the order-preserving multiple pattern matching problem is to find all substrings in T which have the same relative orders as any pattern in ℙ. In this paper, we present a hashing-based algorithm for the order-preserving multiple pattern matching problem.
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 .