Veri Sıkıştırma ve Açgözlü Algoritmalar PDF

9.Hafta Veri sıkıştırma ve Aç gözlü algoritmalar 1  Veri Sıkıştırma (Compression) Kayıplı-Kayıpsız Veri Sıkıştırma Sabit ve Değişken Genişlikli Kodlama Huffman Algortiması (Greedy Algoithms) 2 Veri Sıkıştırma  Veri sıkıştırma;  1- Alan gerek...

9.Hafta Veri sıkıştırma ve Aç gözlü algoritmalar 1  Veri Sıkıştırma (Compression) Kayıplı-Kayıpsız Veri Sıkıştırma Sabit ve Değişken Genişlikli Kodlama Huffman Algortiması (Greedy Algoithms) 2 Veri Sıkıştırma  Veri sıkıştırma;  1- Alan gereksinimini azaltmak için  Hard disklerin boyutu büyümekle birlikte, yeni programların ve data dosyalarının boyutu da büyümektedir ve alan ihtiyacı artmaktadır.  3.5" floppy diskler hala kullanılmaktadır ve alanları çok azdır.  2-Zaman ve bant genişliği gereksinimini azaltmak için  Birçok program ve dosya internetten download edilmektedir.  Birçok kişi düşük hızlı bağlantıyı kullanmaktadır.  Sıkıştırılmış dosyalar transfer süresini kısaltmakta ve bir çok kişinin aynı server’ı kullanımına izin vermektedir. Kayıplı ve Kayıpsız Sıkıştırma  Kayıplı Sıkıştırma  Bilginin bir kısmı geri elde edilemez (MP3, JPEG, MPEG)  Genellikle ses ve görüntü uygulamalarında kullanılır. Çok büyük ses ve görüntü dosyalarında çok iyi sıkıştırma yapar ve kullanıcı kalitedeki azalmayı fark etmez.  Kayıpsız Sıkıştırma  Orijinal dosyalar tekrar ve tam olarak elde edilir (D(C(X)))=X, burada C sıkıştırılan dosyayı, D ise açılan dosyayı ifade eder. .txt,.exe,.doc,.xls,.java,.cpp vs. gibi dosyalarda kullanılır.  Ses ve görüntü dosyalarında da kullanılabilir ancak kayıplı sıkıştırma kadar yüksek sıkıştırma oranına sahip olmaz. Kayıpsız Sıkıştırma  Kayıpsız sıkıştırma temel olarak üç algoritma altında toplanır  Huffman – her karakter için değişken genişlikli bir kelime kodu (codeword) kullanır.  LZ277 – "sliding window (kayan pencere)" kullanır. Bir grup karakteri bir anda sıkıştırır.  LZ278/LZW – daha önce karşılaşılan işaretleri saklayan bir sözlük kullanır ve bir grup karakteri aynı anda sıkıştırır.  Kayıpsız sıkıştırma uygulamaları  Unix compress, gif : LZW  pkzip, zip, winzip, gzip: Huffman+LZ277  ASCII, 8 bit  29 farklı karakter 5 bit ile kodlanabilir.  5/8 = %62,5 sıkıştırma oranı Huffman Kodlama  Renksiz ve özelliksiz karakterlerden oluşan dosyaların sıkıştırılması için kullanılan kodlardır. Dosyadaki bir karakterin tekrar sayısına o karakterin frekansı denir ve karakterlerin tekrar frekansından faydalanarak ikili kodlar üretilir.  İki tip kodlama vardır: Sabit uzunluklu ve değişken uzunluklu.  Toplam 1.000.000.000 karakterden oluşan bilginin sadece 6 harften {a, b, c, d, e, f} oluştuğunu varsayalım. Karakterlerin kullanım sıklıkları: Huffman Kodlama  Değişken uzunluklu kodlamada, frekansı en yüksek olan karaktere en kısa kod ve diğer karakterlere benzer mantıkla kod verilirse, sabit uzunluklu kodlamaya göre daha başarılı bir sonuç elde edilir.  Kodlama ve kodlamayı çözmek için ön ek (prefix) kodlamadan faydalanılır.  Kodlama her zaman için daha kolaydır. Kodu çözmek, sabit uzunluklu kodlamada oldukça kolaydır; değişken uzunluklu kodlamada ise, biraz daha zahmetlidir.  Sıkıştırılmış bir dosyanın kod ağacı tam dolu ikili ağaç ise, bu sıkıştırma işlemi optimaldir; aksi halde optimal değildir.  Sabit uzunluklu kodlama optimal değildir, çünkü ağacı tam dolu ikili ağaç değildir. Karakterlerin Kodunu Çözme Karakterlerin Kodunu Çözme Ön ek Kodları ve İkili ağaçta gösterimi Kodlama için gereken boyut  Eğer ağaç C alfabesinde üretilmiş ise, bu durumda yaprak sayısının |C| olması gerekir ve ara düğümlerde |C|-1 olmalıdır.  cC olsun ve f(c) bu karakterin frekansını göstersin. T ağacı da ön ek(prefix) kod ağacı olsun. dT(c) ise c karakterinin T ağacındaki derinliği olsun ve aynı zamanda c karakterinin kod uzunluğunu gösterir. Dosyanın kodlandıktan sonraki bit olarak uzunluğu B(T) aşağıdaki gibi ifade edilir B(T) =  f (c)d T (c)  olur. cC Kodlama ağacının oluşturulması  Sabit uzunlukta kodlama 100 0 1 14 86 0 1 0 58 28 14 0 1 1 0 0 1 a:45 b:13 c:12 d:16 e:9 f:5 Kodlama ağacının oluşturulması  Değişken uzunlukta kodlama: Frekansa göre sıralanır ve her biri bir yaprağı temsil eder. En küçük iki değer bir atada toplanır ve geriye kalan yapraklar ile ata tekrar sıralanır. f:5 e:9 c:12 b:13 d:16 a:45  Değişken uzunluklu kodlama için frekanslarınsıralanması. Kodlama ağacının oluşturulması  Değişken uzunluklu kodlama 14 c:12 b:13 d:16 a:45 0 1 f :5 e:9 Kodlama ağacının oluşturulması  Değişken uzunluklu kodlama 14 d:16 25 a:45 0 1 0 1 f :5 e:9 c:12 b:13 Kodlama ağacının oluşturulması  Değişken uzunluklu kodlama 25 30 a:45 0 1 0 1 14 d:16 c:12 b:13 0 1 f :5 e:9 Kodlama ağacının oluşturulması  Değişken uzunluklu kodlama 55 a:45 0 1 25 30 0 1 1 0 14 c:12 b:13 d:16 1 0 f:5 e:9 Huffman Algoritması Analizi  Uygun veri yapısı olarak min-heap kullanılabilir. (Her seferinde frekansı düşük olan düğüm çıkarılır ve toplanarak ağaca tekrar eklenir)  (http://rosettacode.org/wiki/Huffman_coding)  Heap oluşturma O(log n) ve for döngüsünde n-1 adet işlem yapılır  Toplam Çalışma süresi O(nlogn) olur.  Huffman algoritması az sayıda karakter çeşidine sahip ve büyük boyutlardaki verilerde çok kullanışlı olabilir. Fakat oluşturulan ağacın sıkıştırılmış veriye eklenmesi zorunludur. Bu da sıkıştırma verimini düşürür. Adaptive Huffman gibi teknikler bu sorunu halletmek için geliştirilmişlerdir. Örnek:  Veri setine ait frekans tablosu aşağıdaki gibi olsun. Sembol Frekans A 60 B 40 C 25 D 20 E 10  Adım 1: Huffman ağacındaki en son düğümleri oluşturacak olan bütün semboller frekanslarına göre küçükten büyüğe doğru sıralanırlar. Örnek: Adım 2  En küçük frekansa sahip olan iki sembolün frekansları toplanarak yeni bir düğüm oluşturulur. Oluşturulan bu yeni düğüm var olan düğümler arasında uygun yere yerleştirilir. Bu yerleştirme frekans bakımından küçüklük veya büyüklüğe göredir. Örnek: Adım 3  Bir önceki adımdaki işlem terkarlanılarak en küçük frekanslı 2 düğüm tekrar toplanır ve yeni bir düğüm oluşturulur. Örnek: Adım 4 Adım 5 Örnek: Adım 6 Örnek: Veri setinin kodlanmış hali Örnek: Karşılaştırma  Veri setini ASCII kodu ile kodlanırsa, her karakter için 1 byte(8 bit)’lık alan gerektiğinden toplamda 155 byte(1240 bit)’a ihtiyaç olacaktı.  Huffman kodlaması ile bu sayı :  60x1 + 40x2 + 25x3 + 20x4 +10x4= 335bittir.  Görüldüğü gibi Huffman kodlaması ile 335/1240= %27’lik bir sıkıştırma oranı sağlanmaktadır. Bu kazanç, veri setindeki sembollerin frekansları arttıkça daha da artmaktadır. Örnek:  e: 00  d: 01  a: 10  b: 111  f: 1100  c: 1101 Örnek  Elimizde sıkıştırılması istenen alttaki katarın olduğunu varsayalım;  aaaabbbccddddeeefa  Bu katardaki karakter sıklıkları hesaplandığında;  f = 1, c = 2, b = 3, e = 3, d = 4, a =5  ASCII olarak tutulduğunda bu katar toplam 18 * 8 = 144 bit yer kaplamaktadır.  Örnek:  Sık olan karakterler üst  a: 10 sıklık:5 dallarda, seyrek olanlar alt  d: 01 sıklık:4 dallarda.  Sıkıştırmadan önce  e: 00 sıklık:3  144 bit (18 * 8 bit)  b: 111 sıklık:3  Huffman kodu  c: 1101 sıklık:2  45 bit (sıklık * kod sözcüğü uzunluğu) yer  f: 1100 sıklık:1  Sıkıştırma oranı  45 / 144 = %31 Kodları elde ettikten sonra veri içerisindeki tüm veriler baştan okunur. Her karaktere karşılık gelen kod yerine yerleştirilir. aaaabbb ccdddd eeef a 10 10 10 10 111 111 111 1101 1101 01 01 01 01 00 00 00 1100 10 verimizin boyutu küçülmüş oldu Huffman Kodunun Çözümü  Frekans tablosu ve sıkıştırılmış veri mevcutsa bahsedilen işlemlerin tersini yaparak kod çözülür. Diğer bir değişle:  Sıkıştırılmış verinin ilk biti alınır. Eğer alınan bit bir kod sözcüğüne karşılık geliyorsa, ilgili kod sözcüğüne denk düşen karakter yerine konulur.  Eğer alınan bit bir kod sözcüğü değil ise sonraki bit ile birlikte alınır ve yeni dizinin bir kod sözcüğü olup olmadığına bakılır. Bu işlem dizinin sonuna kadar yapılır. Böylece huffman kodu çözülerek karakter dizisi elde edilmiş olur.  Açgözlü Algoritmalar (ve Grafikler) Greedy Algorithms (and Graphs) Grafik gösterim Minimum kapsayan ağaç Optimal altyapı Açgözlü seçim Prim’in açgözlü MST algoritması 32 Graflar (Graphs) Konular  Graflar-Tanım  Graf Gösterimleri  Graflarda Dolaşma  Breadth- First Search  Depth Search  Hamiltonian cycle  Euler cycle Graflar (Graphs) Tanım  Graf, matematiksel anlamda, düğümlerden ve bu düğümler arasındaki ilişkiyi gösteren kenarlardan oluşan bir kümedir. Mantıksal ilişki, düğüm ile düğüm veya düğüm ile kenar arasında kurulur.  Bağlantılı listeler ve ağaçlar grafların özel örneklerindendir.  Fizik, Kimya gibi temel bilimlerde ve mühendislik uygulamalarında ve tıp biliminde pek çok problemin çözümü ve modellenmesi graflara dayandırılarak yapılmaktadır.  Elektronik devreler, networkler  Ulaşım ve iletişim network’leri  Herhangi bir türdeki ilişkilerin modellenmesi (parçalar, insanlar, süreçler, fikirler vs.) GRAFLAR  Bir G grafı, V ile gösterilen düğümlerden (node veya vertex) ve E ile gösterilen kenarlardan (Edge) oluşur.  Her kenar iki düğümü birleştirir.  Her kenar, iki bilgi (düğüm) arasındaki ilişkiyi gösterir ve (u,v) şeklinde ifade edilir.  e=(u, v) iki düğümü göstermektedir.  Bir graf yönlü değil ise u ve v düğümleri arasındaki kenar (u,v)  E ve (v,u)  E olarak gösterilebilir.  Bir graf üzerinde n tane düğüm ve m tane kenar varsa, matematiksel gösterilimi, düğümler ve kenarlar kümesinden elamanların ilişkilendirilmesiyle yapılır:  V={v0, v1, v2... vn-1, vn} Düğümler kümesi  E={e0, e1, e2... em-1, em } Kenarlar kümesi  G=(V, E) → Graf  36 Graflar G = (V, E) grafları aşağıda verilmiştir. V = {A, B, C, D, E, F}  E = {(A, B), (A, D), (B, C), (C, D), (C, E), (D, E)} B C A F D E  37 Graflar  38 Graflar-Tanımlar  Komşu(adjacent): Eğer (u,v)  E ise, u ve düğümleri komşudur.  Derece(degree):Bir düğümün derecesi, komşu düğüm sayısına eşittir.  Yol (path): v0, v1, v2... vn, düğümlerinin sırasıdır, vi+1 düğümü vi düğümünün komşusudur. (i= 0..n-1)  Basit Yol (simple path): düğüm tekrarıolmayan yoldur.  Döngü(cycle): basit yoldur, sadece ilk ve son düğüm aynıdır.  39 Graflar-Tanımlar  Bağlı Graf(connected graph): Bütün düğümler bir birine herhangi bir yol ile bağlıdır.  Altgraf(Subgraph):Bir grafı oluşturuan alt düğümler ve kenarlar kümesidir.  Bağlı elaman (Connected component): bağlı alt graflar. Örnek: 3 tane bağlı elamana sahip graflar  40 Graflar-Tanımlar  Ağaç(tree): Döngü olmayan bağlı graflardır.  Orman(forest): Ağaçların toplamıdır.  41 Graflar için Veri yapıları Komşuluk matrisi gösterimi  42 Komşuluk listesi gösterimi  43 Komşuluk listesi gösterimi  Yönsüz graf komşuluk listesi  Yönlü graf komşuk listesi  44 Komşuluk listesi gösterimi  Her kenarı ağırlıklandırılmış yönlü graf komşuluk listesi  45 Graf Arama Algoritmaları  Graf içindeki her kenar ve düğüm için sistematik arama.  G=(V,E) grafı yönlü olabilir veya olamayabilir.  Uygulamalar  Derleyiciler(Compilers)  Grafikler(Graphics)  Haritalama(Mapping)  Ağlar(Networks):routing, searchind, clustering, vs.  46 Enine Arama Breatdh First Search (BFS)  BFS, bir grafın bağlı olan parçalarını dolaşır ve bir kapsayan ağaç (spaning tree) oluşturur.  BFS, arama ağaçlarındaki level order aramaya benzer.  1-Seçilen düğümün tüm komşuları sırayla seçilir ve ziyaret edilir.  2- Her komşu kuyruk içerisine atılır.  3- Komşu kalmadığında kuyruk içerisindeki ilk düğüm alınır ve 2. adıma gidilir.  47 Breatdh First Arama-düğüm renklendirme  Ulaşılmayan bir düğüm beyaz renklidir.  Bir düğüm, eğer kendine ulaşılmış ancak tüm kenarlarına bakılmamışsa gri renklidir.  Bir düğüm, eğer kendisinin tüm komşu düğümlerine ulaşıldıysa (komşuluk listesi tamamen incelenir) siyah renklidir.  48 Breatdh First Arama Örnek  S düğümü ile başla  49 Breatdh First Arama Örnek  51 BFS Özellikleri  G=(V,E) grafı içinBFS, s düğümünden ulaşılabilecek tüm düğümleri dolaşır.  Ulaşılabilecek düğümler için en kısa yolu hesaplayabilir.  Ulaşılabilecek tüm düğümler için BF ağacını oluşturur.  s düğümünden ulaşılan bir v düğümü için BF ağacı içindeki yol, G grafındaki en kısa yolu (shortest path) ifade eder.  52 Yönlü Graf(Digraph) için Enine arama Örnek  53 Enine arama için örnek  54 Enine arama için örnek  55 Derinlemesine Arama Depth First Search(DFS)  1- DFS ile önce bir başlangıç düğümü seçilir ve ziyaret edilir.  2-Seçilen düğümün bir komşusu seçilir ve ziyaret edilir.  3- Seçilen komşu düğümün bir komşusu seçilir ve ziyaret edilir.  4-3. adım koşu düğüm kalmayıncaya kadar devam eder.  5-Komşu kalmadığında geri dönülür (backtracking) ve her düğüm için yeniden 3.adıma gidilir.  57 Derinlemesine Arama-(DFS)  Başlatma(initialize)- tüm düğümler beyaz yapılır.  Tüm beyaz düğümler DFS-Visit kullanılarak dolaşılır.  DFS-Visit(u) çağrıldığında u düğümü yeni ağacın kökü yapılır.  DFS çalışmasını bitirince, her u düğümü için erişilme zamanı (discovery time) d[u], ve bitirme zamanı (finishing time) f[u] değerleri atanır.  Back Edge(B): DF ağacında u düğümünün v atasına (ancestor) bağlı olması.  Forward Edge (F):DF ağacında u düğümünün, v toruna (descendant) bağlı olması.  Cross Edge(C): Geri kalan tüm kenarlar. Bu kenarlar ile aynı yada farklı DF ağacında, atası olmadığı diğer düğümler arasında dolaşabilir.  58 DFS-Örnek  S düğümü ile başla,  d/f→ d: erişilme zamanı, f: bitirme zamanı  59 DFS-Örnek  60 DFS-Örnek  61 DFS-Örnek  62 DFS-Örnek  63 DFS-Örnek du dv dv du DFS-Örnek 64  65 DFS-Çalışma Zamanı ve düğüm renklendirme  Çalışma zamanı:  DFS içindeki döngü (V) süresi alır (DFS-Visit çalışma süresi hariç).  DFS-Visit her düğüm için bir kez çağrılır.  Sadecebeyaz renkteki düğümler için çağrılır  Düğüm hemen gri renk yapılır.  DFS-Visit her çağrılışında |adj[v]| kez çalışır  DFS –Visit içintoplam çalışma zamanı→ (E)  DFS için toplam çalışma zamanı → (V+E)  Düğüm u,  d[u] zamanından önce beyazdır.  d[u] ve f[u] zamanda gridir, bundan sonra ise siyahtır.  66 Döngü olmayan yönlü graflar (DAG) DAG-Directed Acylic Graphs  Bir DAG döngü olmayan yönlü bir graftır.  Sıklıkla olaylar arasındaki öncelik sırasını göstermek için kullanılır. Örnek a olayı b olayından önce olmak zorundadır (paralel kod çalıştırma).  Tüm sıra topolojik sıralamayla (topological sort) verilebilir.  67 Topolojik Sıralama  Öncelik İlişkileri (Precedence relations): x’ten y’ ye bir kenar, x olayı y den önce olur anlamını içerir. Bir iş, kendisinin tüm alt işleri planladıktan sonra planlanabilir.  68 Topolojik Sıralama  Bir DAG’nın topolojik sıralaması tüm düğümlerin doğrusal sırasını ifade eder. Grafta döngü yoktur!  Topolojik sıralamada herhangi bir (u,v) kenarında, u, sıralamada v’den öncedir.  Aşağıdaki algoritma bir DAG için topolojik sıralamayı yapar  Toplam sıralama bağlı dizilerle ile oluşturulur.  69 Topolojik Sıralama  70 Topolojik Sıralama Topolojik sıralama için Sol düğüme göre DFS dolaşma  71 Topolojik Sıralama Topolojik sıralama için Sağ düğüme göre DFS dolaşma  72 Topolojik Sıralama Çalışma zamanı  74 Topolojik Sıralama  75 Topolojik Sıralama  76 Topolojik Sıralama  77 Topolojik Sıralama  78 Topolojik Sıralama  79 Topolojik Sıralama  80 Hamiltonian ve Euler Cycle  Hamiltonian döngüsü: Bir Ggrafında, başlangıç ve bitiş düğümleri hariç her düğüm bir kez bulunduğu yoldur.  Eulerdöngüsü: Bir G grafında, bir düğümünden başlayıp yine kendisinde bitecek şekilde oluşturulan bir yoldur. Bu yolda bütün düğümler en az bir kez bulunur ancak her kenar mutlaka bir kez bulunur.