Bináris fa tárolása?
Biráris fa adatait szeretném eltárolni a lehető leggazdaságosabban, természetesen úgy, hogy a fa az állományból visszaállítható legyen.
A tárolandó adatok tipusa byte.
Előre is köszönöm.
válasza:"és nem szükséges fölöslegesen pakolni a nullákat."
Hát ez meg pont az hogy csomópontonként +2 bit...csak nem előre kigyűjtve, hanem a streamben folyamatosan.. így sokkal egyszerűbb a mentés és viszsatöltés is.
ma 10:32, igen, ez a bajom, hogy esetenként túl sok bitet kell eltárolni. A dolgot árnyalja, hogy a legtöbb fa nem lesz ilyen terjedelmes, tehát itt a csomópontonként nem 10 hanem csak 9 bitnek hosszú távon lehet, hogy lesz akkora hozadéka, hogy megérje mégis ezt alkalmazni. Ezt most még nem tudom.
Az algoritmus komplikáltsága nem jelent problémát, a hardver bírni fogja. Egyéb dolga nem sok minden lesz. Egy z80 proci, 20 Mhz-en.
válasza:Ha ennyire számít a kevés bit inkább az értékeket kéne valahogy tömöríteni.. azokról mit lehet tudni?
Mert ha pl. jellemzően csak 10 alattiak vagy iylesmi, akkor lehet elég takarékosan tárolni.
válasza:Én inkább biztosra mennék a csomópontonkénti 10 bittel.
Az általad leírt algoritmus egyébként sem +1 bit/csomópont, hanem a csomópontszám utána legközelebbi 2 hatvány (-1) darab.
Plusz egyéb adatokat is kell tárolni, pl hány szintje van a fának. (Hogy addig olvasd meg a map-et.)
Tehát eléggé erős feltételek esetén fogja csak megközelíteni a 9bit/csomópontot, míg a másik algoritmussal mindig fixen 10bit/csomópont lesz. Semmi egyéb adatot (darabszám, szintszám, stb) nem kell tárolni. És bármilyen fára működik..még ha az egy láncolt lista is, elágazás nélkül.
ma 12:43: Nem jól látod. Az 1 bit / csomópont az áll, csak teljes fára vonatkoztatva. Sőt, a gyökérelem bitjét le sem kell tárolni, mert az úgyis "van". Fixen az állomány második byte-ja. Ez a spórolás talán fölöslegesnek hat, de ha azt vesszük, hogy nem mindig osztható a csomópontok száma nyolccal, akkor némi értelmet nyer. Az 1 bit egy bytettal rövidebb állományt is jelenthet adott esetben. Sok munka meg nincs vele. Csak ki kell hagyni.
Egyéb adatot (darabszám, szintszám, stb) nem kell tárolni, hiszen a csomópontok számát letárolom az első byteban, ez biztosítja az olvasandó elemszámot és a MAP offsetjét az állományban. A szintszám meg adja magát. Felülről lefelé haladva.
Ha a MAP <> (length(MAP) div 8) akkor ezzel, mármint a bitfüzér valóságos végével sem kell törődnöm, mert a csomópontok száma ismert.
Ezen túl, valóban nem kizárt, hogy a 10 bit / csomópont lesz a nyerő. Még nem tudom a választ, mert látok kihasználatlan lehetőségeket a MAP-es megoldásban.
válasza:Mit nem látok jól? Az első bájton eltárolod a csomópont számot, nem? Vagy mért a második bájttól kezdődik a fa?
Persze az "úgyis van" dolgokat ki lehet hagyni... pl ha tudod, hogy mindig van az gyökér jobb oldali gyerekének egy bal oldali gyereke máris spórolsz 3 bitet:) Ezt azért már nevetségesnek találom.
A te algoritmusoddal soha nem fogod elérni a 9bit/csomópontot.
Írj egy példát légyszives egy nem teljes fára, hanem ami csak 1 szinttel túllóg mint a minimális.
Tehát pl. 14 csomópont 5 szint (a minimális 4 helyett)... lássuk hány bitet fogsz tárolni a te algoritmusoddal.
Talán félreérthetően írtam. Ahogy én képzelem az állomány szerkezetét az a következő.
Az első byte a csúcsok száma (n).
A 2. byte és a következők az n+1. byte-ig a csúcsok értékei.
Az n+2. byte-tól kezdődően (az állomány végén) foglal helyet a MAP.
A teljes MAP összes bitjeinek száma mindig nyolccal osztható, mert ugye az is byte-ok összessége (és ugye 34 bitet nem tudunk leírni csak 40-et), viszont az utolsó byte-ban nem tudni, hogy hány, érdemi információt hordozó bit van. Ez azonban nem is érdekes, mert a csúcsok számából, amit a legelső byte tartalmaz, már pontosan tudjuk, hogy meddig kell olvasnunk a MAP-et.
További kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!