Newsgroup: it.comp.lang.pascal
Titolo: Compressione di Huffman

Mi servirebbe la procedura per creare l'albero per la compressione di
Huffman su un file di testo.
Chiunque possa postarmela, mi farebbe un piacere.
Saluti
e-mail: 
cam...@infomont.it

Huffman su un file di testo.
Dunque, la creazione dell'albero di Huffman si basa su un principio
molto semplice.
Si calcola dapprima l'occorrenza dei caratteri nel file di input.
Si puo' fare con un vettore del tipo 
var occ : array [ byte ] of longint ;
da inizializzare all'inizio del programma con 
fillchar( occ, 256, 0 ) ;
Dato che l'albero da creare e' binario, si costruisce una *foresta* di
foglie mediante un vettore che contiene inizialmente solo le foglie
che servono (cioe' quelle che contengono un carattere presente nel
file).
Ognuna di queste foglie ha 5 informazioni : il carattere contenuto, il
peso (cioe' il numero di volte che compare nel file), il puntatore al
sottoalbero sinistro, il puntatore al sottoalbero destro e il
puntatore al nodo madre..
Ovviamente, inizialmente tutti i puntatori sono azzerati a NIL.
L'unione di almeno due foglie e' un ramo.
Ogni ramo il cui nodo madre vale NIL viene considerato "orfano".
Questo significa che all'inizio le foglie sono tutte orfane.
I rami orfani sono gli unici candidati per la creazione di altri rami.
Vengono scelti a due a due in base al peso minore e viene creato un
unico ramo che somma i loro due pesi.
Si continua cosi' fino a quando non rimane un unico ramo, che coincide
con l'intero albero.
Dirlo a parole e' molto piu' complicato che programmarlo.
In ogni caso, devi avere una buona conoscenza dei puntatori e degli
alberi binari in pascal.
Io ho scritto qualche tempo fa un programma in C che calcola i codici
di Huffman per il ng it.comp.lang.c e lo conservo tra i sorgenti di
una mia libreria.
Nel caso ti interessasse (anche per una eventuale traduzione da C a
pascal) te lo posso spedire.
Andrea Laforgia

relativa procedura in Pascal te ne sarei grato.
Tutto quello contenuto tra le direttive $IFDEF...$ENDIF non e'
strettamente necessario :
{$DEFINE DEBUG }
const MAXLONGINT : longint = $7FFFFFFF ;
type p_foglia = ^foglia ;
     foglia = record
                c : char ;
                peso : longint ;
                sin, des, su : p_foglia ;
              end ;
var occ  : array [byte] of longint ;
    ramo : array [byte] of p_foglia ;
    t    : file ;
    c    : byte ;
    i    : byte ;
    j    : byte ;
    radice : p_foglia ;
    function indice_foglia_peso_minimo(max : byte) : byte ;
    var i, p : byte ;
        peso : longint ;
    begin
      p := 0 ;
      peso := MAXLONGINT ;
      for i := 0 to max-1 do
        if (ramo[i]^.su = nil) and
           (ramo[i]^.peso < peso) then
        begin
          p := i ;
          peso := ramo[i]^.peso ;
        end ;
      indice_foglia_peso_minimo := p ;
    end ;
    function crea_albero(max : byte) : p_foglia ;
    var min1, min2 : byte ;
        p : p_foglia ;
    begin
      while (max > 1) do
      begin
        min1 := indice_foglia_peso_minimo(max) ;
        p := ramo[max-1] ;
        ramo[max-1] := ramo[min1] ;
        ramo[min1] := p ;
        min2 := indice_foglia_peso_minimo(max-1) ;
        new(p);
        p^.su := nil ;
        p^.sin := ramo[min2] ;
        p^.des := ramo[max-1] ;
        ramo[min2]^.su := p ;
        ramo[max-1]^.su := p ;
        p^.peso := ramo[min2]^.peso + ramo[max-1]^.peso ;
        ramo[min2] := p ;
        max := max-1 ;
      end ;
      crea_albero := p ;
    end ;
{$IFDEF DEBUG}
var s : string ;
    procedure scrivi_codici(r : p_foglia) ;
    begin
      if (r <> nil) then
      begin
        if (r^.sin <> nil) then
        begin
          s := s + '0' ;
          scrivi_codici(r^.sin) ;
          s[0] := chr(ord(s[0])-1) ;
        end ;
        if (r^.des <> nil) then
        begin
          s := s + '1' ;
          scrivi_codici(r^.des) ;
          s[0] := chr(ord(s[0])-1) ;
        end;
        if (r^.sin = nil) and (r^.des = nil) then
          writeln(r^.c,' : ', s) ;
      end;
    end;
{$ENDIF}
begin
  assign(t, 'testo.txt') ;
  reset(t, 1) ;
  { inizializzazione variabili globali }
  fillchar(occ, sizeof(occ), 0) ;
  fillchar(ramo, sizeof(ramo), byte(nil));
  j := 0 ;
{IFDEF DEBUG}
  s := '' ;
{ENDIF}
  { calcolo delle occorrenze dei caratteri nel testo }
  while not eof(t) do
  begin
    blockread(t, c, 1) ;
    inc(occ[c]) ;
  end ;
  { costruzione delle foglie dell'albero }
  for i := 0 to 255 do
    if (occ[i] > 0) then
    begin
      new(ramo[j]) ;
      ramo[j]^.sin  := nil ;
      ramo[j]^.des  := nil ;
      ramo[j]^.su   := nil ;
      ramo[j]^.peso := occ[i] ;
      ramo[j]^.c    := char(i) ;
      inc(j) ;
    end ;
{$IFDEF DEBUG }
   for i := 0 to 255 do
     if ramo[i] <> nil then
       writeln(ramo[i]^.c, ' (',ramo[i]^.peso,')');
{$ENDIF }
   radice := crea_albero(j) ;
{$IFDEF DEBUG}
   scrivi_codici(radice) ;
{$ENDIF}
  close(t) ;
end.
--
Posted from 
itaca.ulysse.it
 [195.223.254.1]
via Mailgate.ORG Server - 
http://www.mailgate.org