CComp: Sıkıştırılmış kelime arama için paralel bir sıkıştırma algoritması
CComp: A parallel compression algorithm for compressed word search
Yazar: Öztürk, Emir; Mesut, Altan
Dergi: Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, Vol. 39 No. 3, 2022
Anahtar kelimeler: Engineering ; Mühendislik ; Compressed matching,Data compression,Parallel programming,Text compression ; Sıkıştırılmış arama,Veri sıkıştırma,Paralel programlama,Metin sıkıştırma

Üretilen verilerin saklamasında alandan tasarruf etmek önemlidir. Sıkıştırma algoritmaları bu tasarrufu sağlamak amacıyla kullanılmaktadır. Saklanmak istenen veri bir kere sıkıştırılmakta fakat üzerinde arama yapmak amacıyla defalarca erişilmektedir. Bu sebeple sıkıştırılmış verinin en büyük dezavantajı bu verinin kullanılmak istendiğinde açılması gerekliliğidir. Hızlı bir açma algoritması ile veya açma işlemine ihtiyaç duymayan bir sıkıştırılmış arama yönteminin kullanılması ile bu dezavantajlı durum giderebilir. Sıkıştırılmış arama hem arama uzayının küçük olması hem de açma yapmaması sayesinde aç-ve-ara yöntemlere göre daha hızlı sonuçlar elde edebilmektedir. Bu makalede sıkıştırılmış arama desteği sunan paralel yarı statik kelime tabanlı bir sıkıştırma algoritması olan CComp sunulmuştur. CComp’un amacı diğer paralel sıkıştırma algoritmalarının hızında sıkıştırma-açma ve daha hızlı sıkıştırılmış arama yapmaktır. CComp sıkıştırma, açma ve arama işlemlerini paralel olarak gerçekleştirmektedir. CComp diğer paralel yöntemler ile karşılaştırılmıştır. Sonuçlarda gösterildiği gibi CComp’un sıkıştırma oranları diğer kelime tabanlı algoritmalarla paralel sonuçlar vermektedir. Sıkıştırılmış arama işleminde ise daha önce en iyi sonucu veren Zstd algoritmasına göre yaklaşık 7 kat daha hızlı arama sonuçları elde edilmiştir.  Bu sonuçlar ile CComp sıkıştırılmış arama desteği sunan algoritmalara daha iyi bir alternatif olarak gösterilebilmektedir.

It is important to save space storing the generated data. To achieve this, compression algorithms are used. Stored data is compressed once but accessed many times to search on it. For this reason, the biggest disadvantage of compressed data is that it needs to be decompressed when it will be used. This disadvantage can be eliminated by using a fast decompression algorithm or a compressed search method that does not require decompression. Compressed search can achieve faster results than open-and-search methods, thanks to its small search space and not using decompression. In this article, CComp, a parallel semi-static word-based compression algorithm that supports compressed search, is presented. The purpose of CComp is to obtain faster search results while compressing-decompressing at the speed of other parallel compression algorithms. CComp performs these operations in parallel. CComp has been compared to other parallel methods. As shown in the results, the compression ratios of CComp give results in parallel with other word-based algorithms. In the compressed search process, results were obtained approximately 7 times faster than the Zstd algorithm, which gave the best results before. With these results, CComp can be shown as a better alternative to algorithms that support compressed search.