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

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

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,

PDF

___

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