HTML

Programozó Páternoszter

Ez a Programozó Páternoszter (PP) blogja, a programozásról szól. Aktualitása, hogy a Debreceni Egyetem Informatikai Kara Magasszintű programozási nyelvek 1-2, C++ esattanulmányok, Java esettanulmányok című kurzusainak blogja is egyben.

A vadászat

A Debreceni Egyetem Programozói Évkönyve: az UDPROG projekt. A szakmai fórumunk a Facebook-en. Az új előadások a prezin.
A régi előadások:
Prog1:
1. C bevezetés
2. C tárgyalás
3. C befejezés
4. C a gyakorlatban
5. C++ bevezetés
6. C++ tárgyalás
7. C++ befejezés
8. C++ a gyakorlatban
9. Java platform bevezetés
10. Kvantuminformatikai alg. bev.
Prog2:
1. Java bevezetés
2. Java tárgyalás
3. Java befejezés
4. Java a gyakorlatban
5. Software Engineering bev.
6. Java EE bevezetés
7. AspectJ bevezetés
8. BPMN-BPEL SOA programozás
9. C++ haladó
10. Tensorflow

Kövess engem!

Friss topikok

Linkblog

Játék a betűkkel: TCAG, avagy a Humán Genom Projekt

2012.03.12. 13:59 nb

Az elmúlt héten többen szóvá tették, hogy Ők nem olvasták a labor posztját, ezért nem tudták, hogy pontosan milyen olvasmányélményekkel kell, hogy a laborra rendelkezzenek. A hallgatói laborkártya kezdeményezés kb. olyan, mint amikor a magyar tanárod rákérdezett, hogy "a madáchi tragédiában Évának hányadik gyermeke volt a leány?" Amivel ugye csak arra volt kíváncsi, olvastad-e a művet? A mi analóg (így szabadon feldobott) kérdésünk az volt a struktúrás fejezet kapcsán, hogy írjuk át a szereplő struct date *dp; mutatót használó dp->year-t a . operátort felhasználva. Szerencsére jeles hallgatóim tudták a választ (az örök igazság itt is áll: nem tanulni kell, tudni). Ilyesmi ellenőrző kérdésekre is számíts, de ha olvasgatod a kiadott részeket, nem lehet gond.

Ne feledd: a kurzus szervezésének sorodvonala ez a blog!

Aki lemaradt a laboron, itt egy segítő poszt még tavalyról: Labormérés otthon, avagy hogyan dolgozok fel egy pédát (foglalkozz vele, mert a védendő C++ kb. ugyanez lesz, de itt még a C változat ketyeg). A működésben pedig hasonló a feladott kötelező olvasmány példája.

A C programzónak a bitfaragás olyan, mint a katonának a takarítás, ennek jegyében ismételjünk a labor bemelegítéseként: aki megmagyarázza először a Linux kernelbeli static inline const char *get_task_state(struct task_struct *tsk) függvény bitfaragását egy kommentben elsőként, az 2 trófeát zsebelhet be ezért! Legyél gyors, mert ugyanezzel a fóliával kezdjük holnap az előadást, addig és a kihívás :)

(Kis help a Linux kernel hacking megkezdéséhez itt.)

Jöjjön a szakma:

A UNIX típusú rendszerekben a fork() a mitózis.

Rántsuk le az emberi genom 2. kromoszómájának egy részét:

ftp.ncbi.nlm.nih.gov/genomes/H_sapiens/Assembled_chromosomes/seq/ (már az új fájlneveket használtuk az elmúlt héten). T, C, A, G betűkkel találkozunk, ahogyan hármasával egy fehérjét kódolnak. A következő kis progival (mivel nem feledhetjük, hogy kezdő programozók is vannak köztünk, ezért az ilyen egyszerűekkel is foglalkoznunk kell ter) tehát a következő kis progival átkódoljuk a sorozatot, a Javát tanítok  www.tankonyvtar.hu/informatika/javat-tanitok-1-1-1-080904 TCAG2Hexa osztályának mintájára két nukleotid bázisból egy hexadecimális betűt készítünk:

#include <stdio.h>
#include <unistd.h>

int
main (void)
{      
  char hexa_jegyek[] = {'A', 'B', 'C', 'D', 'E', 'F'};
  
  int paratlan = 0, elso=0, masodik=0, i = 0;
  
  while((i=getchar()) != EOF) {
    
    switch(i) {
      
    case 'T':
      masodik = 0;
      break;
    case 'C':
      masodik = 1;
      break;
    case 'A':
      masodik = 2;
      break;
    case 'G':
      masodik = 3;
      break;
    }
    
    if(paratlan) {
      
      int jegy = 4*elso + masodik;
      
      if(jegy<10)
	printf("%d", jegy);
      else
	printf("%c", hexa_jegyek[jegy-10]);
      
    }
    paratlan = !paratlan;
    elso = masodik;                        
  }        
} 

Az alábbi kis játék során megismerkedünk a (2. előadásban bevezetett) CompLearn csomag használatával.

  • Rántsuk le a humán genom 2. kromoszómájának első 1400 betűjét ftp.ncbi.nlm.nih.gov/genomes/H_sapiens/CHR_02/ (amit a hs_alt_Hs_Celera_chr2.fa.gz név alapján Hschr21400 néven mentünk most el, alul majd helso.human1minta)!
  • Generáljunk le 1000 hexa jegyet a Pi kifejtésének 1.000.000. jegyétől (piezer.txt, alul majd piezer.1000000)!
  • Az első előadás pszeudorandom kártyájával és a fenti tcag2hex kiírás további finomításával
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <sys/types.h>
    #include <unistd.h>
    int
    main (void)
    {
      int i, r;
      srand (time (NULL) + getpid ());
      for (i = 0; i < 2000; ++i)
        {
          r = (int) (16.0 * rand () / (RAND_MAX + 1.0));
    
          if (r < 10)
    	printf ("%d", r);
          else
    	printf ("%c", r - 10 + 'A');
    
        }
      printf ("\n");
      return 0;
    }
    
    nyomtassunk ki 2000 db véletlen jegyet (veletlen2000, alul majd rand.2000db)!
  •  Rántsunk még le a 3. emberi koromóból is 700 betűt (Hschr3700)!
  •  A C elegans fonalféreg II. kromójából is vegyünk valamekkora mintát (c2_2000) ftp.ncbi.nlm.nih.gov/genomes/Caenorhabditis_elegans/CHR_II/NC_003280.fna (ez a féreg közel áll a szívünkhöz az Orch OR tudatmodell miatt is, alul majd celeg.celegans)
  • ... s készítünk még pár mintát... a kutya (canis familiaris), a ló (equus caballus), a kakas (gallus gallus), a szarvasmarha (bos taurus) 2. kromójának elejéből, a Pi kifejtéséből, a csupa 1 jegyből, a 01-ekből álló állományokból:

batfai@kalapacs:~ $ ls -l mintak/
összesen 72
-rw-r--r-- 1 batfai batfai 2100 2011-02-27 18:49 celeg.celegans
-rw-r--r-- 1 batfai batfai  800 2011-02-27 18:20 egyes.8001es
-rw-r--r-- 1 batfai batfai 3220 2011-02-27 21:14 h11kromo.eleje
-rw-r--r-- 1 batfai batfai 3080 2011-02-27 21:17 h11kromo.kozepe
-rw-r--r-- 1 batfai batfai 3260 2011-02-27 21:16 h11kromo.vege
-rw-r--r-- 1 batfai batfai 1400 2011-02-27 17:24 helso.human1minta
-rw-r--r-- 1 batfai batfai  700 2011-02-27 17:24 hmaso.human2minta
-rw-r--r-- 1 batfai batfai 3448 2011-02-27 18:44 kakas.2k
-rw-r--r-- 1 batfai batfai 1400 2011-02-27 21:02 kutya.1400
-rw-r--r-- 1 batfai batfai 1190 2011-02-27 21:09 kutya.kozepe
-rw-r--r-- 1 batfai batfai 1127 2011-02-27 21:09 kutya.vege
-rw-r--r-- 1 batfai batfai 1190 2011-02-27 18:45 lo.2k
-rw-r--r-- 1 batfai batfai 1600 2011-02-27 18:27 nulegy.800par
-rw-r--r-- 1 batfai batfai 1000 2011-02-27 18:39 pi1000.0tol
-rw-r--r-- 1 batfai batfai 2000 2011-02-27 18:35 pi2000.0tol
-rw-r--r-- 1 batfai batfai 1000 2011-02-27 17:25 piezer.1000000
-rw-r--r-- 1 batfai batfai 2000 2011-02-27 17:24 rand.2000db
-rw-r--r-- 1 batfai batfai  700 2011-02-27 20:57 szarvasm.700
batfai@kalapacs:~ $
S lássuk, mit mutat ezekre a mintákra a CompLearn normalizált tömörítési távolsága alapján készített gráfja:

ncd -b -d mintak/ mintak/
maketree distmatrix.clb
neato -Tpng treefile.dot > tcag.png


 

A poszt elején említett kódolást a lerántott genetikai kódrészletekre alkalmazva kapjuk a .hex állományokat, ezzel így módosul a gráf:

 

3/5 trófea üti a markát aki ez iménti CompLearn-ös játékot reprodukálja.

Bajnokság van, nevezel?

Íme néhány a genetikai kóddal kapcsolatos új trófea:

  • 2 trófea annak, aki először megmondja, hogy mennyi az LZW fa ághosszainak szórása a humán 2 kromóban lévő genetikai kódnak. A kódot bináris állományként dolgozd fel (előtte persze azért tömörítsd ki :), jöhet kommentben is a megoldás. (A szórást a Jávácska ONE-beli Hetedik Szem (javacska-one-1.0.0-projects.zip / hetedik-szem-1.0.0 / src / main / java / TudatSzamitas.java) kódja alapján fejleszd bele a korábbi kódunkba.)
  • 3 trófea annak, aki először megmondja, hogy mennyi az LZW fa ághosszainak szórása a humán 2 kromóban lévő genetikai kódnak. A kódot tedd át 2 betűnként hexába, aztán a hexa betűkből nyomj 4 bitet betűnként, az így kapott állományt vizsgáld, jöhet kommentben is a megoldás. (A szórást a Jávácska ONE-beli Hetedik Szem (javacska-one-1.0.0-projects.zip / hetedik-szem-1.0.0 / src / main / java / TudatSzamitas.java) kódja alapján fejleszd bele a korábbi kódunkba.)
  • 4 trófea annak, aki először megmondja, hogy mennyi az LZW fa ághosszainak szórása a humán 2 kromóban lévő genetikai kódnak. A kódot karakteresen a szereplő 5 betű alapján vizsgáld, jöhet kommentben is a megoldás. (A szórást a Jávácska ONE-beli Hetedik Szem (javacska-one-1.0.0-projects.zip / hetedik-szem-1.0.0 / src / main / java / TudatSzamitas.java) kódja alapján fejleszd bele a korábbi kódunkba. A korábbi LZW-s kódunkba ne bináris fát építs, hanem olyat, aminek egy csomópontjából 5 mutató mutat a lehetséges 5 betűvel címkézett gyerek csomópontokra.)
  • (s egy kicsit más jellegű feladat) 1 trófea annak, aki a genetikai kódot a kódnak megfelelő fehérjék sorozatává kódolja, pl.: TGT=Cys, TGG=Trp, TGA=STOP, segít a DNA codon table, jöhet kommentben a kód és egy kis rövid demó minta, hogy lássam jó-e.

Binom trófeák

  • .5 pont a készítőnek, 0.5 pont a binomjának, aki ellenőrzi a megoldást. Maga a feladat pedig tetszőlegesen választott lehet a K&R könyvből.
  • 1 pont a készítőnek, 0.5 pont a binomjának, aki ellenőrzi a megoldást. Maga a feladat pedig tetszőlegesen választott lehet a C++ tankönyvből.

Figyeld a blogot, mert minden feladatból csakis egyet fogadok el ebben a kategóriában!

g.c:

  • Beszéljük meg és teszteljük a g.c-t, itt azt kell kiemelni, hogy hármasával olvassuk a betűket a fájlból, de nagyon rossz gyakorlat, ha a ciklusban ciklusolgatni kezdünk... e helyett egyetlen ciklust használunk:
    // a betűket 3-asával "olvasom": nem kell cifrázni! egy ciklus
    // elvégzi, amiben megjegyzem, hogy melyik hányadik betű volt
    // aki ciklusban ciklusolgat, az már bénázik :)
    int
    main (void)
    {
      // hányadik betűn állok?
      int hanyadik_betu = -1;
      // azon a helyen mit olvastam?
      int elso = 0, masodik = 0, harmadik = 0, i = 0, jegy = 0;
    
      while ((i = getchar ()) != EOF)
        {
    
          switch (i)
    	{
    
    	case 'T':
    	  jegy = 0;
    	  break;
    	case 'C':
    	  jegy = 1;
    	  break;
    	case 'A':
    	  jegy = 2;
    	  break;
    	case 'G':
    	  jegy = 3;
    	  break;
    	}
    
          hanyadik_betu = (hanyadik_betu + 1) % 3;
    
          if (!hanyadik_betu)
    	elso = jegy;
          else if (!(hanyadik_betu - 1))
    	masodik = jegy;
          else
    	{
    	  harmadik = jegy;
    	  printf ("%s", genetikai_kod (elso * 16 + masodik * 4 + harmadik));
    	}
        }
    }
    
    vedd észre, hogy a kód pici továbbfejlesztése a jelen poszt bevezető progijának, csak ott kettesével olvasunk és két betűből készítettünk egy hexadecimális jegyet.
  • Feladat (kisebb sebességű): készíts "aminosav-hisztogramot", azaz a progi továbbfejlesztésével mond meg, melyik aminosav hányszor szerepel? (egy trófea, jöhet kommentben előre is)
  • Hogy változik ez a szám, ha az első kódoló betűt törlöd a bemenő fájlból (azaz a 2. betűtől méred fel a 3 betűket) (egy trófea, jöhet kommentben előre is)
  • Hogy változik ez a szám, ha az első két kódoló betűt törlöd a bemenő fájlból (azaz a 3. betűtől méred fel a 3 betűket) (egy trófea, jöhet kommentben előre is)
  • Feladat (nagyobb sebességű): módosítsd a z.c-t, hogy ne 0, 1 betűkre menjen, hanem a 4 T, C, A, G betűre és így építs fát (ez már nem bináris fa lesz persze), mennyi a 2. kromóra az LZW fa ághosszainak átlaga és sztenderd hibája? (ez 5 trófeát ér, jöhet kommentben is)
  • További két kisbajnokság, aki gyorsabbat ír:
    [norbi@sgu tcag]$ time ./g <hs_alt_Hs_Celera_chr2.fa >aminosavak

    real    0m17.428s
    user    0m16.593s
    sys     0m0.714

g.c

 

// g.c
//
// genetikai kód nyomtató
// 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: szösszenet
//
// A http://progpater.blog.hu/2011/02/27/a_human_genom_projekt poszt
// bevezető kódjának alapötletét használjuk fel, de nem kettesével,
// hanem most hármasával dolgozzuk fel az inputot
//
// Ennek a kódnak a részleteit az itteni kisbajnokikon is
// kamatoztathatod: http://progpater.blog.hu/2011/03/05/szonyegen_a_human_genom

#include <stdio.h>
#include <unistd.h>

// Egyszerűen felsorolom, pl. az alábbi alapján:
// http://en.wikipedia.org/wiki/DNA_codon_table
char *amino_sav[] = {
  "Stop",
  "Phe",
  "Leu",
  "Ile",
  "Met",
  "Val",
  "Ser",			// 6.
  "Pro",
  "Thr",
  "Ala",
  "Tyr",			// 10.
  "His",
  "Gln",
  "Asn",
  "Lys",
  "Asp",
  "Glu",
  "Cys",
  "Trp",			// 18.
  "Arg",			// 19.
  "Gly"				// 20.
};

// a 3 betű melyik aminosavat kódolja?
char *
genetikai_kod (int triplet)
{
  int index = 0;

  switch (triplet)
    {
    case 0:			// Phe
    case 1:
      index = 1;
      break;
    case 2:			// Leu
    case 3:
    case 16:			
    case 17:
    case 18:
    case 19:
      index = 2;
      break;
    case 32:			// Ile
    case 33:
    case 34:
      index = 3;
      break;
    case 35:			// Met
      index = 4;
      break;
// hogy jön ez? az 5 indexű a "Val"
// GTT-től GTG-ig van ez, jegyekben:
// 300-tól 303-ig 4-es számrendszerben
// ez van átváltva, pl.:
//      303(4) -> 3*16+0*4+3*1 = 51(10)      
    case 48:
    case 49:
    case 50:
    case 51:
      index = 5;
      break;
    case 4:
    case 5:
    case 6:
    case 7:
      index = 6;
      break;
    case 20:
    case 21:
    case 22:
    case 23:
      index = 7;
      break;
    case 36:
    case 37:
    case 38:
    case 39:
      index = 8;
      break;
    case 52:
    case 53:
    case 54:
    case 55:
      index = 9;
      break;
    case 8:
    case 9:
      index = 10;
      break;
    case 10:			// Stop
    case 11:
      index = 0;
      break;
    case 24:
    case 25:
      index = 11;
      break;
    case 26:
    case 27:
      index = 12;
      break;
    case 40:
    case 41:
      index = 13;
      break;
    case 42:
    case 43:
      index = 14;
      break;
    case 56:
    case 57:
      index = 15;
      break;
    case 58:
    case 59:
      index = 16;
      break;
    case 12:			// Cys
    case 13:
      index = 17;
      break;
    case 14:			// Stop
      index = 0;
      break;
    case 15:			// Trp
      index = 18;
      break;
    case 28:			// Arg
    case 29:
    case 30:
    case 31:
      index = 19;
      break;
    case 44:			// Ser
    case 45:
      index = 6;
      break;
    case 46:			// Arg
    case 47:
      index = 19;
      break;
    case 60:			// Gly
    case 61:
    case 62:
    case 63:
      index = 20;
      break;

    default:
      // csak tesztelesre a printf
      printf ("Zavar az eroben %d-nel", triplet);
      index = 0;
      break;
    }

  return amino_sav[index];
}

// a betűket 3-asával "olvasom": nem kell cifrázni! egy ciklus
// elvégzi, amiben megjegyzem, hogy melyik hányadik betű volt
// aki ciklusban ciklusolgat, az már bénázik :)
int
main (void)
{
  // hányadik betűn állok?
  int hanyadik_betu = -1;
  // azon a helyen mit olvastam?
  int elso = 0, masodik = 0, harmadik = 0, i = 0, jegy = 0;

  while ((i = getchar ()) != EOF)
    {

      switch (i)
	{

	case 'T':
	  jegy = 0;
	  break;
	case 'C':
	  jegy = 1;
	  break;
	case 'A':
	  jegy = 2;
	  break;
	case 'G':
	  jegy = 3;
	  break;
	}

      hanyadik_betu = (hanyadik_betu + 1) % 3;

      if (!hanyadik_betu)
	elso = jegy;
      else if (!(hanyadik_betu - 1))
	masodik = jegy;
      else
	{
	  harmadik = jegy;
	  printf ("%s", genetikai_kod (elso * 16 + masodik * 4 + harmadik));
	}
    }
}

C elegans fonalféreg

 Az iménti g.c számos hiba forrása is, hiszen a maradékos osztásos "fűrészfog" akkor is dolgozik, amikor nem kéne... addig javítsuk, amíg ez nem jön ki a C elegans fonalféreg II. kromoszómájára, természetesen paramcssorból ránsd le:

wget ftp://ftp.ncbi.nlm.nih.gov/genomes/Caenorhabditis_elegans/CHR_II/NC_003280.fnanbatfai@hallg:~/bevezetes$ ./g </home/nbatfai/NC_003280.fna |tail -n 21
Stop 267497
Phe 445827
Leu 489714
Ile 364670
Met 79613
Val 243280
Ser 450361
Pro 179453
Thr 243056
Ala 175140
Tyr 153251
His 133711
Gln 181261
Asn 275429
Lys 398344
Asp 125314
Glu 199000
Cys 142503
Trp 65033
Arg 303128
Gly 17752

Magam így módosítottam a kódot: g.c

Az aktuális immár ennek kapcsán, hogy egy ugyanazon a gépen gyorsítsd fel ezt a g.c-t további 3/2 pontért, a sebességnövekedést ezzel a paranccsal vizsgáld:

$ time ./g </home/nbatfai/NC_003280.fna |tail -n

GNU/Linux kernel hacking

Azok számára, akik a félévben önálló érdeklődésből a Linux rendszerrel kívánnak közelebbi kapcsolatba kerülni, készítettem egy VirtualBox-OSE-s képet (BatfaiProg1.ova), ahol a PP kernelmodulos példáit aktualizáltam. Az első három 6 évvel a PP születése után (persze a PCB-ből pár tagot gyomlálni kell, a printk pár formátumparaméterét hangolni stb.) is simán megy, a negyedikkel van több hiba, például a "[PATCH -mm 7/3] proc: remove proc_root from drivers" stb. miatt. Nyilván a szóban forgó virtualizált rendszeren már minden javítva van (ez azért sokat segít az előző poszt kiírt Linuxos trófeáihoz). A negyedik modult, már a hardcore programozóknak javaslom, az első három kell mindenkinek persze :) Itt a negyedikről a bizonyítékom, hogy műxik:

s itt egy kis további help ehhez.

Hallgatói laborkártyák

Természetesen a korábbiak mellett (l. a korábbi posztot)

 

85 komment

Címkék: kutya pi kakas dns fehérjék homo sapiens szarvasmarha hexa c elegans humán genom canis familiaris tcag equus caballus gallus gallus bos taurus genetikai kód prog1

Gyönyör a tömör újratöltve

2012.03.04. 11:54 nb

Ez a poszt a ott folytatódik, ahol a feb. 29-i előadást befejeztük, őse a tavalyi Gyönyör a tömör poszt. Aktuális, hogy a "elit képzést" felvevő hallgatók soraiban immár felütötte a fejét a kétségbeesés. Olyan jelekben nyilvánul ez meg, mint például: "nem értem a könyvet". Nincs ezzel az érzéssel semmi gond, azért jelentkezik, hogy tegyél ellene: többet olvasd a könyvet, többet  programozz, beszélj kérdéseidről a binomoddal, dobd be itt a blogon stb.! Ez az érzés tk. meg fog menteni a bukástól, de azért nem akarom túlnyugtatni az olvasót. Mert az teljesen rendben van, hogy most még nem ért valamit, de az nincs rendben, hogy e mellett nem csinálja a kiadott feladatokat: sem a választhatókat, sem a sima, sem a hallgatói laborkártyákat! Szóval ne féljetek, de a félelmeteket csakis a megértés és a tudás tudja eloszlatni; élvezzétek a programozást, még akkor is, ha nehezebben jönnek a sikerélmények, magában a programozás "csinálásában" is találhatjátok meg az örömötöket és a dolgok jóra fordulnak, sőt talán még a források is lefordulnak :)

Pillanatkép a 2012. márc. 7-i előadásból:

Konkrét tanácsom pedig, hogy gyertek felkészülten a laborra, ami azt jelenti, hogy a poszt publikálása után dolgozzátok is fel azt, íme jöjjön hát akkor most jóelőre az anyag:

man compress:

DESCRIPTION
       The  compress  utility  shall attempt to reduce the size of the named files by using adaptive Lempel-Ziv coding algorithm.

       Note:  Lempel-Ziv is US Patent 4464650, issued to William Eastman, Abraham Lempel, Jacob Ziv, Martin Cohn on August 7th, 1984, and assigned to Sperry Corporation.

       Lempel-Ziv-Welch  compression  is  covered  by US Patent 4558302, issued to Terry A. Welch on December 10th, 1985, and assigned to Sperry Corporation."
de már jópár éve lejárt a szabadalmi oltalom, egyik eredmény: a gif visszaszorult, a png elterjedt. (A Lempel-Ziv-Welch algoritmust használja a gif formátuma, sok tömörítő, például a compress, gzip, zip.)
Az algoritmus remek leírását találjuk a Rónyai-Iványos-Szabó Algoritmusok könyvben. Alább egy naivabb  implementációt adunk a Tusnády: Sztochasztikus számítástechnika című könyv alapján: jön a 0-1 sorozat, betűnként olvassuk, ha olyan rész jön, ami még "nincs a zsákban", akkor "letörjük és be a zsákba":

00011101110 -> 0 00 1 11 01 110

 a tördelést egy bináris fával könnyen meg tudjuk valósítani:

                 / 
       0             1
   0      1              1
                       0

Így használd:

[norbi@sgu C]$ more b.txt
00011101110
[norbi@sgu C]$ gcc z.c -o z -std=c99
[norbi@sgu C]$ ./z < b.txt
00011101110
---------1
------------0
------1
---/
---------1
------0
---------0

 A kód  immár nem csak képpel:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.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 szabadit (BINFA_PTR elem);

int
main (int argc, char **argv)
{
  char b;

  BINFA_PTR gyoker = uj_elem ();
  gyoker->ertek = '/';
  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;
  printf ("melyseg=%d", max_melyseg);
  szabadit (gyoker);
}

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);
      for (int i = 0; i < melyseg; ++i)
	printf ("---");
      printf ("%c(%d)\n", elem->ertek < 2 ? '0' + elem->ertek : elem->ertek,
	      melyseg);
      kiir (elem->bal_nulla);
      --melyseg;
    }
}

void
szabadit (BINFA_PTR elem)
{
  if (elem != NULL)
    {
      szabadit (elem->jobb_egy);
      szabadit (elem->bal_nulla);
      free (elem);
    }
}

3 kisbajnokság

Annak, aki először megmondja, hogy a esr.fsf.hu/hacker-howto.html lap bitenként nézve milyen mély ilyen "Ziv-Lempel" fát épít fel. Tipp: írj egy dump progit, ami 0-1 karakterekben kiköpi a bináris bemenetét és tedd ezt:

[norbi@sgu C]$ wget http://esr.fsf.hu/hacker-howto.html
[norbi@sgu C]$ cat hacker-howto.html|./d >hacker-howto.html.01
[norbi@sgu C]$ more hacker-howto.html.01
ezt már megeszi a fenti kód, csak ki kell íratnod a mélységet. (Ne feledd: a laborteljesítés feladata olyasmi lesz, hogy binárisan kell majd feldolgoznod a bemenetet, pontos specifikáció majd később.)

A program a 4. laboron kerül terítékre, de már a harmadikon szerepel majd az említett dump:

 

A laborok teljesítésének egyik szükséges feltétele

Idézet az 1. előadásból:

Labor teljesítésének további szükséges feltétele egy saját program
bemutatása a laborközösség előtt, a félév közepén. A feladat kötött:
adok egy karakterekre (0,1 betűkre) működő algoritmust, azt kell
átírni, hogy bináris bemenetre (0, 1 bitekre) működjön (lásd 3 előadás
és labor). A félév végén pedig egy saját robofocis fejlesztés
bemutatása.

Illetve idén már csak a C++ változat lesz védhető, de éppen ezért addig még van néhány előadás.

A karakterekre működő LZW fa építő most szerepelt, de binárisra úgy engedtük rá, hogy azt először az iménti dump progival karakteres 0,1 állománnyá alakítottuk. Most majd olyat kell írnod, ami kapásból binárisat dolgoz fel! Íme a specifikáció:

Állomány: BNbeadando.c (saját monogram, ékezetes betű nincs)
Parancssor:  ./BNbeadando input_fájl_neve -o kimeneti_fájl_neve (ha nem így indítják, kiírja, hogy így kellene használni és leáll)
Kimenet: tartalmazza a 0,1 bináris LZW fát, majd a fa mélységét, végül a fa ághosszainak szórását (utóbbi a negyedik laboron is téma)

(Lesz néhány teszt állomány megadva, ahol előre meg lehet nézni, hogy megfelelően működik-e a kifejlesztett progitok. Aki előre akar dolgozni, itt a poszt, illetve az SVN-ben fent van a d.c, z.c természetesen, a linkelt posztban a fájlnév változott, ezt használd: ftp://ftp.ncbi.nlm.nih.gov/genomes/H_sapiens/CHR_02/hs_alt_HuRef_chr2.fa.gz ennek mélységéért adok 3 trófeát az elsőnek, s ha a hivatkozott poszt szerint a d.c "meghekkelésével" az első sort kidobja, az így kapott mélységért még +2-t.)

Egyéb trófeák:

  • 10/2 Szigorúan titkos
  • 2/6 (+1) Alternatív tabella (+1 minden bajnoki forduló után, ha a wikire is feltöltöd, azért 2 fős, hogy ellenőrizzék egymást, a wikire csak jó számolást töltsünk fel, ellenőrizzük progijainkat a korábban kitett tabellákra)
  • 20/2 fordíts kernelt a Linuxodon (l. 3. ea. megfelelő fóliái)
  • 3/2 készíts olyan kernelmodult, amely kiírja, hány processz van (l. 3. ea. megfelelő fóliái)
  • 3/2 készíts olyan rendszerhívást, amely kiírja, hány processz van (l. 3. ea. megfelelő fóliái)
  • 3/3 készíts olyan kernelmodult, amely kiírja az összes processz néhány általad választott jellemzőjét a PCB-ből (l. 3. ea. megfelelő fóliái)
  • 3/2 készíts olyan kernelmodult, amely kiírja hogy melyik a következő szabad állományleíró (l. 3. ea. megfelelő fóliái)
  • 10/5 írd meg a Linux top parancsát (a PP 89-től alapján, akkor 5 pont, ha legalább ncurses-es)

Kis help a Linux kernel hacking megkezdéséhez itt.

 Többen jelezték, hogy belezavarodtak a hallgatói laborkártyákba, ezért tekintsük át, mit kell ennek kapcsán tudni felmutatni a 03.05 hét laborján:

  • az első 4 fejezetből a 3 kérdés
  • az első 4 fejezetből a binom 3 kérdésének megismerése, megtárgyalása
  • a referencia kézikönyv részből a 3 kérdés
  • a referencia kézikönyv részből a binom 3 kérdésének megismerése, megtárgyalása
  •  s ha már fellapoztuk a könyvet adjunk ki egy aktuális további feladatot: az 5. és 6. fejezetből is kérném a saját három kérdést (ez a "Mutatók és tömbök" és a "Struktúrák" fejezetek)

nem kell papíron, sokkal jobb, ha elektronikus, de be kell tudni mutatni kérésemre!

114 komment

Címkék: tömörítés humán genom linux kernel ziv lempel welch

süti beállítások módosítása