Kayıpsız Metin Sıkıştırma

Kayıpsız Metin Sıkıştırma Araştırmamın Türkçesinin PDF’ine erişmek için tıklayınız.

Please click for the PDF file of Lossless Text Compression Research in English

Kayıpsız metin sıkıştırma bilindiği gibi belirli döngülerde metnin içinde rastlanan kelimelerin yerine onlara göre hafızada daha az yer tutan eşdeğerlerinin değiştirilmesiyle mümkün olan bir yöntemdir. Huffman Coding bu konuda örnek verebileceğimiz kayıpsız sıkıştırma algoritmalardan bir tanesidir. En çok tekrar edilen (frekansı fazla olan) harfe en kısa bit uzunluğunu vermeyi amaçlar. Bu algoritmayla çok yüksek miktarda sıkıştırma yapılabilmektedir ancak sıkıştırma işleminin geriye alınması işleminde sıkıştırılma anındaki sözlüğün (harfler ve onların frekanslarının) bilinmesi gerekmektedir. Bu durumda da örneğin aynı veri tabanındaki verilerde sonradan eklenenlerle beraber sürekli tekrar bir sıkıştırma işlemi uygulanması gerekmektedir çünkü sözlük sonradan eklenen metinle değişecektir. Dünyada da ihtiyaçlara binaen birçok veri sıkıştırma algoritması bulunmaktadır. Bunların en bilinen örnekleri gzip (deflate algoritması), LZ77, LZ78, Shannon-Fano, Brotli gibi sıkıştırma yöntemleridir.[1]

Ön Fikirler

            İlk olarak yapmayı hedeflediğim çalışma sadece metnin ne oranda sıkıştırıldığını değil aynı zamanda sıkıştırılma (compression) ve açılma (decompression) sürelerini, veri tabanı formatının korunması ve sözlükte olabildiğince az içeriğin bulunması gibi faktörleri göz önünde bulunduracaktır. Bir sıkıştırma algoritmasının temel hedefi sıkıştırma oranının ve sıkıştırılma süresinin optimal düzeyde tutulmasıdır. Ancak ben daha veri tabanı şeklinde bir içerik kullanmayı hedeflediğim için bazı diğer etkenlerden de çalışmada yararlanacağım. Burada veri tabanından kastım spesifik bir veri tabanı değil (SQL, NoSQL vs.), kayıtların belirli bir format çerçevesinde tutulduğu herhangi bir veri saklama yapısı.

Bir metin sıkıştırma algoritmasının en temel görevi içerikteki bazı kısımları oldukları uzunluktan daha kısa bir biçimde yazmayı sağlamak. Bunu da metin içinde sıklıkla rastlanılan ya da rastlanılma ihtimali yüksek olan içeriklere spesifik değerler vererek yapabiliriz. Örneğin Huffman Coding algoritmasını kullanarak “ankara” kelimesini sıkıştırdığımızda a harfi 3 kez tekrarlandığı için a harfine verilebilecek en kısa bit karşılığını vermemiz gerekir. Burada a harfi yerine (0), n ve k yerine (110 ve 111), r yerine ise (10) getirirsek Huffman algoritmasıyla sıkıştırmamızı tamamlamış oluruz. Normalde 48 bitle ifade ettiğimiz kelimeyi (6*8) Huffman algoritması yardımıyla sadece 11 bitle ifade edebiliriz (01101110100).

Türe Bağlı Sıkıştırma Algoritması

Öncelikle bir kullanıcı veri tabanının isim ve soy isim bölümünü ele alalım. İlk olarak ideal koşullar altında oluşabilecek bir örneğe bakalım. Bu veri tabanını bir txt dosyası formatında oluşturalım ve yeni satır karakteri “\n” bizim için yeni bir satırı (girdiyi) ve boşluk karakterinin de “ “ o girdinin bir sonraki sütununu belirten karakterler olduğunu varsayalım. Türkçede genel olarak ad ve soyadların 1 veya 2 isim ve 1 soy isimden oluştuğunu söyleyebiliriz. X Y Z veya X Z şeklinde düşünürsek X ve Y burada isim, Z’nin de soy isim olduğunu görürüz ve örnek veri tabanımız şu şekilde oluşur: X Y Z\nX Y Z\nX Y Z\n . Bunun gösterimi ise şu şekilde olur:

X Y Z

X Y Z

X Y Z

Buradaki yapıyı şu şekilde düşünebiliriz; son sütun soy ismi belirtiyor kalan sütunlar (genellikle 1 ya da 2) ise isimleri belirtiyor. Türkiye’de 2019 yılı verilerine göre en çok kullanılan 3 erkek ve 3 kadın isminin toplamda yaklaşık 83 milyonluk nüfusun 12.8 milyonuna karşılık geldiğini görüyoruz.[2] Burada sözlüğe her ismi eklememiz mümkün değil ancak nüfusun çok büyük bir bölümünü kapsayan isimleri eklememiz mümkün ve bunları sadece 2 bayt şeklinde ifade edersek (2 karakterle) bir sıkıştırma işlemi uygulamış oluyoruz. İdeal koşullarda yani her bir ismin sözlükte ekli olduğu ama hiçbir soyadın bu isimlerden birini herhangi bir kısmında içermediği bir durumda rastgele üretilen isim ve soy isim kombinasyonlarıyla yaptığım denemenin sonuçları:

İşlenmemiş metin boyutu	Sıkıştırıldıktan sonraki boyut	LZW[3] ile sıkıştırıldıktan sonraki boyut	Sıkıştırılma oranı	LZW ile sıkıştırılma oranı
4.32 KB	2.41 KB	2.40 KB	1.7926	1.8060
8.59 KB	4.81 KB	4.19 KB	1.7859	2.0501
17.15 KB	9.58 KB	7.23 KB	1.7900	2.3753

 

Sıkıştırılma Oranı = İlk Halindeki Boyut / Son Halindeki Boyut

Benim geliştirdiğim algoritmada oranın yaklaşık olarak çoğu boyutta 1.79 kalmasının temel nedeni rastgele oluşturulan veri tabanındaki isimlerin sözlükte olması, soy isimlerin olmaması ve veri yapısının bozulmadan korunması. Buna şu şekilde örnek verebiliriz:

X Y Z

H F T

Şeklinde iki adet verimiz olduğunu düşünürsek yapılan sıkıştırma işlemi sonrasında benim geliştirdiğim algoritmada çıkan sonuç:

N M Z~K L T

Şeklinde olacaktır. Burada N ve M, X ve Y’nin onlara göre daha kısa olan karşılıkları, K ve L ise H ve F’nin onlara göre daha kısa olan karşılıkları olmakta, ~ ise yeni satır karakterinin yerine geçecek özel karakteri temsil ediyor. Bu durumda dosyalarda boyut büyümesine rağmen benim kullandığım algoritmada sıkıştırma oranının artmadığı ve bu veri setinde yaklaşık 1.79 bir oran çıkardığını görmüş olduk ama veri yapısı ise korunmuş oldu. Buradan şu sonuca ulaşabiliriz: üstteki örnekte eğer 2.satırdaki veriyi istiyorsak (H F T) yapmamız gereken ilk özel karakterle (~) varsa (yoksa içeriğin sonuna kadar) ikinci özel karakter arasındaki veriyi alıp decompression (açma) işlemi uygulamak, aynı şekilde eğer tüm veri tabanını LZW ile sıkıştırmış olsaydık her seferinde tüm veri tabanını decompress edip sonra istenen satırdaki veriyi alırdık ya da her satırı ayrı ayrı LZW ile sıkıştırmış olsaydık satır bazında direkt decompression yapabilirdik ancak bu da verimli bir sıkıştırma olmazdı (Ek 1.). Kullandığım algoritmada ise istenen satırı alıp direkt onu decompress etmiş oluyoruz. Bu örnekte benim algoritmam şu an sadece isim türüne odaklanmış durumda ve sıkıştırılmak istenilen her bir tür için tekrar bir veri seti oluşturulmalı. Bu set oluşturulurken kullanım sıklıkları göz önünde bulundurulmalıdır.

Bu durumda kullandığım türe bağlı sıkıştırma algoritmasının dezavantajları:

• Sıkıştırma oranının yüksek olmaması
• Duyarlılığının yüksek olması (örneğin yanlış girilecek bir isimde o ismi dönüştürmeyecek olması)
• Rakam içermeyen veri tabanları için sözlük maksimum 10*256=2560 tane eşdeğer alabilir. Rakam içerenler içinse 2 karakter için 256 adet eşdeğer olabilir.

Avantajlı yanı olarak ise

• Veri formatı korunduğu için direkt istenen satır alınarak sadece ona uygulanacak bir decompression işlemiyle veri elde edilebilir.
• Compression (sıkıştırma) işleminin hızlı tamamlanması çünkü sadece sözlükteki kelimeler ya da eklerin karşılıklarını değiştirmesi.

Türe bağlı sıkıştırma algoritmasının önemli konularından biri kelime ya da ekler için eşdeğer seçimidir. Bu konu için de başka bir algoritma gerekmektedir. Örneğin bir haber sitesindeki içerikler ele alındığı zaman, o haber sitesinde daha önce yayımlanmış haberlerin içerisindeki kelime frekansları analiz edilmelidir. Ama bu konuda dikkat edilmesi gereken nokta dönemsel artış eğilimi gösteren durumlardır. Örneğin ABD başkanının 4 yılda bir seçildiğini düşünürsek önceki ABD başkanıyla ilgili haber sayısı şimdikiyle ilgili olandan daha fazladır, ama gelecekte yayımlanacak yeni haberlerde şimdiki ABD başkanının isminin geçme ihtimali daha yüksektir. Bu yüzden sıkıştırma algoritmasında şimdiki ABD başkanına da yer verilmesi gerekmektedir. Bu tarz durumlara da sözlük oluşturulurken dikkat edilmesi gerekmektedir.

Durum Senaryoları

Bir başka örnek durum ise kimlik numaralarıdır. Bilindiği gibi Türkiye Cumhuriyeti’ndeki her bir kişinin 11 haneli T.C. kimlik numarası bulunmaktadır. Eğer ki veri tabanımızda kişilerin T.C. kimlik numaralarının saklandığı bir bölüm varsa bu bölümdeki verileri, veri başına 11 bayttan 5 bayta kadar düşürebiliriz. Bunun için rakamların kombinasyonlarını sözlüğe eklememiz gerekiyor. Bu sıkıştırma tipinde LZW algoritmasına göre daha çok oranda sıkıştırma yapmış oluyoruz.

Başka bir durum ise plaka veri tabanını örnek verebiliriz. Türkiye’de 7 veya 8 haneli olduğu için plaka kodları (00ABC000) gerekli sözlüğü ve değiştirmeleri hazırlayarak 7 haneli plaka için 7 bayttan 4 bayta düşürebiliriz. 8 haneli plakalar içinse 8 bayttan 5 bayta düşürebiliriz. Bu sıkıştırma türünde LZW algoritmasına göre daha çok oranda sıkıştırma yapmış oluyoruz. (Ek 2.)

Son

Türe bağlı sıkıştırma algoritmasının kullanılabileceği alanlar genel olarak önceden verilerin içeriğindeki sık kullanılan kısımları tahmin edilebilir olan veri türleri (örneğin: şehir isimleri, insan isimleri, belirli ürün isimleri, plakalar, T.C. kimlik numaraları vs.). Ayrıca online oyun gibi hızlı bir şekilde sunucuyla kullanıcının hızlı bir şekilde veri aktarımı yapması gereken alanlardaki verilerde kullanılabilir olduğunu düşünüyorum. Ayrıca gerekli yüksek sıkıştırma gereken durumlarda LZW ile ya da diğer benzer algoritmalar ile beraber kullanımı düşünülebilir.

Ekler

1.

Satır içeriği	Orijinal (bit)	LZW ile sıkıştırıldıktan sonra (bit)	Sıkıştırma oranı (orijinal/sıkıştırılmış)
Ankara Istanbul 600	160	140	1.14
Ankara Bolu 400	128	112	1.14
Ankara Kirsehir 350	160	152	1.05
Istanbul Izmir 400	144	126	1.14

Eğer direkt olarak bu 3 satırı sıkıştırsaydık, sıkıştırma oranı: 1.3214

2.

Plaka	Gerçek Boyut	TBSA ile sıkıştırılmış	LZW ile sıkıştırılmış
82ABC888	64 bit	40 bit (fazladan 3 bit eklenmiştir)	56 bit
93CB753	56 bit	32 bit	49 bit

 

Anahtar Kelimeler

Yazı sıkıştırma, sıkıştırma algoritmaları, türe bağlı sıkıştırma algoritması, TBSA, veri tabanı sıkıştırma

Kaynaklar

[1] Kayıpsız Sıkıştırma Algoritmaları Hakkında Karşılaştırmalı Detaylı Bilgi (http://mattmahoney.net/dc/text.html)

[2] https://www.ensonhaber.com/ic-haber/icisleri-bakanligi-2019-yili-dogum-ve-isim-istatistikleri

[3] Lempel–Ziv–Welch

İletişim

onur@bilalonureskili.com