Solving Some Sequence Problems on Run-length Encoded Strings: Longest Common Subsequences, Edit Distances, and Squares - Jia-jie Liu Y. L. Wang G. S. Huang - Boeken - VDM Verlag - 9783639022650 - 16 mei 2008
Indien omslag en titel niet overeenkomen, is de titel correct

Solving Some Sequence Problems on Run-length Encoded Strings: Longest Common Subsequences, Edit Distances, and Squares

Jia-jie Liu Y. L. Wang G. S. Huang

Prijs
€ 55,99

Besteld in een afgelegen magazijn

Verwachte levering 16 - 28 okt.
Voeg toe aan uw iMusic-verlanglijst

Solving Some Sequence Problems on Run-length Encoded Strings: Longest Common Subsequences, Edit Distances, and Squares

Measuring the similarity or difference between two strings is a fundamental problem to many applications. In bioinformatics, one has to predict the structures of RNA and proteins, to classify the functions of molecules, to infer the phylogeny of organisms, and to search entries in huge sequence databases. While processing electronic documents, one needs fast and flexible indexing techniques to perform searches. For this purpose, many measures are defined. The longest common subsequence and the edit distance are the most studied dealt with problems in string processing. In this book, we propose an O(min{mN, Mn}) time algorithm for finding a longest common subsequence of strings X and Y with lengths m and n, respectively, and run-length-encoded lengths M and N, respectively. On the other hand, we also improve the time bound to O(min{mN, Mn}) for finding the edit distance between strings X and Y. Squares play a central role from word combinatorics and application perspective. We show how to locate all squares in a run-length encoded string in time O(N logN). The time complexity of our result is optimal, and it is irrelevant to the length of the original uncompressed string.

Media Boeken     Paperback Book   (Boek met zachte kaft en gelijmde rug)
Vrijgegeven 16 mei 2008
ISBN13 9783639022650
Uitgevers VDM Verlag
Pagina's 78
Afmetingen 113 g
Taal en grammatica Engels