Go to Homepage     Learn about VB Encoding

Front Coding: Compressing Dictionary

 
                    Tokens: 

Terms (sorted and unique):

Dictionary as a string:

After Front Coding:

After Intelligent Front Coding(max block size = 4):

Comparison:




Step 1: Input is tokenized wrt white spaces.


Step 2: All the tokens are case-folded (converted to lower case) and sorted. Stop words and duplicates are removed.


Step 3: Each term, preceded with the corresponding term length is appended to construct "Dictionary as a String".


Step 4: The terms are classified into all but one block of size 'k'. Common prefix in these groups, if any is identified and delimited with special symbol '*'. The substring followed by this common prefix(preceded by their lengths and a special symbol '⬦') are appended.

Step 5: The blocks instead of depending on 'k' are formed on the basis of the longest prefix amongst them such that the block are of size at most 4.


Step 6: Efficiency of Compression in different approaches is compared. We make following assumptions:
• Trivially, the dictionary terms are stored as array entries each of size 20 bytes and we consider this as base standard to compare the efficiency of Compressions
• A pointer to term takes 2 bytes


Note:
In Front Coding, there is a pointer to each block instead of each term. Standard Front Coding takes the block size (k) as specified by the user.
However, intelligent split(wrt common prefixes) involves variable block size (at most 4)

Let's do one exercise!
Take the input text: She sells sea shells on the seashore
Block size: 3
Stop word list: the she by
Now calculate the number of bytes that will be consumed when stored as "Fixed array entries", "Dictionary as a String" and after "Front Coding"