Featured Post

Helppo ja nopea kolmionpiirtorutiini.

Vau. Kehitys kehittynyt ja oppi opittu. public static void SolidTriangle(Point a, Point b, Point c, Color color) {             Point[] po...

Monday, May 11, 2009

Oma sen on oltava, kompressorinkin, eli Sanakirja-enkoodausta, osa 2

Ensin, tehovinkki:
RAMDrivet on kiveja. Nykykoneissa on 2-4G muistia, joten luo sellainen ja osoita oma Temp-kansio ja mahdollisesti oma Swap-file sinne. Eron huomaa.

Myös pelien datatiedostojen nakkelu RAM-drivelle ja .ini tiedostojen osoitus sen suuntaan on hauska temppu.

mO_Om

Hm. Viime keväänäkin oli virtaa ja tapahtui asiossa. Paino kävi tänään 96.5:ssä. Viel on siinäkin tekemistä. Lisää kaurapuuroa.

Onko se muuten ironista jos ei saa luettua "kuinka saa projektit tehtyä" - kirjaa?

Asiaan:
Kauan sitten jotain mietin asiasta, ja kauan se seisoi. Tänään sain koodia vääntymään, suurinpiirtein kuvatunlaisella algoritmilla, eli noin epätäsmällisesti:
  • luetaan syötettä merkki kerrallaan, jokainen merkkiyhdistelmä up to "maksimi sananpituus" laitetaan sanakirjaan. Eli, jos syöte on abcdef, sanakirjaan tulee sanat a, ab, abc, abcd, abcde ja abcdef.
  • Sortataan sanakirja niin että toistojen määrä * sanan pituus toimii painona. 
  • Sortatuilla sanoilla ruvetaan poistamaan stringistä palasia. Eli, jos sanakirja on _talo, talo, _, n, na, ja syöte on "talo_talon_talona" niin siitä on ekan poiston jälkeen jäljellä "talo", "n", "na". 
Tuossa olen menossa, mutta meni tappeluksi kun yritin raakasti pelata nollaterminoidun c-stringin kanssa.

Oikea ratkaisu on hajoittaa syöte puiksi. 


En tiedä selventääkö tuo yhtään asiaa, mutta suusanallisesti, teemme luokan / structin joka sisältää tekstinpätkän, pointterin sanakirjan sanaan ja vasemman ja oikean lapsen.

Homma etenee näin:
  • syötteestä poistetaan ensimmäinen '_talo', jolloin meille jää "talo" ja "n_talona" blobit. Vasemmalla ei koskaan ole syötettä. Luodaan ylin silmu, jonka teksti = null, sana -> "_talo", vasen lapsi on silmu jonka teksti = "talo" ja oikea on silmu jonka teksti on "n_talona". 
  • Jatketaan oikeaan silmuun ja analysoidaan sen teksti, joka hajoaa osiksi "n", ja "na". Asetetaan silmun sana -> "_talo", vasen lapsi -> "n", oikea "na"
  • Analysoidaan oikea - siellä ei ole mitään.
  • Seuraava sana lähtee analysoimaan puun silmuja, joissa teksti != null.
Puussa kuljetaan alimpaan vasempaan, minkä jälkeen parent-silmun kautta oikean noden vasempaan etc. Tämäntyyppisen puussa kulkemisen voi hoitaa rekursiolla.

Mites sitten jos halkaistaan solmu jolla on lapsia?  puoliskoista tulee lapsien vanhempia. 

Eli, jos bab:llä on c-lapset ja halkaistaan a pois, niin syntyy a-node jolla on vasen b ja oikea b. 
Silmujärjestys on aina vasen-parent-oikea-ylös. Ei pitäisi olla vaikeaa. Kai. katsotaan lisää sitten taas joskus.

1 comment:

  1. PS. tuollaiset sanat riittävät puussa jossa max. sananpituus on 5. Täysin parsimattomassa puussa on len - max_word_len sanaa, noin suurinpiirtein.

    ReplyDelete