Evaluation of the Pattern Matching Performance of Compressed and Uncompressed Text


Buluş N. H., Erdoğan C., Diri B.

Electronic Journal of Vocational Colleges, cilt.6, sa.3, ss.60-76, 2016 (Hakemli Dergi)

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 6 Sayı: 3
  • Basım Tarihi: 2016
  • Dergi Adı: Electronic Journal of Vocational Colleges
  • Derginin Tarandığı İndeksler: Index Copernicus
  • Sayfa Sayıları: ss.60-76
  • Yıldız Teknik Üniversitesi Adresli: Evet

Özet

ÖZET Bu çalışmada metin veriler üzerinde yapılmakta olan dizgi eşleme işlemi istatistikleri ile aynı veriler üzerinde gerçekleştirilen sıkıştırılmış dizgi eşleme işlemi istatistikleri karşılaştırılmıştır. Bu kıyaslamayı yapmak için daha önce geliştirdiğimiz bir uygulama* iyileştirilmiştir ve test sonuçları bu uygulama sayesinde elde edilmiştir. Çalışmanın amacına uygun olarak literatürde mevcut dizgi eşleme algoritmalarının üzerinde herhangi bir değişiklik yapılmadan, sıkıştırılmış dizgi eşlemede de kullanılabilmesini sağlayan bir sıkıştırma yöntemi de sunulmuştur. Yapılan testlerde ikili ve üçlü kodlamaya dayanan sıkıştırma algoritması %30-%35 arası bir sıkıştırma faktörü sunarken, elde edilen sıkıştırılmış dizgi eşleme süresi, sıkıştırılmamış metin üzerinde yapılan dizgi eşleme süresinden daha düşük olarak bulunmuştur. Ayrıca, dizgi eşleme yaparken gerçekleştirilen karakter karşılaştırma sayılarının sıkıştırılmış metinde, sıkıştırılmamış metne göre daha az olduğu saptanmıştır. Dolayısıyla geliştirilen algoritmanın amacı yüksek sıkıştırma oranı sağlamak yerine, sıkıştırılmış dosya ile sıkıştırılmamış dosya arasındaki metin işleme süreleri farklarına dikkat çekmek ve başka uygulamalar için bir fikir oluşturmaktır. Ayrıca, üretilen algoritma üzerinde bazı değişiklikler yapılarak sıkıştırma oranlarının %5 gibi iyileşmesi sağlanmış ve algoritmanın yeni hali çalışmada verilmiştir. Anahtar Kelimeler: Veri sıkıştırma, Dizgi eşleştirme, Sıkıştırılmış dizgi eşleştirme, Dizgi değiştirme

ABSTRACT In this study, statistics of the pattern matching on an un/compressed form of the same text data are compared. In order to achieve this goal, a previously developed* application was improved. This modified application provided the test results of this study. The purpose of the study is presenting a compression method that can be used in compressed pattern matching without any changes on pattern matching algorithms which are previously studied in the literature. During the tests, the digram and trigram encoding based compression algorithm has provided a compression factor between 30-35%, and the as-obtained compressed pattern matching duration on the compressed text is calculated less than the one on the uncompressed text. In addition, it is confirmed that the total number of character comparisons on the compressed text matching is less than the one on the uncompressed texts. Therefore, the purpose of the as-developed algorithm is to draw attention to the pattern matching process time difference between the compressed and uncompressed text, instead of providing a high compression ratio. Besides, the aim of the study is to lead prospective pattern matching applications based on the points captured in this work. In addition, the changes made to the algorithm have increased the compression ratio by 5% and the new version of the algorithm is also explained in this study. Keywords: Data compression, Pattern matching, Compressed pattern matching, Pattern substitution