Dinaminis Šenono Fano kodavimas

Dinaminis Šenono Fano kodavimas – algoritmas, naudojamas duomenų kompresijoje. Simboliai koduojami dinamiškai, tai yra kodai kuriami suspaudimo eigoje.

Dinaminis Šenon Fano kodavimas skiriasi nuo statinio:

Nėra formuojama antraštė užkoduoto failo pradžioje.
Raidžių kodai keičiasi kodavimo eigoje.
Kuriamas dvejetainis medis turi vieną papildomą lauką, kuris skirtas saugoti nežinomos raidės kodui (not yet transmited).
Vidutiniškai dinaminis Šenono Fano kodavimas neduoda geresnių rezultatų, nei statinis.

Yra du galimi būdai realizuoti Dinamini Šenono Fano kodavimą:

Po kiekvienos perskaitytos raidės medis perkuriamas visiškai iš naujo.
Po kiekvienos perskaitytos raidės medis yra pertvarkomas, kad atitiktų to medžio taisykles.

1-mas būdas[redaguoti | redaguoti vikitekstą]

Skaitomas archyvuojamas failas po vieną raidę.
Perskaityta raidė tikrinama ar ji jau egzistuoja mūsų medyje (raidžių masyve, kuris yra mūsų abėcėlė), jei egzistuoja, padidinamas jos pasikartojimų skaičius.
Į suarchyvuojamą failą įrašomas tos raidės kodas.
Abėcėlė yra rūšiuojama pagal raidžių pasikartojimų skaičių, tada naudojama funkcija aprašyta Statiniame Šenono Fano kodavime, kad sukurti raidžių kodus iš masyvo. Iš tų raidžių kodų kuriamas dvejetainis medis, su sąlyga, kad jis turės (not yet transmited) simbolį(Jis būna arba pats dešiniausias medyje, arba pats kairiausias).
Jei archyvuojant buvo sutiktas naujas simbolis, į failą rašomas naujos raidės(not yet transmited) kodas ir į 8bitus pati raidė.

Pastaba: rūšiavimą ir medžio perkūrimą atlikti tik po to, kai į failą buvo įrašytas seno medžio raidės kodas.

Archyvuojamas failo turinys: abrakadabra, Suarchyvuojamo failo turinys: a0b00r1000k1000d…

Dekoduojant atliekami analogiški žingsniai kaip ir užkoduojant, tik iš failo skaitoma po vieną bitą ir vaikštoma po medį pagal perskaitytus bitus. Jeigu dekoduojant buvo nueita iki nežinomo simbolio, iš failo perskaitoma 8bitai. Jeigu buvo nueita iki simbolio, esančio medyje, vėl didinamas pasikartojimų skaičius, į išarchyvuojamą failą įrašoma rasta raidė, o tada medis perkuriamas kaip užkodavime.

Išimtis pirmam simboliui - perskaityti reikia 8bitus.

Suarchyvavimo pavyzdys

public static void suarchyvuok(byte[] p_fromFile) throws IOException

   {
       byte chr;
       list = new Vector<int[]>();
       Additional addit = new Additional();
       String[] medis = null;
       BinarySearchTree BST = null;
       for (int i = 0; i < p_fromFile.length; i++)
       {
           chr = p_fromFile[i];
           int[] elem = {0, 0};

           boolean notFound = true;

           if (list.isEmpty())
           {
               elem[0] = chr;
               elem[1] = 1;
               list.add(elem);

               bout.writeBits(chr, 8); 
               
               Node root = new Node('r', -1);
               BST = new BinarySearchTree(root);

               Node first = new Node('s', 0);
               BST.insertLeft(first);

               BST.setToRoot();
               Node empty = new Node('?', 1);
               BST.insertRight(empty);
               BST.setToRoot();
           }
           else
           {
               for (int n = 0; n < list.size(); n++)
               {
                   if (list.elementAt(n)[0] == chr)
                   {
                       list.elementAt(n)[1]++;
                       notFound = false;
                   }
               }
               if (notFound)
               {
                   elem[0] = chr;
                   elem[1] = 1;
                   list.add(elem);
               }

               if (notFound)
               {
                   String kodas = BST.findRightMost();
                   for (int z = 0; z < kodas.length(); z++)
                       bout.write1Bit();                   
                  
                   bout.writeBits(chr, 8); 
                                       
                   list = addit.sortList(list);
                   medis = addit.makeCodes(list);
                   BST = makeTree(medis);
               } 
               else
               {                                        
                   writeToFileKode(chr, medis);              
                   list = addit.sortList(list);
                   medis = addit.makeCodes(list);
                   BST = makeTree(medis);                      
               }
           }
       }     
       
       String kodas = BST.findRightMost();
       for (int z = 0; z < kodas.length(); z++)
       {
           bout.write1Bit();                   
       }

       bout.writeBits(255, 8);
       bout.close();
   }

2-as būdas[redaguoti | redaguoti vikitekstą]

Įgyvendinti ši būdą sudėtingiau, bet veikimo greitis didesnis ir algoritmas trumpesnis. Medžiai nėra perkūrinėjami iš naujo, jie yra pertvarkomi pagal tam tikras taisykles:

Visi medžio sūnūs saugo jų sūnų pasikartojimų skaičių sumą.
Pasirenkama: dešinysis arba kairysis sūnus visada privalo turėti daugiausiai pasikartojimų.
Jeigu netenkina pastarosios sąlygos, atliekami medžio pertvarkymai, kad išlaikyti šią sąlygą.

Papildoma informacija: