<?php
abstract class Drzewo {
public $waga;
public $znaki;
// tworzymy nowe Drzewo - zeby to zrozumiec przydaje sie zajrzec do konstruktora Rozgalezionego drzewa
function nowe_Drzewo($prawe) {
$nowawaga = $this->waga + $prawe->waga;
$noweznaki = $this->znaki + $prawe->znaki;
return new Rozgalezione($this,$prawe,$noweznaki,$nowawaga);
}
// to nalezy przeczytac po zobaczeniu jak tworzone sa drzewa
function dekoduj_znak($bity) {
if ($this instanceof Lisc)
return array($this->znak,$bity);
else
if ($bity[0] == 0)
$nowedrzewo = $this->lewe;
else
$nowedrzewo = $this->prawe;
return $nowedrzewo->dekoduj_znak(array_slice($bity,1));
}
function dekoduj($bity){
if ($bity == array())
array();
else
{
$odkodowany_znak = dekoduj_znak($bity);
$znak = $odkodowany_znak[0];
$nowebity = $odkodowany_znak[1];
$dekodowanareszta = $this->dekoduj($nowebity);
return array_merge(array($a),$dekodowanareszta);
}
}
}
//Drzewo jest Lisciem
class Lisc extends Drzewo {
public $znak;
function __construct($z,$w){
$this->znak = $z;
$this->waga = $w;
$this->znaki = array($z);
}
}
// ... albo ma poddrzewa
class Rozgalezione extends Drzewo {
public $lewe;
public $prawe;
function __construct($podDrzewo_lewe, $podDrzewo_prawe, $z , $w){
$this->lewe = $podDrzewo_lewe;
$this->prawe = $podDrzewo_prawe;
$this->znaki = $z;
$this->waga = $w;
}
}
/*
function nowe_Drzewo($lewe,$prawe) {
$nowawaga = $lewe->waga + $prawe->waga;
$noweznaki = array_merge($lewe->znaki, $prawe->znaki);
return new Rozgalezione($lewe,$prawe, $noweznaki, $nowawaga);
}
function zamien_na_tablice($str){
//oprocz zmiany w tablice usuwamy spacje
$str = str_replace(' ','',$str);
return str_split($str);
}
/*nazwa sama sie wyjasnia
wystapienia_w_tekscie : array[Char] -> array[(Char,Int)]
*/
function wystapienia_w_tekscie($tekst) {
$wystapienia = array();
$dl = count($tekst); // ZAL TEKST JEST LISTA CHAR'OW
for ($i = 0; $i < $dl ; $i++){
$litera = $tekst[$i];
$wystapienia[$litera] +=1;
}
return $wystapienia;
}
/*
stworz_liste_Lisci_dla_znakow : array[(Char,Int)] -> array[drzewa]
*/
function stworz_liste_Lisci_dla_znakow( $wystapienia ) {
usort($wystapienia);
$a = array();
foreach ($wystapienia as $znak => $ile) {
$Lisc_w_Liscie = new Lisc($znak,$ile);
$a = array_merge($a,array($Lisc_w_Liscie));
}
return $a;
}
/*to jest to samo co insert z insertion sort
umiesc_w_odpowiednim_miejscu : drzewa x array[drzewa] -> array[drzewa]
*/
function umiesc_w_odpowiednim_miejscu($d , $a){
if ($a == array())
return array($d);
else
{
$glowa = $a[0];
$ogon = array_slice($a,1);
if ($glowa->waga <= $d->waga)
return array_merge( array($glowa) , umiesc_w_odpowiednim_miejscu($d,$ogon));
else
return array_merge( array($d), $a);
}
}
/*
konstruuj_z_drzew : array[drzewa] -> drzewa
MOMENT - NAJWAZNIEJSZY POMYSL HUFFMANNA
jesli mamy poszeregowane wzgl. czestosci znaki,
to tworzymy Drzewo kodujace w nast sposob :
- umieszczamy 'na dole' Drzewo scalone z Lisci
o 2 najrzadziej wystepujace symbolach
- rekurencyjnie stosujemy funkcje do reszty
- doklejamy wyzej opisane Liscie
*/
function konstruuj_z_drzew($drzewa) {
/*
zakladamy ze drzewa sa wysortowane - funkcja
stworz_liste_Lisci_dla_znakow sortuje wejscie,
a ta funkcje bedziemy stosować do jej wyjscia
*/
if (length($drzewa) <= 1)
return $drzewa;
else
{ // TO WARTO SOBIE NARYSOWAC
$d1 = $drzewa[0];
$d2 = $drzewa[1];
$dolne = $d1->nowe_Drzewo($d2) ;
$reszta = array_slice($drzewa,2);
umiesc_w_odpowiednim_miejscu($dolne,konstruuj_Drzewo_huffmana($reszta));
}
}
?>
- Output for git.master, git.master_jit, rfc.property-hooks
This tab shows result from various feature-branches currently under review by the php developers. Contact me to have additional branches featured.
Active branches
Archived branches
Once feature-branches are merged or declined, they are no longer available. Their functionality (when merged) can be viewed from the main output page
preferences:
40.42 ms | 401 KiB | 8 Q