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 @math characters over the alphabet @math can be uniquely decoded from its two-character shingles. Our algorithm achieves an overall time complexity @math and space complexity @math . As an application, we demonstrate how this algorithm can be extended to larger shingles for efficient string reconciliation.
It was shown in @cite_2 that the collection of strings having a unique reconstruction from the shingles representation is a regular language. Following up, Li and Xie @cite_18 gave an explicit construction of a deterministic finite-state automaton (DFA) recognizing this language. Our work in @cite_21 has demonstrated that there is no DFA of subexponential size for recognizing this language, and instead we have exhibited an equivalent NFA with @math states.
@cite_18 @cite_21 @cite_2
2041411237 1977458360
Symbolic sequences uniquely reconstructible from all their substrings of length k compose a regular factorial language. We thoroughly characterize this language by its minimal forbidden words, and explicitly build up a deterministic finite automaton that accepts it. This provides an efficient on-line algorithm for testing the unique reconstructibility of the sequences. We define the family of n-gram embeddings from strings over a finite alphabet into the semimodule NK. We classify all ξ ∈ NK that are valid images of strings under such embeddings, as well as all ξ whose inverse image consists of exactly 1 string (we call such ξ uniquely decodable). We prove that for a fixed alphabet, the set of all strings whose image is uniquely decodable is a regular language.