www.data-compression.info
The Data Compression Resource on the Internet

Contents

 Weigthed Frequency Count (WFC)


The Weigthed Frequency Count algorithm (WFC) was introduced in 2001 by Sebastian Deorowicz. WFC is a replacement of the Move To Front stage (MTF) within the Burrows-Wheeler Compression Algorithm and is a representative of a List Update Algorithm (LUS) just like MTF.
In contrast to MTF the WFC algorithm takes former symbol distribution into acount by using a weighting scheme for former symbol occurences. The WFC stage needs no additional overhead like the IF stage and leads to good compression rates in the BWT field. The main disadvantage of the WFC stage is the time consumption for the calculation of the weighting scheme.

 Publications


Logo

Title

Description

Second step algorithms in the Burrows-Wheeler compression algorithm

Second step algorithms in the Burrows-Wheeler compression algorithm
 

This publication of Sebastian Deorowicz in "Software-Practice and Experience" from 2002 give a quite complete overview of the post BWT stages used within the Burrows-Wheeler Compression Algorithm. Besides his own Weighted Frequency Count Algorithm and other post BWT stages, Sebastian describes briefly but clearly variantions of the Move To Front scheme, the Inversion Frequencies algorithm and the Distance Coding algorithm with the 3 properties of the newsgroup posting. This is one of my favourite BWCA papers.
This BWCA approach achieves a compression rate of 2.25 bps for the Calgary Corpus.
 

An analysis of the second step algorithms in the Burrows-Wheeler compression algorithm

An analysis of the second step algorithms in the Burrows-Wheeler compression algorithm
 

A  quite similar publication from 2000 to the article "Second step algorithms in the Burrows-Wheeler compression algorithm" from Sebastian Deorowicz, describing his Weighted Frequency Count Algorithm.
This BWCA approach achieves a compression rate of 2.25 bps for the Calgary Corpus.
 

Universal lossless data compression algorithms

Universal lossless data compression algorithms
 

The disseration of Sebastian Deorowicz concerns universal lossless data compression algorithms such as LZ, PPM, and BWCA methods. A new algorithm based on the Burrows–Wheeler transform is proposed.
Its most important features are improved Itoh–Tanaka method for computing BWT, Weighted Frequency Count transform (instead of the MTF), and weighted probability estimation. The performance of the algorithm is evaluated on the Calgary and Silesia corpora.
 

 People


Logo

Name

Description

Sebastian Deorowicz

Sebastian Deorowicz
 

Sebastian is the author of the Weigthed Frequency Count algorithm (WFC) and an Assistant Professor of the Silesian University of Technology, Poland.
 

 Source Code


Logo

Title

Description

 

Copyright © 2002-2022 Dr.-Ing. Jürgen Abel, Lechstraße 1, 41469 Neuß, Germany. All rights reserved.