Normalized Compression Distance CLI

Works on any UNIX-like operating system with shell.

It has zero extra dependencies on a POSIX-compliant operating system.

MANUAL / DOCUMENTATION:

This program aims to provide a portable normalized compression distance implementation.

It should work on any UNIX-like OS. It works with any compressor program that can operate on files.

It only operates on files. It expects two arguments, paths. It will return the compressed size values as a table. Run it with no arguments, and pipe such a table into the program to compute NCD values.

With no arguments, it will also take in lines of such tables and compute the NCD for every input table line.

This program supports arbitrary precision: iff the environment variable PRECISION is set to a valid integer, the NCD values will be computed to that precision. Otherwise, the default is 16.

iff the environment variable NCD_SYMMETRIC is set(to anything, except nothing), it will return z(yx) in addition to z(xy) in the output table

Also, the computed result will be done symmetrically if the aforementioned environment variable is set.

Where z(x) is the byte length of x compressed with compressor z,

computes, with a compressor z, and files x, and y: NCDz(x, y)

which is equal to [(z(xy) - min{z(x), z(y)})/(max{z(x), z(y)})]

if NCD_SYMMETRIC is set, z(xy) is substituted with min{z(xy), z(yx)}

The NCD_COMPRESS should pass through a COMP_IN, and COMP_OUT path

which are variables that allow this script to control the input and output files to a compressor.

For example: NCD_COMPRESS='gzip $COMP_IN --stdout >$COMP_OUT'

notice the single quotes, as to not actually evaluate those variables.

But it should be evaluable shell for it to work!

This requires a scratch directory, and will by default use $TMPDIR. That directory must have enough space.

If doing large computations, it may be worth considering using a TMPDIR value that corresponds to

system memory, rather than an SSD, where it may cause wear.

Example usage

First things first, we need to set up a compressor, for example gzip:

$ export NCD_COMPRESS='gzip $COMP_IN --stdout >$COMP_OUT

Optionally, use symmetric NCD instead of the default assymetric NCD:

$ export NCD_COMPRESS="anything_just_not_nothing"

then, to compute the normalized compression distance between ./LICENSE and ./ncd.sh:

$ ./ncd.sh ./LICENSE ./ncd.sh | ./ncd.sh 

Then you can do:

$ for f1 in $(ls); do for f2 in $(ls); do printf "NCD of $f1 and $f2: "; ./ncd.sh "$f1" "$f2" | ./ncd.sh; done; done
NCD of LICENSE and LICENSE: .0829959514170040
NCD of LICENSE and ncd.sh: .8117809479981592
NCD of LICENSE and README.md: .9669902912621359
NCD of ncd.sh and LICENSE: .8117809479981592
NCD of ncd.sh and ncd.sh: .0427979751495628
NCD of ncd.sh and README.md: .6203405430280717
NCD of README.md and LICENSE: .9669902912621359
NCD of README.md and ncd.sh: .6203405430280717
NCD of README.md and README.md: .0495145631067961

Accumulating to a file, and computing NCD on the compressed-size data directly:

$ ./ncd.sh LICENSE LICENSE >> /tmp/data.txt
$ ./ncd.sh LICENSE README.md >> /tmp/data.txt
$ cat /tmp/data.txt | ./ncd.sh
.0829959514170040
.9669902912621359

License

This is free software. See LICENSE.