24 October 2007

Dictionary Compressing

Aşağıda, "Veri Sıkıştırma" ile yapmış olduğum örnek bir uygulama bulunuyor. Bu konu ile ilgilenenler için örnek olacağını düşünüyorum:

1.Konu

Verilen bir sözlüğün sıkıştırılma işlemi yapılacaktır.

Alfabeden örnek bir kesit

aba    
aba      
abacılık   
abadi      
abajur     
abajurcu   

Sıkıştırma sonucunda elde edilecek kesit:

aba    
3cı    
5lık   
3di    
3jur   
6cu    

Alfabe içinde ses olaylarından dolayı oluşmuş tekrarlı kayıtların temizlenmesi de yapılacaktır.

Tekrarlı kayıt örneği

abartmacılığ    
abartmacılık 

Silinmesi gereken kayıt

abartmacılığ

Bu ve buna benzer tekrarlar aşağıda belirtilen harflerin yumuşama olayı ile elde edilmişlerdir.

k à ğ
ç à c
p à b
t à d

Yapılan sıkıştırma işleminin analizi yapılacaktır.

2. Uygulama İçin Kullanılacak Yöntem ve Araçlar

Yapılması istenen sıkıştırma işlemi, verilerden oluştuğu için, bu verilerin bir veritabanına aktarılıp oradan işlenmesinin daha uygun olacağı varsayılmıştır. Kullanılacak veri tabanı yönetim sisteminin kendine has veriye erişim yöntemleri ile daha performanslı bir sıkıştırma işlemi yapılacaktır.

Veritabanı yönetim sistemi oalarak Oracle kullnılacaktır. Oracle ile bütünleşik gelen SQL*Plus adlı metin tabanlı dosyaların veritabanı yüklenmesini sağlayan bir araçtan yararlanılacaktır. Sıkıştırma işlemi için ise Oracle ile bütünleşik gelen programlama dili PL/SQL olacaktır.


3. Verileri Okuma

Sözlük, txt uzantılı bir dosyada bulunmaktadır. Bu dosya yapısı gereği, her satırda bir harf olacak şekilde sıralı bir şekilde bulunmaktadır. Oracle içinde sözlüğü tutacak bir tablo oluşturulmalıdır. Bunun oluşturulabilmesi için aşağıdaki SQL cümlesi çalıştırılmalıdır:

create table dict
(
  row_number      number,
  original_word   varchar2(32)
);

Oracle ile bütünleşik gelen SQL*Plus aracı ile veriler tabloya yüklenecektir. Bu nedenle SQL*Plus in anlayabileceği bir dilde kontrol dosyası oluşturulur:

LOAD DATA

--Input file name
INFILE 'tr-sozluk.txt'

--bad records put into
BADFILE  'dict_bad.dat'

--discarded records put into
DISCARDFILE 'dict_discarded.dat'

--truncate existing records
TRUNCATE

--add data to table
INTO TABLE dict

--every column is distinguished by "" caharacter
FIELDS TERMINATED BY ""

(
     --like a sequence, inc one-by-one
     row_number RECNUM,
     --replace TAB char and TRIM
     original_word "TRIM(REPLACE(original_word,CHR(9)))"
)

Yukarıdaki konfügrasyon dosyası ile veriler okunup veritabanında bulunan tabloya atılır. Bu işlem için komut satırına aşağıdaki komut yazılmalıdır:

> sqlldr userid=username/password@database control=dict.ctl log=dict.log

Buradaki ;
  • userid=username/password@database; kısmı bağlantı bilgilerini
  • control=dict.ctl; yukarıda oluşturulan kontrol dosyası bilgilerini
  • log=dict.log; log dosyası bilgilerini

tutmaktadır. Yukarıdaki işlem sonucunda dosyada bulunan 49756 kayıt, veritabanına aktarılır.


4. Ön İşleme

Kullanılacak Türkçe sözlükte giriş kısmında da belirtildiği üzere tekrarlı kayıtlar bulunmaktadır. Bu kayıtların silinmesi için aşağıdaki SQL cümleleri çalıştırılmalıdır

DELETE FROM dict WHERE original_word IS NULL;

Yukarıdaki işlem sonucunda boş olan 4 satır silinir.


DELETE FROM dict
 WHERE original_word IN
       (SELECT substr(original_word, 1, length(original_word) - 1) ||
                decode(substr(original_word, -1, 1),
                       'ç',
                       'c',
                       'p',
                       'b',
                       'k',
                       'ğ',
                       't',
                       'd')
          FROM dict
         WHERE substr(original_word, -1, 1) IN ('ç', 'p', 'k', 't'));

Yukarıdaki işlem sonucunda mükerrer olan 8360 satır silinir.


Toplamda 8364 kayıt silinir. İşlenecek kayıt sayısı 42392 olarak kalır.

5.   Sıkıştırma İşleminin Yapılması

Veritabanına yüklenen kelimeler sözlük sırasına göre artan sıralama ile sıralanır. Her kelime, bir sonraki kelime ile karşılaştırılarak sıkıştırma işlemi yapılır. Aşağıdaki sorgu ile bu algoritma çalıştırılır.


SELECT curr AS original_word,
       decode(MAX(lev), 0, '', MAX(lev)) || substr(curr, MAX(lev) + 1) AS compressed_word
  FROM (SELECT *
           FROM (SELECT a.curr, a.prev, b.lev,
                         lag(b.lev, 1, 0) over(ORDER BY a.curr, a.prev, b.lev) - b.lev AS diff
                    FROM (SELECT curr, prev,
                                  least(length(curr), length(prev)) AS min_len
                             FROM (SELECT w AS curr,
                                           lag(w, 1, ' ') over(ORDER BY w) AS prev
                                      FROM (SELECT original_word AS w FROM dict))) a,
                         (SELECT LEVEL - 1 AS lev
                             FROM dual
                           CONNECT BY LEVEL < (SELECT MAX(length(original_word)) + 1
                                                 FROM dict)) b
                   WHERE a.min_len >= b.lev
                     AND (substr(a.curr, b.lev, 1) = substr(a.prev, b.lev, 1) OR
                         b.lev = 0))
          WHERE diff >= -1)
 GROUP BY curr, prev

Yukarıdaki sorgu sonucunda, orjinal kelimeler ile sıkıştırılmış kelimeler ayrı bir tabloya aktarılır. Sıkıştırılmış sözlüğün bir kısmı aşağıda belirtilmiştir.

aba
3cı
5lık
3di
3jur
6cu
3küs
3lı


Sıkıştırma işleminin sonucunda, Oracle içinde tanımlanan TEMP_DIR adlı dizin nesnesinin gösterdiği yerde(c:\temp) sıkıştırma öncesi ve sonrası oluşan kayıtlar metin halinde bulunmaktadır. Bunlar

  • Original.txt : Sıkıştırma öncesi sözlüğün ilk hali.
  • Compressed.txt: Sıkıştırma sonrası oluşan sözlük.

Dosya yolu, ekte belirtilen dosya içinden değiştirilerek, gerekli yerde oluşturulması sağlanabilir.

6.   Uygulamanın Çalıştırılması

Ön şart olarak, Oracle veritabanı 9 veya üzeri bir versiyonun yüklü ve çalışıyor olması gerekmektedir.

Uygulama ile ilgili gerekli olan dosyalar aşağıda belitilmiştir:

Dosya Adı
Görevi
dict_init.sql
Oracle içine atılacak dosya için gerekli tablo ve indexlerin oluşturulmasını sağlayan dosya. Bu dosya çalıştıktan sonra, veritabnı içinde dict adında bir tablo oluşturulur.
dict.ctl
SQL*Loader adlı metin dosyalarının Oracle veritabanı içine atılmasını sağlayan aracın okuduğu konfigürasyon dosyası. Bu dosya içinde sıkıştırılacak dosyanın(dict.txt) ismi bulunmaktadır.
dict_preprocess.sql
Sözlük ile ilgili ön işlemlerin yapıldığı dosya. Bu dosya çalıştırılarak gereksiz verilerin silinme işlemi yapılır.
dict_process.sql
Sözlük ile ilgili sıkıştırma işleminin yapıldığı dosya. Bu dosya çalıştırılarak sıkıştırma işlemi yapılır, veritabanında dict_compressed isimli bir tablo oluşturulur.
dict_start.bat
Sözlüğün yüklenmesi ve işlenmesi ile ilgili dosyaların hangi sıra ve parametreler ile çağrıldığının belirtildiği dosyadır. Bu dosya, uygulamanın ana dosyasıdır. Bu dosya, komut satırından çağrıldığı takdirde sıkıştırma ile ilgi işlemler sıra ile yapılır.
dict.txt
Sözlük verilerinin bulunduğu dosya.
UTL_EXP_v3.pck
Sıkıştırılan sözlüğün bir metin dosyasına aktarılmasını sağlayan PL/SQL paketidir. Bu paketin Oracle içine yüklenmiş olmalıdır.

Uygulama çalıştıktan sonra aşağıda belirtilen dosyalar oluşturulur:


Dosya Adı
Görevi
dict.log
SQL*Loader ile oluşacak dosyanın logunu tutulduğu dosyadır. Bu dosya içinde hata durumları ve istatistiki bilgileri bulunur.
dict_preprocess.log
Uygulamanın ön işleme kısmında tutulan loglar buraya yazılır.
dict_process.log
Uygulamanın sıkıştırma kısmında tutulan loglar buraya yazılır.
original.txt
bu bir bakıma sözlüğün bir kopyasıdır.  Eğer ön işlemler yapılmışsa, burada ön işlemler sonucunda elde edilien sözcükler bulunur.
compressed.txt
Bu dosya içinde sıkıştırma işlemi sonucunda sözcükller bulunur.


Uygulamayı çalıştırmak için belirtilen dosyalar belirli bir dizine toplanır. dict_start.bat adlı dosya çalıştılır. Bu dosya içinde Oracle veritabanına bağlanmak için gerekli değişiklikler yapılmalıdır. Örneğin aşağıda belirtilen dosyada

hr/hr@XE è username/password@database_identifier

olarak belirtilen bağlantı bilgileri değiştirilmelidir.

sqlplus hr/hr@XE  @dict_init.sql
sqlldr  userid=hr/hr@XE control=dict.ctl log=dict.log
sqlplus hr/hr@XE  @dict_preprocess.sql
sqlplus hr/hr@XE  @dict_process.sql

Eğer sözlük ile ilgili bir ön işleme yapılmayacaksa,

sqlplus hr/hr@XE  @dict_preprocess.sql

kısmı, bat uzantılı dosyadan çıkarılmalıdır.

Uygulama ile başka sözlüklerin de sıkıştırılması gerekiyorsa, uygulama dizini içine o sözlüğün dict.txt halinde kopyalanması gereklidir.

Uygulamanın örnek bir çalışma şekli aşağıda belirtilmiştir:

C:\DC>dict_start.bat

C:\DC>sqlplus hr/hr@XE  @dict_init.sql

SQL*Plus: Release 10.2.0.1.0 - Production on Sal Eki 23 00:14:13 2007
Copyright (c) 1982, 2005, Oracle.  All rights reserved.

Connected to:
Oracle Database 10g Express Edition Release 10.2.0.1.0 - Production

PL/SQL procedure successfully completed.
Table created.
Index created.
Index created.

Connected.

Directory created.
Grant succeeded.
Grant succeeded.

Disconnected from Oracle Database 10g Express Edition Release 10.2.0.1.0 - Production

C:\DC>sqlldr  userid=hr/hr@XE control=dict.ctl log=dict.log
SQL*Loader: Release 10.2.0.1.0 - Production on Sal Eki 23 00:14:17 2007
Copyright (c) 1982, 2005, Oracle.  All rights reserved.

....
Commit point reached - logical record count 49728
Commit point reached - logical record count 49756

C:\DC>sqlplus hr/hr@XE  @dict_preprocess.sql
SQL*Plus: Release 10.2.0.1.0 - Production on Sal Eki 23 00:12:16 2007
Copyright (c) 1982, 2005, Oracle.  All rights reserved.

Connected to:
Oracle Database 10g Express Edition Release 10.2.0.1.0 - Production

8360 rows deleted.
4 rows deleted.

Disconnected from Oracle Database 10g Express Edition Release 10.2.0.1.0 - Production

C:\DC>sqlplus hr/hr@XE  @dict_process.sql
SQL*Plus: Release 10.2.0.1.0 - Production on Sal Eki 23 00:12:18 2007
Copyright (c) 1982, 2005, Oracle.  All rights reserved.

Connected to:
Oracle Database 10g Express Edition Release 10.2.0.1.0 - Production

PL/SQL procedure successfully completed.
Table created.


TOTAL_ORIG TOTAL_COMPR      PERCT
---------- ----------- ----------
    310030      143120 ,538367255


PL/SQL procedure successfully completed.
Disconnected from Oracle Database 10g Express Edition Release 10.2.0.1.0 - Production

C:\DC>


7.   Analiz ve Yorumlar

Sıkıştırma işlemi sonucunda sıkıştırma öncesi sözlükdeki toplam harf sayısı ile sıkıştırma sonrasındaki harf sayısı ve boyutu incelenmiştir.



Sıkıştırma Öncesi
Sıkıştırma Sonrası
Harf Sayısı
310030
143120
Dosya Boyutu(KB)
419
233

Sıkıştırma Oranı : %54


Yapılan bu çalışma sonucunda, varolan veriler saklanma yerinde yaklaşık %54 oranında tasarruf edilmiştir. Bu hem maliyete hem de verilerin taşınması için gerekli ağ kaynaklarının kullanılmasında tasarruf demektir. Bu kazanımın yanında, sıkıştırma ve açma işlemlerinin yapılması gereklidir. Bu da zaman noktasında az da olsa bir kayıptır.


  • Bu yöntemde fazla zaman almadan yüksek oranda bir sıkıştırma başarısı elde edilmiştir.
  • Sadece sözlük tarzı uygulamalarda bu yöntem etkin bir şekilde kullanılabilir. Yani bir kelime, kendinden sonra gelen kelime içinde tamamen veya kısmen geçiyorsa, bu yöntem uygulanabilir.

No comments: