METİN VERİLERDE DİZGİ EŞLEME VE SIKIŞTIRILMIŞ DİZGİ EŞLEME İŞLEMLERİ ARASINDAKİ PERFORMANS FARKLARININ İNCELENMESİ

Yıl 2016, Cilt: 6 Sayı: 3, 60 - 76, 20.12.2016

Nusret Buluş Cihat Erdoğan Banu Diri

Öz

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

EVALUATION OF THE PATTERN MATCHING PERFORMANCE OF COMPRESSED AND UNCOMPRESSED TEXTS

Öz

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.

Anahtar Kelimeler

Data compression, Pattern matching, Compressed pattern matching, Pattern substitution

Kaynakça

• Amir, A., & Benson, C. (1992). Efficient two-dimensional compressed matching. In Data Compression Conference, 1992. DCC ’92. (pp. 279–288). http://doi.org/10.1109/DCC.1992.227453
• Amir, A., Benson, G., & Farach, M. (1996). Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files. Journal of Computer and System Sciences, 52(23), 299–307. http://doi.org/DOI: 10.1006/jcss.1996.0023
• Boyer, R. S., & Moore, J. S. (1977). A Fast String Searching Algorithm. Commun. ACM, 20(10), 762–772. http://doi.org/10.1145/359842.359859 Crochemore, M., & Rytter, W. (2002). Jewels of Stringology: Text Algorithms. Hackensack, NJ, USA: World Scientific. Retrieved from http://www.amazon.com/exec/obidos/redirect?tag=citeulike07-20&path=ASIN/9810248970
• Farach, M., & Thorup, M. (1998). String Matching in Lempel—Ziv Compressed Strings. Algorithmica, 20(4), 388–404. http://doi.org/10.1007/PL00009202
• Gasieniec, L., & Rytter, W. (1999). Almost-optimal fully LZW-compressed pattern matching. In Data Compression Conference, 1999. Proceedings. DCC ’99 (pp. 316–325). http://doi.org/10.1109/DCC.1999.755681
• Kärkkäinen, J., Navarro, G., & Ukkonen, E. (2003). Approximate string matching on Ziv-Lempel compressed text. Journal of Discrete Algorithms, 1(3–4), 313–338. http://doi.org/10.1016/S1570-8667(03)00032-7
• Kida, T., Takeda, M., Shinohara, A., & Arikawa, S. (1999). Shift-and approach to pattern matching in LZW compressed text. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1645, 1–13. http://doi.org/10.1007/3-540-48452-3_1
• Klein, S. T., & Shapira, D. (2002). A new compression method for compressed matching. Data Compression Conference, 2000. Proceedings. DCC 2000, 400–409. http://doi.org/10.1109/DCC.2000.838180
• Manber, U. (1997). A Text Compression Scheme That Allows Fast Searching Directly in the Compressed File. ACM Trans. Inf. Syst., 15(2), 124–136. http://doi.org/10.1145/248625.248639
• Moura, E. S. De, Navarro, G., Ziviani, N., & Baeza-Yates, R. (1998). Direct pattern matching on compressed text. Proceedings. String Processing and Information Retrieval: A South American Symposium (Cat. No.98EX207). http://doi.org/10.1109/SPIRE.1998.712987
• Navarro, G., & Raffinot, M. (1999). A general practical approach to pattern matching over ziv-lempel compressed text. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1645, 14–36. http://doi.org/10.1007/3-540-48452-3_2
• Salomon, D. (2006). Data Compression: The Complete Reference. Secaucus, NJ, USA: Springer-Verlag New York, Inc.
• Shannon, C. E. (1948). A mathematical theory of communication. The Bell System Technical Journal, 27(July 1928), 379–423. http://doi.org/10.1145/584091.584093
• Shibata, Y., Kida, T., Fukamachi, S., Takeda, M., Shinohara, A., Shinohara, T., & Arikawa, S. (2000). Speeding up pattern matching by text compression. Algorithms and Complexity, 306–315. http://doi.org/10.1007/3-540-46521-9