Mark Jason Dominus (陶敏修)


UDCode - Does a set of code words form a uniquely decodable code?


        use UDCode;

        if (is_udcode(@words)) { ... }

        my ($x1, $x2) = ud_pair(@words);


A code is a set of strings, called the code words. A code is "uniquely decodable" if any string S that is a concatenation of code words is so in exactly one way.

For example, the code "ab", "abba", "b" is not uniquely decodable, because "abba" . "b" eq "ab" . "b" . "ab". But the code "a", "ab", "abb" is uniquely decodable, because there is no such pair of sequences of code words.


is_udcode(@words) returns true if and only if the specified code is uniquely decodable.


If @words is not a uniquely decodable code, then ud_pair(@words) returns a proof of that fact, in the form of two distinct sequences of code words whose concatenations are equal.

If @words is not uniquely decodable, then ud_pair returns references to two arrays of code words, $a, and $b, such that:

        join("", @$a) eq join("", @$b)

For example, given @words = qw(ab abba b), ud_pair might return the two arrays ["ab", "b", "ab"] and ["abba", "b"].

If @words is uniquely decodable, ud_pair returns false.


Mark Jason Dominus (


This software is hereby released into the public domain. You may use, modify, or distribute it for any purpose whatsoever without restriction.