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.

This module provides a pair of functions to tell whether a set of code words is a uniquely decodable code, and to find an example of sequences of code words whose concatenations are the same, if there is such a pair.

INTERFACE

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

COPYRIGHT AND LICENSE

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