Sıkıştırılmış metin veriler içinde dizgi eşleme algoritmalarının kullanılmasının incelenmesi ve yeni bir yaklaşımın geliştirilmesi
Studying of usage of pattern matching algorithms in compressed text data and developing a new approach
Yazar: HALİL NUSRET BULUŞ
Danışman: YRD. DOÇ. DR. AYDIN CARUS
Trakya Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2010
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Bu tezin amacı, sıkıştırılmış dizgi eşleme yapmaya uygun yeni bir sıkıştırma algoritmasının ve sıkıştırılmış dizgi eşleme yaklaşımının geliştirilmesidir. Ayrıca mevcut sıkıştırma algoritmaları ile sıkıştırılmış veriler üzerinde dizgi eşleme yapan çalışmaların araştırılarak, sıkıştırılmış dizgi eşleme yöntem ve yaklaşımlarının kullandıkları sıkıştırma algoritmalarına göre sınıflandırılması da yapılmıştır.Tezin birinci bölümünde, veri sıkıştırma, dizgi eşleme ve sıkıştırılmış dizgi eşleme konularından kısaca söz edilip, konular ile ilgili diğer genel terimlere açıklık getirilmiştir. Tezin ikinci bölümünde daha önceden üzerinde sıkıştırılmış dizgi eşleme yaklaşımı geliştirme çalışmaları yapılmış olan sıkıştırma algoritmaları ele alınmış ve bu algoritmaların örnekler ile açıklaması yapılmıştır. Tezin üçüncü bölümünde mevcut yapılmış olan sıkıştırılmış dizgi eşleme çalışmalarında kullanılmış olan dizgi eşleme yöntemleri ve yaklaşımları örneklerle açıklanmıştır. Tezin dördüncü bölümünde literatürde yer alan sıkıştırılmış dizgi eşleme çalışmaları ayrıntılı bir şekilde incelenmiştir. Tezin beşinci bölümünde, yeni geliştirilen sıkıştırılmış dizgi eşlemeye elverişli veri sıkıştırma algoritması ve bu algoritma için sıkıştırılmış dizgi eşleme yaklaşımı ayrıntılı olarak ele alınmıştır. Altıncı bölümde geliştirilmiş olan sıkıştırma algoritması ile mevcut diğer ilgili sıkıştırma algoritmalarının sıkıştırma oranları, sıkıştırma ve açma süreleri kıyaslanmıştır. Ayrıca mevcut bilinen külliyatlardan da yararlanılarak İngilizce ve Türkçe külliyatlar oluşturulmuştur. Bu külliyatlar üzerinde, geliştirilen sıkıştırılmış dizgi eşleme yaklaşımı ile diğer mevcut sıkıştırılmış dizgi eşleme yaklaşımlarının, dizgi eşleme süreleri bakımından kıyaslamaları yapılmıştır.

Abstract:
The purpose of this thesis is developing a new compression algorithm appropriate for compressed pattern matching and developing a new approach to compressed pattern matching. In addition to this, explanations of current compression algorithms and compressed pattern matching studies, the classification of compressed pattern matching methods and approaches according to the used compression algorithms take place in this thesis.In the first chapter of this thesis, data compression, pattern matching and compressed pattern matching subjects are briefly explained and the definitions of the other terms related to these subjects are given. In the second chapter, compression algorithms which are studied previously in compressed pattern matching area are given and the explanation of these algorithms with examples are made. In the third chapter, pattern matching methods and approaches that are used in current compressed pattern matching studies are explained with some examples. In the fourth chapter, the compressed pattern matching studies in the literature are explained in details. In the fifth chapter, the new developed compression algorithm appropriate for compressed pattern matching and the compressed pattern matching approach for this compression algorithm are explained in details. In the sixth chapter, the compression ratios, compression and decompression times of the developed algorithm and current related algorithms are compared. In addition to this English and Turkish corpuses are made from well known corpuses. On these new corpuses, the developed compressed pattern matching approach and the current compressed pattern matching approaches are compared in compressed pattern matching times.