GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages


Manual Reference Pages  -  UDCODE (3)

.ds Aq ’

NAME

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

CONTENTS

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.

CWis_udcode

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

CWud_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.
Search for    or go to Top of page |  Section 3 |  Main Index


perl v5.20.3 UDCODE (3) 2008-02-26

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with manServer 1.07.