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.