Improved Repeat Selection

• GNU gzip v1.2.4 uses a heuristic modification of a greedy repeat selection.

• The improved algorithm uses a dynamic programming (DP) algorithm to find an optimal covering of repeats that minimizes the final block length.

• The improved algorithm also evaluates non-maximal repeats and even different offsets.

Previous slide

Next slide

Back to first slide

View graphic version