How to compress a list of sorted words?
algorithm, compression
Solution
You seem to be thinking of something like front compression, where each entry is a count of the number of leftmost characters which the entry shares with the preceding entry followed by the remaining, unshared characters. Example using your data:
0, ABAISSAT
8, ES
6, E
7, E
etc.
The result would still need gzipping (or other compression).
Problem
I have a large file with a single word per line. The entire file is sorted and I now need to compress it. I could simply use GZIP and the result would be pretty good. However I am wondering if it is possible to do better knowing that we are dealing with a list of sorted words. Here's a snippet of my list of sorted words: ``` [...] ABAISSAT ABAISSATES ABAISSE ABAISSEE ABAISSEES ABAISSEMENT ABAISSEMENTS ABAISSENT ABAISSER ABAISSERA ABAISSERAI ABAISSERAIENT ABAISSERAIS [...] ``` Would compressing the file using prefixes give a better results then GZIP? ``` [...] ABAISS AT ATES E EE EES EMENT EMENTS ENT ER ERA ERAI ERAIENT ERAIS [...] ``` What is the algoritm that would allow me to compress my list of words using the sort of compression I am describing? Any other idea how I could compress the data? P.S. I though about using a Trie and I implemented it. The final size of the Trie is memory was almost as large as the list itself and the time to load the list was very high. For these reasons I decided to no go that path.