@ Michael M, nu au înțeles cu adevărat cum să "răsucească" copacul dacă are o structură mai complexă decât în exemplul tău. Și nu este foarte clar ce înseamnă "adâncime inițială" și "nu se dezvoltă" și cum se poate restaura arborele de la aceste informații. M-am gândit puțin mai mult și m-am gândit cum să salvez toate informațiile în 478 octeți, indiferent de mărimea datelor de intrare, o să scriu mai târziu în răspunsul meu. - dzhioev Dec 27 '13 la 9:03 am
> 478 octeți, indiferent de dimensiunea datelor de intrare, voi scrie mai târziu> în răspunsul meu Asigurați-vă că scrieți. Vom reface toate arhivele. - uzumaxy 27 decembrie '13 la 13:12
Adâncimea inițială este adâncimea foii din stânga. Prima schimbare este diferența dintre adâncimea celei de-a doua stânga a colii și a celei din stânga. Arborele este restabilit fără ambiguități. Ne uităm la adâncimea inițială - lăsăm așa în stânga. Adăugăm foaia în conformitate cu primul simbol înregistrat. Dacă în continuare "crește" - pe "fratele" său, mergem atât de profund, dacă nu - adăugăm o foaie la același nivel. Etc. 478. Probabil ați crezut că vreți să vă concentrați cu o mască mică pentru toate cele 256 de caractere. Probabil, este posibil să jucați pe împrăștierea copacilor. Cu toate acestea, 478> 2 biți * 255 + 256 octeți - Michael M Dec 27 '13 la 13:12
Nu este necesar să salvați copacul. Puteți salva contoarele pentru fiecare caracter la începutul fișierului și puteți restaura arborele înainte de decodificare. Dacă stocați contoare de 8 octeți, veți avea nevoie de 8B * 256 = 2KiB, care nu este deloc deloc.
UPD. dacă vă pare rău pentru 2KiB, atunci puteți stoca contoarele mai compact. De exemplu, introduceți următorul format pentru contor: prefix + contra. Prefixul este un număr întreg de trei biți egal cu dimensiunea contorului în octeți. exemple:
- Contorul este 0. Salvat în 000 (3 biți).
- Contorul este 222. Este stocat în 00111011110 (11 biți).
- Contorul este 1024. Acesta este stocat în 0100000010000000000 (19 biți).
Ie mărimea datelor stocate pentru contorul n va fi egală cu ceil (ceil (log_2 (n)) / 8) * 8 + 3 biți.
UPD2. a venit cu o altă cale, care, mi se pare, este mai bună decât cea anterioară. În primul rând, voi descrie ce implementare a algoritmului pentru construirea unui copac pe care o voi folosi:
Dacă te uiți atent la codul, putem înțelege că, pentru a restabili copac topologie dostatotochno ne în linia de start-up de caractere și noduri INSERT_INDEX pe fiecare dintre pașii. Contelează cât de multă memorie este nevoie.
Pentru a stoca permutarea inițială, aveți nevoie de 255 de octeți (nu puteți stoca primul / ultimul caracter, dar obțineți-l printr-o metodă de excepție).
Notă de asemenea, că numărul de iterații ale algoritmului este fix (255) și pe iteratie i-lea (numărând de la zero) INSERT_INDEX se află în intervalul [0, 255 - i), astfel încât să putem la iterații ulterioare aloca mai puțini biți pentru a INSERT_INDEX de stocare. Mai exact:
Ie hraneniya pentru a insera indici au nevoie de 127 * 8 + 64 * 7 + 32 * 6 + 16 * 5 + 8 * 4 + 4 * 3 + 2 * 2 = 1784 biți = 223 octeți.
În total avem 255 + 223 = 478 octeți, iar acest număr nu depinde de dimensiunea datelor de intrare, spre deosebire de metoda descrisă mai sus.
Trimiteți-le prietenilor: