NAME

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

SYNOPSIS

        use UDCode;

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

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

DESCRIPTION

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"

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

"ud_pair"

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.

AUTHOR

Mark Jason Dominus ("mjd@plover.com")

COPYRIGHT

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