n-Gram-Based Text Compression

Vu H. Nguyen, Hien T. Nguyen, Hieu Ngoc Duong, Václav SnáselComput. Intell. Neurosci 2016 · DOI

TL;DR

This paper introduces a novel text compression method for Vietnamese that leverages n-gram dictionaries, achieving impressive compression ratios (up to 90%) by encoding sequences of characters based on their frequency. The method significantly outperforms existing techniques on Vietnamese text, offering a promising direction for language-specific compression.

What Problem Does This Paper Address?

Data compression is crucial for reducing storage space and increasing data transfer rates. While general-purpose compression algorithms exist, text compression, in particular, aims to exploit the inherent redundancies within natural language. These redundancies can occur at various levels: character, syllable, or word. Existing lossless text compression techniques often fall into categories like substitution, statistical, dictionary, or context-based methods. However, many of these methods, while effective, may not be optimally tailored for languages with specific linguistic structures, such as Vietnamese, which has a rich morphology. The authors identify a gap in applying n-gram dictionary-based compression specifically to Vietnamese text and aim to develop a method that achieves high compression ratios for this language.

Methods

The proposed method is an n-gram-based text compression technique that utilizes dictionaries of n-grams (sequences of n items). The core idea is to split the input text into n-grams and then encode them using pre-built dictionaries.

Here's a breakdown of the key components:

  • N-gram Dictionaries: The system builds five distinct dictionaries for unigrams (single characters), bigrams, trigrams, four-grams, and five-grams. These dictionaries are populated from a large corpus of Vietnamese text.
  • Sliding Window and Greedy Encoding: The compression process employs a sliding window approach. It attempts to match the longest possible n-gram (up to five grams) from the input text against the dictionaries. If a five-gram is found, it's encoded. If not, it tries a four-gram, and so on, down to unigrams. This greedy strategy aims to capture the most significant redundancies.
  • Encoding Scheme: Each n-gram found in a dictionary is encoded by an index. The encoding uses a fixed number of bytes, with the first three bits of the first byte indicating which n-gram dictionary was used (e.g., unigram, bigram, etc.). Subsequent bits store the index of the n-gram within that dictionary. Special codes are used for characters not found in any dictionary (e.g., newline).
  • Decompression: The decompression process reverses this by reading the encoded stream, interpreting the dictionary indicator bits, and then using the index to retrieve the original n-gram from the corresponding dictionary.

Datasets

  • Training/Dictionary Building: A 2.5 GB text corpus was collected from Vietnamese news agencies to build the n-gram dictionaries. This corpus was used to generate unigram through five-gram dictionaries, resulting in a total size of approximately 12 GB.
  • Testing: A separate testing set of 10 different text files, varying in size and content, was used to evaluate the method's performance.

Key Insights and Ideas

  • Leveraging Vietnamese Morphology: The paper highlights that n-gram-based compression, particularly with higher-order n-grams (like four and five grams), can effectively capture the sequential patterns and redundancies present in Vietnamese text, which might be missed by simpler character-level or word-level methods.
  • Dictionary Size vs. Compression Ratio: The study demonstrates a clear trend: as the order of n-grams in the dictionaries increases (from unigram to five-gram), the compression ratio generally improves. This suggests that longer sequences provide more context and thus more opportunities for efficient encoding.
  • Trade-off between Compression and Speed: While the method achieves excellent compression ratios, the experimental results indicate that compression and decompression times are higher compared to some established algorithms. This is a common trade-off in compression, where achieving higher compression often requires more computational effort.

Key Results

  • High Compression Ratios: The proposed n-gram-based method achieved compression ratios around 90% on the tested Vietnamese text files.
  • Outperforms Previous Methods: The method significantly outperformed the authors' previous work on Vietnamese text compression (based on syllable-based methods and trigrams) and also showed better compression ratios than general-purpose compressors like WinRAR and WinZIP on the same dataset.
  • Impact of N-gram Order: Combining all five n-gram dictionaries (unigram to five-gram) yielded the best compression ratios, indicating the benefit of using a wider range of n-gram contexts.

Limitations and Future Work

  • Computational Cost: The paper acknowledges that the compression and decompression times are higher than some other methods. This is attributed to the process of looking up n-grams in large dictionaries.
  • Future Work: The authors suggest that optimizing the dictionary lookup process could lead to faster execution times. This could involve exploring more efficient data structures or indexing techniques for the n-gram dictionaries. Further research into speeding up the lookup process is proposed as a future direction.

Summary updated

BibTeX
@article{nguyen2016n,
  author = {Vu H. Nguyen and Hien T. Nguyen and Hieu Ngoc Duong and Václav Snásel},
  title = {{n-Gram-Based Text Compression}},
  journal = {Comput. Intell. Neurosci.},
  year = {2016},
  doi = {10.1155/2016/9483646},
}
Figure