ALGORITMI: Bik' par binaarajiem kodiem...

[Guest inx]

Virkne: aaabbcd

taatad aiznjem 7 * 8(bit) = 56 bitus

 

1. Saskaita unikaalam simbolam frekvenci:

a - 3

b - 2

c - 1

d - 1

 

2. Izveido binaaro koku:

         0 __|__ 1

            |      |

      0 _b(0)   a(1)

        |

  0 __|__ 1

    |       |

c(00)  d(01)

 

3. Pieraksta virkni binaaraa formaa:

a(1) a(1) a(1) b(0) b(0) c(00) d(01) jeb 111000001 = 9 biti

 

Un tagad veel pasakiet, ka mans ieprieksheejais topiks bija garaam!!! Un, ka es nenjemu veeraa, ko citi saka! :evil:

 

[VIL]

Hafmana kods. Klasisks kompresijas algoritms. Lieliski strādā uz palielākiem datu apjomiem.

 

Ja atgriežamies pie Tava augstākaprakstītā piemēra, tad Tu neesi ņēmis vērā koka izmēru. Ja Tev koks ir mainīgs, tad kompresijas iznākums ir koka apraksts + kompresētā simbolu virkne. Otrs risinājums ir fiksēt koku, iekodējot to [de-]kompresijas programmā. Šādā gadījumā Tu izvairīsies no koka pārraides, bet arī neiegūsi visefektīvāko kompresijas pakāpi.

 

Iepriekšējā topikā Tu uzdevi jautājumu, kā 4 bitus pārveidot par 2 bitiem bez datu zuduma. Tas nav iespējams. Manuprāt, pie 4 bitiem arī Hafmana kods neko daudz nestrādās. Izskatās, ka Tev galvā bija vairāk infas, nekā Tu iepostēji iepriekšējā topikā. Tā kā tauta Tev sniedza pareizu atbildi, bet Tu viņus par miroņiem... :cry:

[Guest inx]

Jaa, VIL! Tas ir Hafmena binaarais koks. Lieliski straadaa, ja ir jaaizmanto texta kompreseeshanai, jo algoritma aatrdarbiiba ir optimaala max. koda garumam, kas nepaarsniedz 8.

 

Lielaakiem kluchiem shis algoritms ir garaam, ja neizmanto aritmeetisko kodeeshanu ar kanoskajiem Hafmena kodiem.

[Dawis]

NEVAR vispariga gadijuma neko saspiest.. tas izriet no vienkarsham kombinatorikas likumsakaribaam.. var saspiest specialgadijumos, ja informacija ir pierakstiita neizdeviigaa sisteemaa, tad to var pierakstiit izdevigaakaa