CFG Approximations: Light implementation of four text-compression algorithms based on context-free grammars

CFG Approximations is a Java package implementing the compression algorithms considered in this SODA 2002 article by Lehmann and Shelat.

Downloading the package

The archive is available for download:

  As a JAR file (approximations.JAR)
Or
 
  As a TAR Gziped file (approximations.TGZ)

Running JAVA program

Prior to running the software, it is necessary to downloading an install a recent version of the JAVA JDK (or JRE or SDK). It is available from SUN.

Under Zindozs (and maybe some other Linux distributions...), a jar can be executed through a simple double-click, once Java is installed.

A JAR file may also be uncompressed using the JAR tool bundled with JAVA (jar.exe under Zindozs...). The command line should look something like: jar -xvf approximations.JAR

Once the sources and classes have been decompressed, an executable class can be run, within the approximations directory, by invoking the following command

java -cp . approximations.Simulation

Description and usage

The package includes the following executable classes: :

  • approximations.Simulation : Sofwtare GUI, allowing for basic tests by manually inputing the string to compress. Although a file can also be input through the interface, it is advisable to use the Calcul class to compress a file. Algorithms can be selected through checkboxes. The GUI can be spawned by an execution of the JAR archive, or through the command:
    java -cp . approximations.Simulation
  • approximations.Calcul : Command-line version of the software, allowing for a faster and more parsimonious execution. It can be invoked within a shell by a command similar to:
    java -cp . approximations.Calcul ...options... files
    where the options are -(L|LZ78) (ON|OFF), -(B|BISECTION) (ON|OFF), -(S|SEQUENTIAL) (ON|OFF) or -(G|GREEDY) (ON|OFF), activating/deactivating the various algorithms.
  • approximations.Shuffle : A command-line software which shuffles a text file including natural langage text, and outputs the results to the standard output. Commande Line:
    java -cp . approximations.Shuffle file