Форум программистов [Powered by Invision Power Board]

Цитата(SergXP @ 8.3.2009, 10:09

)

а это не слишком примитивно?

Цитата(SergXP @ 8.3.2009, 10:52

)

. Если я правильно понял

Код


Результат работы для строки «to be or not to be?». Выводятся: символ, его вес и двоичный код. Далее закодированная строка и результат декодирования.

e  2  000
?  1  0010
n  1  0011
o  4  01
   5  10
t  3  110
r  1  1110
b  2  1111
11001101111000100111101000110111010110011011110000010
to be or not to be?
-----------------------------------------------------------------------
110 01 10 1111 000 10 01 1110 10 0011 01 110 10 110 01 10 1111 000 0010
t   o     b    e      o  r       n    o  t      t   o     b    e   ?
Итого:
53 бита
19 знаков (с пробелами)
2,79 бит/знак
Соответствующее дерево Хаффмана.

       root
      /    \
     0      1
    / \    / \
  00   o "_"  11
 /  \        /  \
e   001     t   111
    / \         /  \
   ?   n       r    b

Цитата(SergXP @ 7.3.2009, 23:24

)

Для обеспечения сохранности информации при хранении

Цитата(SergXP @ 8.3.2009, 11:29

)

а xor подойдет же для файлов?

Код


unit CHuffman;
 
interface
 
uses
  SysUtils, Classes, Dialogs;
 
const
  ALPHABETSIZE = 256;
 
type
  TTree = class;
  THuffman = class;
 
  TTree = class(TObject)
  private
    fchild0 : TTree;      // потомки "0" и "1"
    fchild1 : TTree;
    fleaf : Boolean;      // признак листового дерева
    fcharacter : Integer; // входной символ
    fweight : Integer;    // вес этого символа
  public
    procedure Tree(character, weight : integer; leaf : boolean);
    procedure traverse(code : string; h : THuffman);
    property child0 : TTree read fchild0 write fchild0;
    property child1 : TTree read fchild1 write fchild1;
    property leaf : Boolean read fleaf write fleaf;
    property character : Integer read fcharacter write fcharacter;
    property weight : Integer read fweight write fweight;
  end;
 
  THuffman = class(TObject)
  private
    // поля :)
    fweights : array [0..ALPHABETSIZE-1] of Integer;// веса символов
    fcode : array [0..ALPHABETSIZE-1] of String;// коды Хаффмана
    ftree : array [0..ALPHABETSIZE-1] of TTree;// рабочий массив деревьев
    // методы доступа к массиву :)
    function GetCodeValue(Index: Integer): String;
    function GetTreeValue(Index: Integer): TTree;
    function GetWeightValue(Index: Integer): Integer;
    procedure SetCodeValue(Index: Integer; const Value: String);
    procedure SetTreeValue(Index: Integer; const Value: TTree);
    procedure SetWeightValue(Index: Integer; const Value: Integer);
  public
    // методы :)
    procedure makeCode;
    procedure growTree(var data : array of Integer);
    function getLowestTree(used : integer) : integer;
    function coder(var data : array of integer) : string;
    function decoder(data : string) : string;
    // свойства :)
    property weights[Index: Integer] : Integer read GetWeightValue write SetWeightValue;
    property code[Index: Integer] : String read GetCodeValue write SetCodeValue;
    property tree[Index: Integer] : TTree read GetTreeValue write SetTreeValue;
  end;
 
var
  Huffman : THuffman;
 
implementation
 
{ TTree }
 
procedure TTree.Tree(character, weight: integer; leaf: boolean);
begin
  fleaf := leaf;
  fcharacter := character;
  fweight := weight;
end;
 
(*  Обход дерева с генерацией кодов
    1. "Распечатать" листовое дерево и записать код Хаффмана в массив
    2. Рекурсивно обойти левое поддерево (с генерированием кода).
    3. Рекурсивно обойти правое поддерево. *)
procedure TTree.traverse(code: String; h: THuffman);
begin
  if leaf then
  begin
    h.code[Ord(character)] := code;
    ShowMessage('Символ: ' + Chr(character) +'  '+'Вес: '+IntToStr(weight) +'  '+'Двоичный код: '+ code);
  end;
  if child0 <> nil then child0.traverse(code + '0', h);
  if child1 <> nil then child1.traverse(code + '1', h);
end;
 
{ THuffman }
 
(* ищем самое "легкое" дерево *)
function THuffman.getLowestTree(used: integer): integer;
var
  min, i : Integer;
begin
  min := 0;
  for i:=1 to used-1 do if tree[i].weight < tree[min].weight then min := i;
  Result := min;
end;
 
(* кодирует данные строкой из 1 и 0 *)
function THuffman.coder(var data: array of Integer): String;
var
  str : String;
  i : Integer;
begin
  str := '';
  for i:=0 to High(data) do str := str + code[data[i]];
  Result := str;
end;
 
function THuffman.decoder(data : string): string;
var
  str : String;
  c : Integer;
begin
  str := '';
  while(length(data) > 0) do
  begin
    for c:=0 to ALPHABETSIZE-1 do
    if (weights[c] > 0) AND (code[c] = copy(data, 1, length(code[c]))) then
    begin
      data := copy(data, length(code[c])+1, length(data));
      str := str + chr(c) + ' - ' + code[c] + #13;
    end;
  end;
  Result := str;
end;
 
(* растим дерево *)
procedure THuffman.growTree(var data: array of Integer);
var
  i, c, w, min, used, weight0 : Integer;
  temp : TTree;
begin
  for i:=0 to ALPHABETSIZE-1 do weights[i] := 0;
  for i:=0 to High(data) do weights[data[i]] := weights[data[i]] + 1; // считаем веса символов
  //  заполняем массив из "листовых" деревьев
  //  с использованными символами
  used := 0;
  for c:=0 to ALPHABETSIZE-1 do
  begin
    w := weights[c];
    if w <> 0 then
    begin
      inc(used);
      tree[used-1] := TTree.Create;
      tree[used-1].Tree(c, w, true);
    end;
  end;
  while used > 1 do                             // парами сливаем легкие ветки
  begin
    min := getLowestTree(used);                 // ищем 1 ветку
    weight0 := tree[min].weight;
    temp := TTree.Create;                       // создаем новое дерево
    temp.child0 := tree[min];                   // и прививаем 1 ветку
    dec(used);
    tree[min] := tree[used];                    // на место 1 ветки кладем
                                                // последнее дерево в списке
    min := getLowestTree(used);                 // ищем 2 ветку и
    temp.child1 := tree[min];                   // прививаем ее к нов.дер.
    temp.weight := weight0 + tree[min].weight;  // считаем вес нов.дер.
    tree[min] := temp;                          // нов.дер. кладем на место 2 ветки
  end;                                          // все! осталось 1 дерево Хаффмана
end;
 
(* запускаем вычисление кодов Хаффмана *)
procedure THuffman.makeCode;
begin
  tree[0].traverse('', self);
end;
 
function THuffman.GetCodeValue(Index: Integer): String;
begin
  Result := fcode[Index];
end;
 
function THuffman.GetTreeValue(Index: Integer): TTree;
begin
  Result := ftree[Index];
end;
 
function THuffman.GetWeightValue(Index: Integer): Integer;
begin
  Result := fweights[Index];
end;
 
procedure THuffman.SetCodeValue(Index: Integer; const Value: String);
begin
  fcode[Index] := Value;
end;
 
procedure THuffman.SetTreeValue(Index: Integer; const Value: TTree);
begin
  ftree[Index] := Value;
end;
 
procedure THuffman.SetWeightValue(Index: Integer; const Value: Integer);
begin
  fweights[Index] := Value;
end;
 
end.

Код


const ALPHABETSIZE = 256;

class TTree;
class THuffman;

class TTree {

 private:
    TTree* fchild0;      // ïîòîìêè "0" è "1"
    TTree* fchild1;
    bool fleaf;      // ïðèçíàê ëèñòîâîãî äåðåâà
    int fcharacter; // âõîäíîé ñèìâîë
    int fweight;    // âåñ ýòîãî ñèìâîëà
  public:
    void __fastcall Tree(int character, int weight, bool leaf);
    void __fastcall traverse(char code[400], THuffman h);
    TTree property child0 (read fchild0 write fchild0);
    property child1 : TTree read fchild1 write fchild1;
    property leaf : Boolean read fleaf write fleaf;
    property character : Integer read fcharacter write fcharacter;
    property weight : Integer read fweight write fweight;
  //end;
};

class THuffman {
  private:
    // ïîëÿ :)
    int fweights[ALPHABETSIZE-1];// âåñà ñèìâîëîâ
    char fcode[ALPHABETSIZE-1];// êîäû Õàôôìàíà
    TTree ftree[ALPHABETSIZE-1];// ðàáî÷èé ìàññèâ äåðåâüåâ
    // ìåòîäû äîñòóïà ê ìàññèâó :)
    char GetCodeValue(int Index);
    TTree GetTreeValue(int Index);
    int GetWeightValue(int Index);
    void __fastcall SetCodeValue(int Index, const char Value[200]);
    void __fastcall SetTreeValue(int Index, const TTree Value);
    void __fastcall SetWeightValue(int Index, const int Value);
  public:
    // ìåòîäû :)
    void __fastcall makeCode;
    void __fastcall growTree(int data[]);
    int getLowestTree(int used);
    char coder(int data[]);
    char decoder(char data[400]);
    // ñâîéñòâà :)
    //property weights[Index: Integer] : Integer read GetWeightValue write SetWeightValue;
    //property code[Index: Integer] : String read GetCodeValue write SetCodeValue;
    //property tree[Index: Integer] : TTree read GetTreeValue write SetTreeValue;
 // end;
};


void __fastcall TTree::Tree(int character, int weight, bool leaf){
  fleaf = leaf;
  fcharacter = character;
  fweight = weight;
}

/*  Îáõîä äåðåâà ñ ãåíåðàöèåé êîäîâ
    1. "Ðàñïå÷àòàòü" ëèñòîâîå äåðåâî è çàïèñàòü êîä Õàôôìàíà â ìàññèâ
    2. Ðåêóðñèâíî îáîéòè ëåâîå ïîääåðåâî (ñ ãåíåðèðîâàíèåì êîäà).
    3. Ðåêóðñèâíî îáîéòè ïðàâîå ïîääåðåâî. */

void __fastcall TTree::traverse(char code[400], THuffman h)
{
  if (h::leaf) {

    h.code[Ord(character)] = code;
    ShowMessage('Ñèìâîë: ' + Chr(character) +'  '+'Âåñ: '+IntToStr(weight) +'  '+'Äâîè÷íûé êîä: '+ code);
  }
  if child0 <> nil then child0.traverse(code + '0', h);
  if child1 <> nil then child1.traverse(code + '1', h);
end;

Цитата(SergXP @ 8.3.2009, 19:35

)

И кто муже придется мне терь VC++ 6.0 ставить :(

Цитата(SergXP @ 10.3.2009, 10:54

)

В общем запустисть удалось! Спасибо за помощь!

Цитата(SergXP @ 10.3.2009, 10:54

)

можно ли как-нибудь выдернуть нужные ф-ции и воткнуть их в C++ Builder?

Код


#include <iostream>
#include <fstream>
#include <vector>
#include <string>

struct s_node
{
    unsigned c;
    unsigned char ch;
    unsigned n;
    std::vector<s_node*> br;
};

class my_ifstream: public std::ifstream
{
public:
    virtual my_ifstream& operator>>(unsigned char&);
    my_ifstream(const char *_Filename, std::ios_base::openmode _Mode = ios_base::in, int _Prot = (int)ios_base::_Openprot);
};

my_ifstream::my_ifstream(const char *_Filename, std::ios_base::openmode _Mode, int _Prot):std::ifstream(_Filename, _Mode, _Prot)
{
}

my_ifstream& my_ifstream::operator>>(unsigned char& ch)
{
    ch = get();

    return *this;
}

void tree_walk(s_node *);
void tree_del(s_node *);
void write_message();

std::ofstream fout("output.txt");
std::string table[256];

int main()
{
    my_ifstream fin("input.txt", std::ios_base::in | std::ios_base::binary);
    
    if (!fin.is_open())
    {
        std::cout << "Input file not found" << std::endl;
        
        system("pause");

        return 0;
    }

    std::vector<unsigned char> ch_set;
    std::vector<s_node> nodes;
    unsigned char ch;
    unsigned j = 0;

    while (fin >> ch)
    {
        unsigned i;

        for (i = 0; i < ch_set.size() && ch_set[i] != ch; i++);

        if (i == ch_set.size())
        {
            s_node t;

            ch_set.push_back(ch);

            t.ch = ch;
            t.n = 0;
            t.c = 0;
        
            nodes.push_back(t);

            my_ifstream fin2("input.txt", std::ios_base::in | std::ios_base::binary);

            while (fin2 >> ch)
                if (ch == nodes[j].ch)
                    nodes[j].n++;

            j++;
        }
    }

    for (unsigned i = 0; i < nodes.size() - 1; i++)
        fout << "'" << nodes[i].ch << "'" << nodes[i].n << ", ";
    
    fout << "'" << nodes[nodes.size() - 1].ch << "'" << nodes[nodes.size() - 1].n << std::endl << std::endl;

    std::vector<s_node*> t;

    for (unsigned i = 0; i < nodes.size(); i++)
    {
        t.push_back(new s_node);
        *t[i] = nodes[i];
    }

    while (t.size() > 1)
    {
        s_node *x;

        for (unsigned i = 0; i < t.size(); i++)
            for (unsigned j = 0; j < t.size(); j++)
                if (t[i]->n < t[j]->n)
                    x = t[i], t[i] = t[j], t[j] = x;

        s_node *min1 = t[0];
        unsigned c1 = 0;

        t.erase(t.begin() + c1);
        
        s_node *min2 = t[0];
        unsigned c2 = 0;

        s_node *tmp = new s_node;

        tmp->br.push_back(min1);
        tmp->br.push_back(min2);

        tmp->c = 2;
        tmp->n = min1->n + min2->n;
        t[c2] = tmp;
    }

    tree_walk(t[0]);
    write_message();
    tree_del(t[0]);

    return 0;
}

void tree_walk(s_node *root)
{
    static std::string s = "";

    if (root->c)
    {
        s += "1";
        
        tree_walk(root->br[1]);
        s.erase(s.size() - 1, 1);
        
        s +="0";

        tree_walk(root->br[0]);
        s.erase(s.size() - 1, 1);
    }
    else
    {
        fout << "'" << root->ch << "'" << " = " << s << std::endl;
        table[root->ch] = s;
    }
}

void tree_del(s_node *root)
{
    if (root->c)
    {
        tree_del(root->br[1]);
        tree_del(root->br[0]);
    }
    else
        delete root;
}

void write_message()
{
    my_ifstream fin("input.txt");
    unsigned char ch;

    fout << std::endl;

    while(fin >> ch)
        fout << table[ch];
}

Цитата(SergXP @ 10.3.2009, 12:12

)

чтобы данные выводились в Memo.