Skip to content
Switch branches/tags

Latest commit


Git stats


Failed to load latest commit information.
Latest commit message
Commit time
This program computes Lempel Ziv(LZ77) factorization from input text,
which was made by Keisuke Goto, Hideo Bannai.
The original algorithm is proposed by Keisuke Goto and Hideo Bannai.
Details of the algorithm are available in
The souce code is hosted at .

All source codes are licensed by MIT License.
You can read the details in LICENSE file.

We partly use souce codes made by G. Nong and J. Karkkainen,
saca-k.cpp by G. Nong,
the reading_text function within bgCommon.cpp by J. Karkkainen
Their source codes are available at
and respectively.

Scons ( is used for the building process.
Just type "scons" if you have it installed.

-- Description

This package contains implementations of linear time algorithms computing
the Lempel Ziv(LZ77) factorization (also known as LZ77 parsing) from the paper

Keisuke Goto, Hideo Bannai:
Space Efficient Linear Time Lempel-Ziv Factorization for Small Alphabets. DCC 2014: 163-172

Implemented algorithms:

  BGone  - uses 5n bytes of space (assuming 32-bit integers and byte alphabet),
          This is the most space efficient algorithm.
  BGtwo  - uses 9n bytes of space. 

Given space requirements include the input text of n bytes but exclude the
output factorization.

-- Terms of use

If you use this code for experiments in a research paper, please cite the
paper mentioned above and publish the URL from which you downloaded the code.

-- How to use
See the help option, BGone -h or BGtwo -h.


Automatically exported from




No releases published


No packages published