A Fast Algorithm for Computing Longest Common Subsequences of Small Alphabet Size

• Item type: JInfP(1)
• 公開日: 1991-02-10
• タイトル: A Fast Algorithm for Computing Longest Common Subsequences of Small Alphabet Size
• タイトル / 言語: en
• タイトル: A Fast Algorithm for Computing Longest Common Subsequences of Small Alphabet Size
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Department of Computer Science University of Hong Kong/Department of Computer Science University of Texas at Dallas
• 著者所属: Department of Computer Science University of Hong Kong
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, University of Hong Kong/Department of Computer Science, University of Texas at Dallas
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, University of Hong Kong
• 著者名: FrancisY.L.Chin; C.K.Poon
• 著者名(英): Francis, Y.L.Chin; C., K.Poon
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Given two strings of lengths m and n⩾m on an alphabet of size s the longest common subsequence (LCS) problem is to determine the longest subsequence that can be obtained by deleting zero or more symbols from either string. The first ョﾈmn) algorithm was given by Hirschberg in 1975. The algorithm was later revised to ョﾈln) where l is the length of an LCS between the two strings. Another strategy given by Hunt and Szymanski takes ョﾈrlogn) time where r⩽mn is the total number of matches between the two strings. Apostolico and Guerra combined the two approaches and derived an ョﾈmlogn+dlog(mn/d)) algorithm where d⩽r is the number of dominant matches (minimal candidates) between the two strings. Efficient algorithms for two similar strings were devised by Nakatsu et al.[7]and Myers[61with time complexities of ョﾈn(m-1)) and ョﾈn(n-1)) respectively. This paper presents a new algorithm for this problem which requires preprocessing that is nearly standard for the LCS problem and has time and space complexity of ョﾈns+min{ds lm}) and ョﾈns+d) respectively. This algorithm is particularly efficient when s (the alphabet size) is small Different data structures are used to obtain variations of the basic algorithm that require different time and space complexities.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given two strings of lengths m and n⩾m on an alphabet of size s, the longest common subsequence (LCS) problem is to determine the longest subsequence that can be obtained by deleting zero or more symbols from either string. The first ョﾈmn) algorithm was given by Hirschberg in 1975. The algorithm was later revised to ョﾈln), where l is the length of an LCS between the two strings. Another strategy given by Hunt and Szymanski takes ョﾈrlogn) time, where r⩽mn is the total number of matches between the two strings. Apostolico and Guerra combined the two approaches and derived an ョﾈmlogn+dlog(mn/d)) algorithm, where d⩽r is the number of dominant matches (minimal candidates) between the two strings. Efficient algorithms for two similar strings were devised by Nakatsu et al.[7]and Myers[61with time complexities of ョﾈn(m-1)) and ョﾈn(n-1)), respectively. This paper presents a new algorithm for this problem, which requires preprocessing that is nearly standard for the LCS problem and has time and space complexity of ョﾈns+min{ds,lm}) and ョﾈns+d), respectively. This algorithm is particularly efficient when s (the alphabet size) is small Different data structures are used to obtain variations of the basic algorithm that require different time and space complexities.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA00700121
• 書誌情報: Journal of Information Processing; 巻 13, 号 4, p. 463-469, 発行日 1991-02-10
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-6652
• 出版者 / 言語: ja
• 出版者: 情報処理学会