Computer Science – Discrete Mathematics
Scientific paper
2012-04-15
Computer Science
Discrete Mathematics
Scientific paper
Determining whether an unordered collection of overlapping substrings (called shingles) can be uniquely decoded into a consistent string is a problem that lies within the foundation of a broad assortment of disciplines ranging from networking and information theory through cryptography and even genetic engineering and linguistics. We present three perspectives on this problem: a graph theoretic framework due to Pevzner, an automata theoretic approach from our previous work, and a new insight that yields a time-optimal streaming algorithm for determining whether a string of $n$ characters over the alphabet $\Sigma$ can be uniquely decoded from its two-character shingles. Our algorithm achieves an overall time complexity $\Theta(n)$ and space complexity $O(|\Sigma|)$. As an application, we demonstrate how this algorithm can be extended to larger shingles for efficient string reconciliation.
Kontorovich Aryeh
Trachtenberg Ari
No associations
LandOfFree
Efficiently decoding strings from their shingles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficiently decoding strings from their shingles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficiently decoding strings from their shingles will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-287905