M188: A New Preprocessor for Better Compression of Text and Transcription Files

Abstract

ABSTRACT: Compression of natural language text files is worthwhile for communities such as Project Gutenberg in terms of their storage space and even for text messaging applications' bandwidth efficiency. Thus, there has been extensive research on preprocessing techniques. The thesis proposes a new word-based preprocessor named METEHAN188 (M188). The proposed method provides better compression of text and transcription files when concatenated with some well known data compression algorithms. M188 and state-of-the-art preprocessors; starNT, WRT, ETDC, SCDC and RPBC are compared while concatenated with PPMD and PPMonstr. M188 differs from the other methods; it has larger dictionary which provides coverage of more words, the disadvantage is that it slows down the process; it has longer alphabet which gives M188 the opportunity of assigning shorter codewords; it does not code space and punctuation characters which speeds up M188 also output a more predictable scheme. During experiments, Wall Street Journal, Calgary, Canterbury, Large, Gutenberg and Pizza & Chili corpora are used. For the files in Calgary corpus the experimental results yield that M188 can overcome all other preprocessing techniques in terms of compression effectiveness. For the files selected from the project Gutenberg and Canterbury corpora WRT+PPMonstr has 1.22% gain in over M188+PPMonstr on the average. The results showed that best two preprocessors for compression effectiveness are M188 and WRT and for timing performance ETDC and SCDC are the fastest preprocessors. Keywords: LIPT, StarNT, WRT, Universal Preprocessor, PPMonstr, M188, ETDC, SCDC, RPBC, PPM, Data Compression.

………………………………………………………………………………………………………………………… ÖZ: Gutenberg projesi gibi toplulukların veri depolama alanlarını ve hatta metin mesajlaşma uygulamalarının bant genişliğini kazanımı için metin sıkıştırma kayda değer bir uygulamadır, araştırmalar önişlemcilerin kayda değer kazanç sağladığını göstermiştir. İş bu tez, metin dosyaları için sıkıştırılma oranını en iyileştirmeye yönelik yeni bir önişlemciyi önermektedir. Bu önişlemciyi Metehan 188 ya da M188 olarak adlandırmış bulunuyorum. M188 ile LIPT, StarNT, WRT, ETDC, SCDC, RPBC önişlemcileri PPMonstr ve PPMD sıkıştırma algoritmalarına önişlem yapacak şekilde kullanılmış daha sonrasında zaman ve sıkıştırma başarımı açısından kıyaslanmıştır. Diğer metotlara göre; M188 daha büyük bir sözlüğe sahiptir bu da kodlama kapsamını genişletmiştir; ayrıca, M188 kodlarını daha uzun bir alfabeden yararlanarak yaratmaktadır, bu sayede daha kısa kodlar atayabilmektedir. Son olarak M188 boşluk ve noktalama işaretlerini kodlamamaktadır bu da zamanlamada kazanç sağlamakta olup sıkıştırma algoritmalarına daha tahmin edilebilir bir yapı sağlamaktadır. Deneylerde; Wall Street Journal, Calgary, Canterbury, Large, Gutenberg ve Pizza & Chili metin derlemelerinden alınan dosyalar kullanılmıştır. Calgary dosyalarında M188 diğer tüm önişlemcilerden daha iyi sıkıştırma sağlamıştır. Gutenberg ve Canterbury dosyalarında ise WRT+PPMonstr ikilisi M188+PPMonstr 'ye göre yüzde 1.22 daha iyi sıkıştırma başarımı sağlamıştır. Sonuç olarak sıkıştırma başarımları en iyi olan iki algoritma M188 ve WRT olarak belirlenmiştir. En hızlı iki algoritma ise ETDC ve SCDC olarak belirlenmiştir. Anahtar Kelimeler: LIPT, StarNT, WRT, Evrensel Önişlemci, PPMonstr, M188, ETDC, SCDC, RPBC, PPM, Veri Sıkıştırma.