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.
"ab", "abba", "b"
"abba" . "b" eq "ab" . "b" . "ab"
"a", "ab", "abb"
is_udcode
is_udcode(@words) returns true if and only if the specified code is uniquely decodable.
is_udcode(@words)
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.
@words
ud_pair(@words)
If @words is not uniquely decodable, then ud_pair returns references to two arrays of code words, $a, and $b, such that:
$a
$b
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"].
@words = qw(ab abba b)
["ab", "b", "ab"]
["abba", "b"]
If @words is uniquely decodable, ud_pair returns false.
Mark Jason Dominus (mjd@plover.com)
mjd@plover.com
This software is hereby released into the public domain. You may use, modify, or distribute it for any purpose whatsoever without restriction.
To install UDCode, copy and paste the appropriate command in to your terminal.
cpanm
cpanm UDCode
CPAN shell
perl -MCPAN -e shell install UDCode
For more information on module installation, please visit the detailed CPAN module installation guide.