Efficiently decoding strings from their shingles

Details Efficiently decoding strings from their shingles Efficiently decoding strings from their shingles

2012-04-15

arxiv.org/abs/1204.3293v1

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.

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-287905