File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Performance analysis of some simple heuristics for computing longest common subsequences

TitlePerformance analysis of some simple heuristics for computing longest common subsequences
Authors
KeywordsHeuristics
Longest common subsequence
Performance analysis
Scan algorithms
Issue Date1994
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica, 1994, v. 12 n. 4-5, p. 293-311 How to Cite?
AbstractAlthough the Longest Common Subsequence (LCS)Problem has been studied by many researchers for years, heuristic methods have not been investigated before. In this paper we present a simple heuristic which guarantees to return a common subsequence of length at least 1/s that of the longest where s is the number of different symbols in the input strings. Furthermore, we generalize the idea to several classes of heuristic algorithms. Surprisingly, we find that no other heuristic in these classes outperforms this simple algorithm. In other words, we show that any heuristic which uses only global information, such as number of symbol occurrences, might return a common subsequence as short as 1/s of the length of the longest. Analysis of the average performance of the simple heuristic for s=2 is also presented. © 1994 Springer-Verlag New York Inc.
Persistent Identifierhttp://hdl.handle.net/10722/89032
ISSN
2015 Impact Factor: 0.795
2015 SCImago Journal Rankings: 0.898
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChin, Fen_HK
dc.contributor.authorPoon, CKen_HK
dc.date.accessioned2010-09-06T09:51:32Z-
dc.date.available2010-09-06T09:51:32Z-
dc.date.issued1994en_HK
dc.identifier.citationAlgorithmica, 1994, v. 12 n. 4-5, p. 293-311en_HK
dc.identifier.issn0178-4617en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89032-
dc.description.abstractAlthough the Longest Common Subsequence (LCS)Problem has been studied by many researchers for years, heuristic methods have not been investigated before. In this paper we present a simple heuristic which guarantees to return a common subsequence of length at least 1/s that of the longest where s is the number of different symbols in the input strings. Furthermore, we generalize the idea to several classes of heuristic algorithms. Surprisingly, we find that no other heuristic in these classes outperforms this simple algorithm. In other words, we show that any heuristic which uses only global information, such as number of symbol occurrences, might return a common subsequence as short as 1/s of the length of the longest. Analysis of the average performance of the simple heuristic for s=2 is also presented. © 1994 Springer-Verlag New York Inc.en_HK
dc.languageengen_HK
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_HK
dc.relation.ispartofAlgorithmicaen_HK
dc.subjectHeuristicsen_HK
dc.subjectLongest common subsequenceen_HK
dc.subjectPerformance analysisen_HK
dc.subjectScan algorithmsen_HK
dc.titlePerformance analysis of some simple heuristics for computing longest common subsequencesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0178-4617&volume=12&spage=293&epage=311&date=1994&atitle=Performance+analysis+of+some+simple+heuristics+for+computing+longest+common+subsequencesen_HK
dc.identifier.emailChin, F:chin@cs.hku.hken_HK
dc.identifier.authorityChin, F=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/BF01185429en_HK
dc.identifier.scopuseid_2-s2.0-0028518079en_HK
dc.identifier.hkuros1191en_HK
dc.identifier.volume12en_HK
dc.identifier.issue4-5en_HK
dc.identifier.spage293en_HK
dc.identifier.epage311en_HK
dc.identifier.isiWOS:A1994PC55900004-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChin, F=7005101915en_HK
dc.identifier.scopusauthoridPoon, CK=7202673523en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats