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.