osct ¶This program prints an output signal choice tree a large actor uses to generate output signals with various profile probabilities. By default, it is a Huffman tree generated for a list of declared profile probabilities of output signals.
As the profile probability of an output signal determined by the structure of a Huffman tree is equal to tree arity raised to integer power equal to negative depth of a tree node for the output signal, actual profile probability of an output signal can be substantially different from its declared profile probability. On passing the option -t, --tolerance=FLOAT, a large actor restructures the Huffman tree by node splitting and adding leaves for output signals so that multiple leaves can correspond to a single output signal. As a result of this restructuring, the output signal choice tree provides selecting output signals with actual profile probabilities that differ from declared profile probabilities by a value less than the argument of that option.
Run the program using the following command line formats:
qsmm-example-osct [OPTIONS] -N NSIG_OUT qsmm-example-osct [OPTIONS] -f SIG_WEIGHT_FILE qsmm-example-osct [OPTIONS] WEIGHT1 ... WEIGHTn
where WEIGHT1 … WEIGHTn are declared relative profile probabilities of output signals.
Example
The following command prints an output signal choice tree for selecting one of five output signals with equal declared profile probabilities:
$ qsmm-example-osct -N 5 +---+---+--- [0.12500000] 1 | | | | | +--- [0.12500000] 0 | | | +--- [0.25000000] 4 | +---+--- [0.25000000] 3 | +--- [0.25000000] 2Numbers in ‘[’ … ‘]’ are actual profile probabilities of tree leaves, and numbers after ‘]’ are indices of output signals corresponding to tree leaves.
As declared profile probability of every output signal is 1.0/5=0.2, actual profile probabilities 0.125 and 0.25 indicated in the output signal choice tree above differ from the declared profile probability significantly—by 0.2-0.125=0.075 and 0.25-0.2=0.05 respectively. Passing the option -t 0.005 makes the differences be less than 0.005:
$ qsmm-example-osct -N 5 -t 0.005 --ow=weights +---+---+--- [0.12500000] 1 | | | | | +---+--- [0.06250000] 1 | | | | | +--- [0.06250000] 0 | | | +---+--- [0.12500000] 0 | | | +--- [0.12500000] 4 | +---+---+--- [0.12500000] 2 | | | +--- [0.12500000] 3 | +---+---+--- [0.06250000] 3 | | | +--- [0.06250000] 4 | +---+---+---+--- [0.01562500] 4 | | | | | +--- [0.01562500] 2 | | | +---+---+--- [0.00781250] 1 | | | | | +--- [0.00781250] 0 | | | +--- [0.01562500] 3 | +--- [0.06250000] 2The above tree has multiple leaves for each output signal. The created file weights contains four columns: the index of an output signal, its declared profile probability, its actual profile probability, and absolute difference between the two profile probabilities.
$ cat weights 0 0.20000000 0.19531250 0.00468750 1 0.20000000 0.19531250 0.00468750 2 0.20000000 0.20312500 0.00312500 3 0.20000000 0.20312500 0.00312500 4 0.20000000 0.20312500 0.00312500The above table shows that the maximum difference between the declared profile probability and an actual profile probability is 0.0046875, which is considerably less than 0.075 for the non-restructured (original) tree.
The program supports the following command line options:
Generate an output signal choice tree with a specified arity. It is the maximum number of child nodes of every tree node. The default value is 2.
Read declared relative profile probabilities of output signals from a specified file. The filename ‘-’ means stdin. Each line of the file should contain the index of an output signal and its declared relative profile probability separated by a space. Declared profile probabilities of output signals not present in the file are zero.
Use equal declared profile probabilities for a specified number of output signals. Each declared profile probability is equal to 1 divided by the number of output signals.
Dump a generated output signal choice tree to a specified file. By default, dump the tree to stdout.
Dump to a specified file or stdout a table where each line contains the index of an output signal, its declared profile probability, its actual profile probability, and absolute difference between the two probabilities.
Restructure a Huffman tree to obtain an output signal choice tree where absolute difference between a declared profile probability and actual profile probability for every output signal is less than a specified value. On omitting this option, use a Huffman tree as an output signal choice tree.