Помощь - Поиск - Пользователи - Календарь
Полная версия: Вопрос задам проще
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
Янычар
Я смотрю что всем лень читать то что у меня понаписано по хаффмана в предыдущей теме так что напишу кратче и яснее, постараюсь по крайней мере) Кароче говоря кто знает как из частотной таблицы и соответствующей ей таблице симвлов кодируемого файла построить дерево Хаффмана? Мне было бы неплохо привести пример с кодом
Unknown
в свое время писал пргу с кодами Хаффмана и Шеннона-Фано.
целиком выкладывать проблематично, код - ниже. Надеюсь, разберешься )
только там дерево не строится, а лишь кодируется каждый символ.

//---------------------------------------------------------------------------

#include <vcl.h>
#include <stdio.h>
#include <math.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;

char abc[100] = "";
int j=0, l=1;
AnsiString B[100][100];

int Check(char c){
for (int i=0; i<j; i++)
if (c == abc[i]) return i+1;
return 0;
}

void Sort(float * A, int j){
AnsiString tmp;
int l = 1;
do {
int r = 0;
if(A[l] < A[l+1]){
A[l] = A[l+1] + A[l];
A[l+1] = A[l] - A[l+1];
A[l] = A[l] - A[l+1];
do {
tmp = B[l+1][r];
B[l+1][r] = B[l][r];
B[l][r] = tmp;
r++;
} while ((B[l][r] != "0") | (B[l+1][r] != "0"));
}
l++;
} while (l < j);
}

//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
Memo1->Text = "";
StringGrid1->Cells[0][0] = "Symbol";
StringGrid1->Cells[1][0] = "Probability";
StringGrid1->Cells[2][0] = "Code Shennon-Fano";
StringGrid1->Cells[3][0] = "Code Haffman";
StringGrid1->RowCount = 2;
for (int i = 1; i < StringGrid1->ColCount; i++) {
StringGrid1->Cells[0][i] = "";
StringGrid1->Cells[1][i] = "";
StringGrid1->Cells[2][i] = "";
StringGrid1->Cells[3][i] = "";
}
}

//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Memo1->Text = "";
StringGrid1->RowCount = 2;
for (int i = 1; i < StringGrid1->RowCount; i++) {
StringGrid1->Cells[0][i] = "";
StringGrid1->Cells[1][i] = "";
StringGrid1->Cells[2][i] = "";
StringGrid1->Cells[3][i] = "";
}
char A[10000];
int i;
if (OpenDialog1->Execute()){
Form1->Memo1->Lines->LoadFromFile(Form1->OpenDialog1->FileName);
strcpy(A,Form1->Memo1->Text.c_str());
int Length = strlen(A);
if (strlen(A)==1) ShowMessage ("Введите хотя бы два символа");
else
for (i=0;i<strlen(A);i++)
switch(A[i]){
case ' ': A[i]='_'; break;
case 13: A[i]='_'; break; // /r
case 10: for(j=i; j<strlen(A)-1; j++) A[j]=A[j+1]; break; // /n
}
char c;
j = 0;
for (int i=0;i<Length;i++){
c = A[i];
if (Check© == 0){
StringGrid1->RowCount += 1;
abc[j] = c; j++;
StringGrid1->Cells[1][j] = 1.0/Length;
StringGrid1->Cells[0][j] = c;
}
else
StringGrid1->Cells[1][Check©] =
FloatToStr(StrToFloat(StringGrid1->Cells[1][Check©])+1.0/Length);
}
}
float H = 0;
for (i = 1; i <= j; i++)
H -= StrToFloat(StringGrid1->Cells[1][i])*log(StrToFloat(StringGrid1->Cells[1][i]))/log(2.0);
Label2->Caption = H;

AnsiString tmp;
bool mark;
for(int i = 1; i <= j; i++) { //сортировка
mark = true;
for(int l = 1; l < j; l++)
if(StringGrid1->Cells[1][l] < StringGrid1->Cells[1][l+1]){
tmp = StringGrid1->Cells[1][l+1];
StringGrid1->Cells[1][l+1] = StringGrid1->Cells[1][l];
StringGrid1->Cells[1][l] = tmp;
tmp = StringGrid1->Cells[0][l+1];
StringGrid1->Cells[0][l+1] = StringGrid1->Cells[0][l];
StringGrid1->Cells[0][l] = tmp;
mark = false;
}
if (mark) break;
}

float a1, a2, v;
do {
H = 0;
for (i = 1; i <= j; i++) {
tmp = StringGrid1->Cells[2][i];
v = StrToFloat(StringGrid1->Cells[1][i]);
mark = false;
for (l = 1; l <= j; l++)
if ((StringGrid1->Cells[2][i] == StringGrid1->Cells[2][l])&(l!=i)) {
H = 1; v += StrToFloat(StringGrid1->Cells[1][l]); mark = true;
}
if (mark) {
a1 = 0, a2 = 0;
for (int y = 1; y <= j; y++)
if (StringGrid1->Cells[2][y] == tmp)
if (a2 < 0.5*v) {
a2 += StrToFloat(StringGrid1->Cells[1][y]);
StringGrid1->Cells[2][y] = StringGrid1->Cells[2][y] + "1";
}
else {
a1 += StrToFloat(StringGrid1->Cells[1][y]);
StringGrid1->Cells[2][y] = StringGrid1->Cells[2][y] + "0";
}
}
}
} while (H != 0);

float P[100] = {0};
for (i = 1; i <= j; i++) {
P[i] = StrToFloat(StringGrid1->Cells[1][i]);
B[i][0] = B[i][0] + i;
for (int r = 1; r <=j; r++)
B[i][r] = "0";
}

do {
P[j-1] = P[j-1] + P[j];
l = 0;
do {
StringGrid1->Cells[3][StrToInt(B[j][l])] = "0" + StringGrid1->Cells[3][StrToInt(B[j][l])];
l++;
} while(B[j][l] != "0");
l = 0;
do {
StringGrid1->Cells[3][StrToInt(B[j-1][l])] = "1" + StringGrid1->Cells[3][StrToInt(B[j-1][l])];
l++;
} while(B[j-1][l] != "0");
int a = 0;
do {
B[j-1][l] = B[j][a];
l++;
a++;
} while (B[j][a] != "0");
j--;
Sort(P, j);
} while (j > 1);

a1 = 0;
a2 = 0;
for (int i = 1; i < StringGrid1->RowCount; i++) {
a1 += strlen(StringGrid1->Cells[2][i].c_str());
a2 += strlen(StringGrid1->Cells[3][i].c_str());
}
StringGrid1->Cells[2][StringGrid1->RowCount-1] = a1/(StringGrid1->RowCount-2);
StringGrid1->Cells[3][StringGrid1->RowCount-1] = a2/(StringGrid1->RowCount-2);
}
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.