Aktuális a mindenféle mintákra (genomi szekvenciák, arecibói rádiójelek ET-től, a mikrohullámú háttér) LZW fás vizsgálata, lássuk hát azt a használati esetet, amelyben a hallgató feldolgozza a z.c forrást! Melynek során (a posztban hivatkozott Sztoch. számtek. könyv iránymutatása alapján) azt vizsgáljuk saját proginkkal, hogy mekkora a felépített fa ághosszainak szórása.
Hogyan járj el? Skiccelj fel papírra egy rövid teszt sorozatot: 01111001001001000111, s tollal hajtsd végre magad az algoritmus, majd számold ki az átlagot és a szórást! Íme magam is ezt teszem: 
aztán beadom inputként ezt a mintát a z.c-nek is:
[norbi@sgu sgu]$ ./z <tesztminta.txt Ugyanaz jön ki. Ez után már barátságosabban nézünk a kódra, kicsivel, de csak egy kicsivel jobban bízunk abban, amit kiír (mert nem akarunk ugye úgy járni, mint John Conor a T100 Arnolddal :)
------------1(3)
---------1(2)
------1(1)
---------0(2)
------------0(3)
---------------0(4)
---/(0)
---------1(2)
------0(1)
---------0(2)
melyseg=4
altag=2.750000
szoras=0.957427
Más: van pár beküldött szórás, amit még nem ellenőriztünk... mivel ebben a kódban már bízunk, most ezt is elvégezzük:
[norbi@sgu sgu]$ tail hs_alt_Hs_Celera_chr2.fa.lzwtree.txt Ha a d.c-t kicsit megpatkolod, hogy a 0x0A sorvége jeleket ne egye meg, akkor így módosul az eredmény (mindkét változatot elfogadom)
---------------------------------------------0(14)
---------------------------------------------------1(16)
------------------------------------------------------0(17)
------------------------------------------------0(15)
------------------------------------0(11)
---------------------------1(8)
------------------------0(7)
melyseg=1051
altag=74.354451
szoras=11.285391
#include <stdio.h>a futtatás (2+6 giga lesz kb....)
#include <unistd.h>
int
main (void)
{
int i, egy_e;
unsigned char b;
while (read (0, (void *) &b, sizeof (unsigned char)))
{
if (b == 0x0a)
continue;
for (i = 0; i < 8; ++i)
{
egy_e = b & 0x80;
if ((egy_e >> 7) == 1)
printf ("1");
else
printf ("0");
b <<= 1;
}
}
}
[norbi@sgu sgu]$ ./da <hs_alt_Hs_Celera_chr2.fa >hs_alt_Hs_Celera_chr2.fa.01.das az eredmény így:
[norbi@sgu sgu]$ ./z <hs_alt_Hs_Celera_chr2.fa.01.da > hs_alt_Hs_Celera_chr2.fa.lzwtree.txt.da
[norbi@sgu sgu]$ tail hs_alt_Hs_Celera_chr2.fa.lzwtree.txt.da (A mélység kiiírásán kicsit változtattam, hiszen a kiir fgv. inorder, a számolgatók (átlag, szórás) postorder rendben mennek és egy kasztolás is kellett az átlagnál a helyes eredményhez :) így az aktuális z.c immár ez:
------------------------------------------------------1(17)
---------------------------------------------------------0(18)
---------------------------------------------------1(16)
------------------------------------------------0(15)
------------------------------------0(11)
---------------------------1(8)
------------------------0(7)
melyseg=1962
altag=77.975710
szoras=13.33418
// z.c // // LZW fa építő // Programozó Páternoszter // // Copyright (C) 2011, Bátfai Norbert, nbatfai@inf.unideb.hu, nbatfai@gmail.com // // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see <http://www.gnu.org/licenses/>. // // Ez a program szabad szoftver; terjeszthetõ illetve módosítható a // Free Software Foundation által kiadott GNU General Public License // dokumentumában leírtak; akár a licenc 3-as, akár (tetszõleges) késõbbi // változata szerint. // // Ez a program abban a reményben kerül közreadásra, hogy hasznos lesz, // de minden egyéb GARANCIA NÉLKÜL, az ELADHATÓSÁGRA vagy VALAMELY CÉLRA // VALÓ ALKALMAZHATÓSÁGRA való származtatott garanciát is beleértve. // További részleteket a GNU General Public License tartalmaz. // // A felhasználónak a programmal együtt meg kell kapnia a GNU General // Public License egy példányát; ha mégsem kapta meg, akkor // tekintse meg a <http://www.gnu.org/licenses/> oldalon. // // // Version history: // // 0.0.1, http://progpater.blog.hu/2011/02/19/gyonyor_a_tomor // 0.0.2, csomópontok mutatóinak NULLázása (nem fejtette meg senki :) // 0.0.3, http://progpater.blog.hu/2011/03/05/labormeres_otthon_avagy_hogyan_dolgozok_fel_egy_pedat // #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <math.h> typedef struct binfa { int ertek; struct binfa *bal_nulla; struct binfa *jobb_egy; } BINFA, *BINFA_PTR; BINFA_PTR uj_elem () { BINFA_PTR p; if ((p = (BINFA_PTR) malloc (sizeof (BINFA))) == NULL) { perror ("memoria"); exit (EXIT_FAILURE); } return p; } extern void kiir (BINFA_PTR elem); extern void ratlag (BINFA_PTR elem); extern void rszoras (BINFA_PTR elem); extern void szabadit (BINFA_PTR elem); int main (int argc, char **argv) { char b; BINFA_PTR gyoker = uj_elem (); gyoker->ertek = '/'; gyoker->bal_nulla = gyoker->jobb_egy = NULL; BINFA_PTR fa = gyoker; while (read (0, (void *) &b, 1)) { // write (1, &b, 1); if (b == '0') { if (fa->bal_nulla == NULL) { fa->bal_nulla = uj_elem (); fa->bal_nulla->ertek = 0; fa->bal_nulla->bal_nulla = fa->bal_nulla->jobb_egy = NULL; fa = gyoker; } else { fa = fa->bal_nulla; } } else { if (fa->jobb_egy == NULL) { fa->jobb_egy = uj_elem (); fa->jobb_egy->ertek = 1; fa->jobb_egy->bal_nulla = fa->jobb_egy->jobb_egy = NULL; fa = gyoker; } else { fa = fa->jobb_egy; } } } printf ("\n"); kiir (gyoker); extern int max_melyseg, atlagosszeg, melyseg, atlagdb; extern double szorasosszeg, atlag;
Katt a továbbra a teljes forrásért:
printf ("melyseg=%d\n", max_melyseg-1); /* Átlagos ághossz kiszámítása */ atlagosszeg = 0; melyseg = 0; atlagdb = 0; ratlag (gyoker); // atlag = atlagosszeg / atlagdb; // (int) / (int) "elromlik", ezért casoljuk // K&R tudatlansági védelem miatt a sok () :) atlag = ((double)atlagosszeg) / atlagdb; /* Ághosszak szórásának kiszámítása */ atlagosszeg = 0; melyseg = 0; atlagdb = 0; szorasosszeg = 0.0; rszoras (gyoker); double szoras = 0.0; if (atlagdb - 1 > 0) szoras = sqrt( szorasosszeg / (atlagdb - 1)); else szoras = sqrt (szorasosszeg); printf ("altag=%f\nszoras=%f\n", atlag, szoras); szabadit (gyoker); } // a Javacska ONE projekt Hetedik Szem/TudatSzamitas.java mintajara // http://sourceforge.net/projects/javacska/ // az atlag() hivasakor is inicializalni kell oket, a // a rekurziv bejaras hasznalja int atlagosszeg = 0, melyseg = 0, atlagdb = 0; void ratlag (BINFA_PTR fa) { if (fa != NULL) { ++melyseg; ratlag (fa->jobb_egy); ratlag (fa->bal_nulla); --melyseg; if (fa->jobb_egy == NULL && fa->bal_nulla == NULL) { ++atlagdb; atlagosszeg += melyseg; } } } // a Javacska ONE projekt Hetedik Szem/TudatSzamitas.java mintajara // http://sourceforge.net/projects/javacska/ // az atlag() hivasakor is inicializalni kell oket, a // a rekurziv bejaras hasznalja double szorasosszeg = 0.0, atlag = 0.0; void rszoras (BINFA_PTR fa) { if (fa != NULL) { ++melyseg; rszoras (fa->jobb_egy); rszoras (fa->bal_nulla); --melyseg; if (fa->jobb_egy == NULL && fa->bal_nulla == NULL) { ++atlagdb; szorasosszeg += ((melyseg - atlag) * (melyseg - atlag)); } } } //static int melyseg = 0; int max_melyseg = 0; void kiir (BINFA_PTR elem) { if (elem != NULL) { ++melyseg; if (melyseg > max_melyseg) max_melyseg = melyseg; kiir (elem->jobb_egy); // ez a postorder bejáráshoz képest // 1-el nagyobb mélység, ezért -1 for (int i = 0; i < melyseg; ++i) printf ("---"); printf ("%c(%d)\n", elem->ertek < 2 ? '0' + elem->ertek : elem->ertek, melyseg-1); kiir (elem->bal_nulla); --melyseg; } } void szabadit (BINFA_PTR elem) { if (elem != NULL) { szabadit (elem->jobb_egy); szabadit (elem->bal_nulla); free (elem); } }
