@ 2014-06-08T15:47:12Z <?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));
}
}
$tekst_lista = zamien_na_tablice($tekst);
$wystapienia = wystapienia_w_tekscie($tekst_lista);
$bazowe_Liscie = stworz_liste_Lisci_dla_znakow($wystapienia);
konstruuj_z_drzew($bazowe_Liscie);
}
?>
Enable javascript to submit You have javascript disabled. You will not be able to edit any code.
Here you find the average performance (time & memory) of each version. A grayed out version indicates it didn't complete successfully (based on exit-code).
Version System time (s) User time (s) Memory (MiB) 5.4.29 0.008 0.052 12.53 5.4.28 0.013 0.043 12.42 5.4.27 0.010 0.060 12.42 5.4.26 0.017 0.091 12.42 5.4.25 0.011 0.054 12.42 5.4.24 0.023 0.045 12.42 5.4.23 0.008 0.048 12.41 5.4.22 0.009 0.071 12.41 5.4.21 0.006 0.054 12.41 5.4.20 0.010 0.098 12.41 5.4.19 0.014 0.049 12.41 5.4.18 0.007 0.040 12.41 5.4.17 0.004 0.040 12.41 5.4.16 0.010 0.037 12.41 5.4.15 0.005 0.044 12.40 5.4.14 0.006 0.038 12.10 5.4.13 0.004 0.039 12.08 5.4.12 0.009 0.051 12.04 5.4.11 0.007 0.052 12.04 5.4.10 0.009 0.047 12.04 5.4.9 0.009 0.055 12.04 5.4.8 0.011 0.051 12.04 5.4.7 0.011 0.046 12.03 5.4.6 0.011 0.051 12.04 5.4.5 0.007 0.067 12.04 5.4.4 0.009 0.046 12.02 5.4.3 0.006 0.050 12.02 5.4.2 0.007 0.053 12.02 5.4.1 0.009 0.050 12.02 5.4.0 0.005 0.060 11.51 5.3.28 0.009 0.052 12.72 5.3.27 0.008 0.046 12.73 5.3.26 0.005 0.048 12.73 5.3.25 0.007 0.040 12.72 5.3.24 0.007 0.043 12.73 5.3.23 0.006 0.059 12.72 5.3.22 0.012 0.037 12.69 5.3.21 0.009 0.056 12.69 5.3.20 0.008 0.058 12.69 5.3.19 0.013 0.056 12.69 5.3.18 0.010 0.052 12.68 5.3.17 0.009 0.055 12.68 5.3.16 0.012 0.060 12.68 5.3.15 0.011 0.047 12.68 5.3.14 0.008 0.042 12.68 5.3.13 0.005 0.056 12.67 5.3.12 0.006 0.040 12.67 5.3.11 0.007 0.039 12.67 5.3.10 0.008 0.044 12.15 5.3.9 0.011 0.046 12.14 5.3.8 0.012 0.073 12.13 5.3.7 0.011 0.044 12.13 5.3.6 0.006 0.052 12.11 5.3.5 0.015 0.080 12.06 5.3.4 0.017 0.093 12.07 5.3.3 0.011 0.084 12.03 5.3.2 0.037 0.111 11.81 5.3.1 0.017 0.048 11.77 5.3.0 0.010 0.055 11.75
preferences:dark mode live preview
142.05 ms | 1394 KiB | 7 Q