Sardinas-Patterson Algorithm

The Sardinas-Patterson algorithm is a method in coding theory for determining whether a variable-length code is uniquely decodable, that is, whether every possible encoded message has only one way of being broken back down into codewords. It works by carrying out a systematic search for any string that could be built up from the code's words in two genuinely different ways, so that finding such a string proves the code is not uniquely decodable, and finding none within the algorithm's bounded search proves that it is; the algorithm runs in time polynomial in the length of its input, making it practical for real coding problems. It was developed by August Albert Sardinas and George W. Patterson, who published it in 1953; computer scientist Robert W. Floyd is reported by Donald Knuth to have independently rediscovered essentially the same method about ten years later, in 1963, apparently unaware that coding theorists already considered the problem settled. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/