PDA

View Full Version : الگوریتم هافمن



Mahdi_20
شنبه 05 دی 1383, 22:57 عصر
با سلام.
من میخوام از این الگوریتم برای فشرده سازی استفاده کنم.
برای تشکیل درخت هافمن روش ساده چیه؟ و برای ذخیره درخت در اول فایل فشرده شده چه راهی رو پیشنهاد میکنید؟
در ضمن کدی که بصورت بیتی از درخت بدست میاد را در رجیستر ذخیره کرد و در اون بیتها حرکت کرد.
با تشکر.

Sepidar
یک شنبه 06 دی 1383, 02:02 صبح
قبلا در این باره بحث شده.

Mahdi_20
چهارشنبه 09 دی 1383, 00:01 صبح
درسته ولی سوال من چیز دیگه ایه.
سوال من روش درست کردن درخته . من تو این موندم که چه جوری با تعدادی برگ یک درخت درست کنم.
چون این مسله فرق داره.
ممنون میشم اگه منو راهنمایی کنید.

Sepidar
چهارشنبه 09 دی 1383, 00:45 صبح
به یاد ایام قدیم، امشب می شینم و دوباره این تیکه الگوریتم هافمن رو پیاده می کنم. منتظر باش.

Sepidar
چهارشنبه 09 دی 1383, 03:18 صبح
مواظب باش: تست نشده. اما فکر کنم به خوبی منطق کار رو نشونت بده.

type
TCharData=record
Quentity:largeint;
Used:boolean;
end;

CharsData=array[char] of TCharData;

PTreeNode=^TTreeNode;
TTreeNode=record
Big,Small:PTreeNode;
Idx:integer;
SigmaQ:largeint;
end;

.
.
.

function MakeTree(ABig,ASmall:PTreeNode):PTreeNode;
(******************************)
function NewNode(ABig,ASmall:PTreeNode;AIdx:integer;Q:large int):PTreeNode;
var
P:PTreeNode;
begin
new(P);
with P^ do begin
Big:=ABig;
Small:=ASmall;
AIdx:=Idx;
SigmaQ:=Q;
end;
NewNode:=P;
end;
(******************************)
function FindLessQ:integer;
var
i:integer;
ch:char;
begin
i:=-1;
for ch:=#0 to #255 do
if not CharsData[ch].Used then
if i=-1 then i:=integer(ch) else
if CharsData[ch].Quentity<CharsData[char(i)].Quentity then i:=integer(ch);

if i<>-1 then CharsData[char(i)].Used:=true;
FindLessQ:=i;
end;
(******************************)
procedure Swap(var a,b:PTreeNode);
var
c:PTreeNode;
begin
c:=a;
a:=b;
b:=c;
end;
(******************************)
var
i:integer;
P1,P2,P3:PTreeNode;
begin
if ABig=nil then begin
i:=FindLessQ;
P2:=NewNode(nil,nil,i,CharsData[char(i)].Quentity) ;

i:=FindLessQ;
P1:=NewNode(nil,nil,i,CharsData[char(i)].Quentity) ;

MakeTree:=MakeTree(P1,P2);
end else begin
P1:=ABig;
P2:=ASmall;
i:=FindLessQ;
if i=-1 then MakeTree:=NewNode(P1,P2,-1,P1^.Quentity+P2^.Quentity)
else begin
P3:=NewNode(nil,nil,i,CharsData[char(i)].Quentity) ;

if P3^.Quentity>P2^.Quentity then Swap(P2,P3);
if P2^.Quentity>P1^.Quentity then Swap(P2,P1);

MakeTree:=MakeTree(NewNode(P1,P2,-1,P1^.Quentity+P2^.Quentity),P3);
end;
end;
end;

.
.
.
.

//main prog

var
TreeRoot:PTreeNode;
.
.
begin
{initialization CharsData[aaa] with
Used:=Tree and Quentity:=frequence of using aaa character in file}
.
.
.
TreeRoot:=MakeTree(nil,nil);
.
.
.
end.

esi_dar
چهارشنبه 16 اسفند 1385, 11:42 صبح
سلام
دست شما در د نکنه .اگه امکان داره یه مقدار پیاز داغشو بیشتر کن تا استادم اشکش درد بیاد

esi_dar
چهارشنبه 16 اسفند 1385, 11:45 صبح
از کتاب ساختمان داده جعفر نژاد استفاده کن اگه از اون چیزی فهمیدی منو راهنمایی کن