CSC-SY

شكراً بلال
شو شباب ما في حدا نشيط يكمل

شو رأيك؟؟؟

بكرا رح حاول اشرح يلي بعرفه عن تقنية هوفمان يلي يمكن كل طلاب السنة التالتة بجامعة دمشق عندهم فكرة عنها لإنها كانت انطلبت منا كوظيفة السنة الماضية
على كل حال يلي بيحب يشوف الكود كمان فيني ابعتله ياه و هو مكتوب بالـ pascal لإنو السنة الماضية ما كنت بعرف غيرها

أنا ما كتير بعرف عن Huffman ..
و هي مزبوط انطلبت كوظيفة خوارزميات2 السنة الماضية ..
الفكرة فيها ضغض البيانات ..
بيستخدمو فيها بنية شجرة ثنائية و بيكون النص مخزن بالأوراق تبعوت هالشجرة ..
و بيكون عنوان ورقة ما X هو الطريق للورقة X ..
ذهاب يساري =1
ذهاب يميني=0
أو العكس ..

بتصور أنو الطلاب يلي اشتغلو فيها بيفيدونا أكتر بهالمسألة ..
(طلاب الثالثة - دمشق)

تدعى هذه الشجرة بشجرة هوفمان الثنائية Huffman Binary Tree، بعد بناء شجرة هوفمان يتم الترميز اعتماداً عليها فلترميز أي محرف نسند إلى الرمز الموافق السلسلة الخالية ونبدأ عند جذر شجرة هوفمان فإذا صعدنا نحو فرع يميني فإننا نضيف 1 إلى الرمز الموافق و إذا صعدنا إلى فرع يساري فإننا نضيف 0 إلى الرمز الموافق حتى نصل إلى الورقة المطابقة للحرف.
خوارزمية هوفمان Huffman Algorithm:
كيف يتم بناء شجرة هوفمان:
المعطيات: الأبجدية Σ والنص P
المخرجات: اللائحة L ثم الشجرة T

٨ αi є Σ ; f(i) = frequency(αi);
من أجل كل α تنتمي إلى الأبجدية Σ احسب تردد αi في P وهو f(i).
احشر (αi ، f(i)) في اللائحة L في موقعها المناسب مرتبة تصاعدياً بحسب قيمة f(i)

عندما ننتهي من بناء السلسلة نطبق ما يلي:

طالما i<length(P) كرر:
1-
o:=(αi + αi+1، f(i) + f(i+1))
o.left := (αi ، f(i))
o.right := ( αi+1 ، f(i+1))
2- احشر o في السلسلة
ولنوضح ذلك بشكل عملي :

نشكل لائحة مترابطة مبنية على المؤشرات وندع المؤشر يشير إلى بدايتها نضيف العناصر بشكل مرتب إلى هذه السلسلة كما يلي:
نحسب تردد كل محرف ونحشره بموقعه المناسب بواسطة التابع BuildList أي إذا كان لدينا المحارف الآتية مع تكرارها:
ونقوم بعملية الإضافة كما يلي:
نفحص أول عنصر في القائمة فإذا كان تردده أكبر من تردد المحرف الجديد إننا نجعل المحرف الجديد بداية السلسلة ونجعل المؤشر يشير إلى هذا المحرف أما إذا كان تردد الحرف الأول في السلسلة أصغر من تردد الحرف الجديد فإننا ننتقل إلى المحرف الثاني وهكذا إلى نصل إلى الموقع المناسب عندئذ نجعل مؤشر الحرف السابق لهذا الموقع في السلسلة يشير إلى الحرف الجديد ونجعل مؤشر هذا الأخير يشير إلى الموقع الذي كان يشير إليه المحرف السابق.
و يمثل الشكل التالي عملية بناء القائمة List وفقاً للإجراء Build():

عندما ننتهي من بناء القائمة سيكون علينا بناء الشجرة كما يلي:
نأخذ أول عنصرين من القائمة ونجعلهما ابنان يساري (للعنصر الأول) ويميني (للعنصر الثاني) لعنصر جديد محرفه هو مجموع المحرفين وتردده مجموع ترددي المحرفين ونحذف هذان العنصران من القائمة ثم نضيف العنصر الجديد وبموقعه المناسب بحسب تردده إلى القائمة ونكرر ذلك حتى يبقى هناك عنصر واحد في القائمة يصبح هو جذر شجرة هوفمان وتكون هذه الشجرة مرتبة على شكل كومة ثنائية إن محرف الجذر هو الأبجدية بكاملها وتردده هو طول النص.
تمثل الأوراق في الشجرة السابقة الأحرف الأصلية في النص والتي نريد الحصول على ترميزها.

و فيما يلي نبين كيفية تحويل القائمة إلى شجرة Huffman وفق الإجراء merge():

يتم الحصول على الترميز عن طريق التجول في الشجرة ابتداء من الجذر وانتهاء بالورقة، فكلما اتجهنا يمينا نضيف إلى الرمز 1 وكلما اتجهنا يساراً نضيف 0 وهكذا إلى أن نصل إلى ورقة، وبهذا الشكل نحصل على ترميز كل حرف حيث نلاحظ أنه تم ترميز الأحرف ذات التكرار الكبير بعدد صغير من الرموز والأحرف ذات التكرار الصغير بعدد كبير من الرموز، مما يؤدي إلى تصغير حجم النص المطلوب، وكتابته على القرص، ونجد أيضاً أنه لا يوجد ترميز لمحرف يشكل بادئة لترميز محرف آخر
لو كان فيني حط صور لوضت الشغلة أكتر....

ما بعرف ليش طلع التنسيق هيك .....
بس لوضوح أكتر انسخوها و عملوا الalignment على اليسار
ملاحظة : إذا حدا بوا الexe أو الsource ل ويندوز أو للينكس يقلي ....

شو قلبت بروجكتك على Linux ؟ ..
عن جد مبروك ... و عقبال عنا ..

فينك تنسق الكود بالشكل التالي:

[code ] code here [ /code ]

بس بدون فراغات.

النتيجة:

code here

جربت طلعت النتيجة أسوأ...

إذا فيك تظبطها انت بكون ممنون....

ما ظبطت، لانو عربي و انكليزي مع بعض.

كتب "ammar_halaby":

Let's assume that C is a set of n characters and that each character c in C is an object with a defined frequency fi]c[/i. The builds the tree T corresponding to the optimal code in a bottom-up manner. It begins with a set of |C| leaves and performs a sequence of |C| - 1 "merging" operations to create the final tree. A min-priority queue Q, keyed on f, is used to identify the two least-frequent objects to merge together. The result of the merger og two objects is a mew object whose frequency is the sum of the frequencies of the two objects that were merged.
The algorithm which builds the tree will be something like this (in pseudo code):


Huffman(C)
1.....n = |C|
2.....Q = C
3.....for i = 1 to (n - 1) do
4..........allocate a new node z
5..........z.left = x = Q.Extract-Min
6..........z.right = y = Q.Extract-Min
7..........f[z] = f[x] + f[y]
8..........Insert(Q, z)
9.....return Q.Extract-Min ; return the root of the tree


The algorithm above is similar what Kinan posted before, but I used a tree structure instead of the linked list structure; thus reducing the complexity from n^2 to n.log(n)

but u consumed n^2 to build ur queue ...
I think it's the same ..or what....
if I didn't understand this ...plz tell me how did u build the first tree...

yeaaa that's good ...
and I think it's good to put this algorithm too.....

but I think u need O(n) to build the first heap

رح وضح كيف بنيت السلسلة المترابطة ......
استخدمت المؤشرات و أدخلت كل حرف جديد بمكانه ....على طريقة السلاسل الخطية يللي أخدناها السنة الماضية ...
بعتقد أنها ذات تعقيد O(n) time

(كتاب الخوارزميات 1 ص 147) ....
اما الإجراء build موجود بكتاب البرمجة 2 ص 92 و ص 93

بعدين عملت إجراء التحيل إلى شجرة ....
لمعلومات أكتر راجع كتاب intro to algorithms

مجرد مثال عن تقنية ضغط هوفمان :

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/huffman.html

في بآخرة الصفحة مثال تطبيقي عن التقنية من أولتا لآخرتا ..........
بس اضغط :
Run the Animation

Great applet!

لا تحتاج إلى شيء بعد بناء السلسلة الأولى O(n)0000
سوى أن تدمج كل أول عنصرين لتخلق العنصر الجديد ....ثم تضيفه إلى القائمة مرة أخرى وفي موقعه المناسب
o(n)+o(n)00
أي العمليتلن منفصلتان ....الثانية نحتاج إليها تماماً لأن العناصر جديدة ....
التعقيد هو كما أعتقد o(n)0
المثال بكتاب intro into algorithms
واضح كتير

الصفار منشان يزبط التنسيق

طيب، بهالحالة انت بتدمج عنصرين (n - 1) مرة ، مو لحتى تدمج أصغر عنصرين لازم تدور عليهن؟؟ يعني لازم تعمل 2(n - 1) عملية بحث.
كل عملية تدوير (بحث) بتاخد (n) لأنو البحث خطي (لا يمكن إلا البحث خطيا ففي هذه الحالة).
الكلفة الكلية: (n - 1) * (n) ~ (n ^ 2) ....... اتفقنا ولا لسا؟؟

لأ ما لازم تدور عليهم ....
عطول بتدمج أول عنصرين
ما السلسلة مرتبة ....

ammar_halaby محق

أنا استعملت linked list وما عملت temporary array

type st=string;
type Hufft=^nod;
     nod=record
        left,right,next:Hufft;
        symbol:String;
        Frq:integer;
        isLeaf:boolean;
     end;
procedure BuildList(var tree:Hufft;f1:integer;s:st;b:boolean;l,r:hufft);
var p,n1,pr:Hufft;
begin
  if tree=nil then
  begin
  new(tree);
tree^.next:=nil;
tree^.isLeaf:=b;
    if b then begin

  tree^.left:=nil;
  tree^.right:=nil;
  end
  else
  begin
  tree^.left:=l;
  tree^.right:=r;
  end ;

tree^.symbol:=s;

tree^.Frq:=f1;
  end
else
if (f1<tree^.Frq) or  ((tree^.Frq =f1) and (tree^.symbol>s)) then
begin
new(n1);
n1^.next:=tree;


n1^.Frq:=f1;
n1^.symbol:=s;
n1^.isLeaf:=b;
  if b then
  begin
n1^.left:=nil;
n1^.right:=nil;
  end
  else
begin
n1^.right:=r;
n1^.left:=l;
end;
tree:=n1;
end
else
begin
p:=tree;pr:=p;
while(p<>nil) and ( (p^.Frq <=f1) or ((p^.Frq =f1) and (p^.symbol<s))   ) do
begin

pr:=p;
p:=p^.next;
end;

begin
new(n1);
n1^.next:=p;
n1^.isLeaf:=b;
n1^.Frq:=f1;
n1^.symbol:=s;
  if b then
  begin
n1^.right:=nil;
n1^.left:=nil;
  end
else
begin
n1^.right:=r;
n1^.left:=l;
end;
pr^.next:=n1;
end;

end;



end;
procedure merge(var list:Hufft;var z:Hufft);
var q:Hufft;

begin
        new(q);

if list^.next^.next<>nil then
     begin
      z:=list^.next^.next ;
       list^.next^.next:=nil; //i
        q^.left:=list;
      q^.right:=list^.next;
         list^.next:=nil;          //i
      q^.isLeaf:=false;
      q^.Frq:=q^.left^.Frq + q^.right^.Frq;
    q^.next:=nil;
       q^.symbol:=q^.right^.symbol + q^.left^.symbol;
        BuildList(z,q^.Frq,q^.symbol,q^.isLeaf,q^.left,q^.right);
       
      end
else
   begin

   q^.left:=list;
      q^.right:=list^.next;
     list^.next:=nil;//ii

         q^.isLeaf:=false;
      q^.Frq:=q^.right^.Frq + q^.left^.Frq ;
      q^.next:=nil;
       q^.symbol:=q^.right^.symbol + q^.left^.symbol;

       z:=q;
       
end;
end;

هدا جزء من الكود
ال symbol و ترتيبه كان فزلكة...

بس عم يستدعى بعد بناء السلسلة المرتبة ...و بظن الخلاف كان هنيك ....
الإستدعاء كان للعنصر الجديد يعني كأنك زدت عدد العناصر بس ...من n ل n+n/2

ما صحي ولا....

بعدين باللينك يللي فوق (مشاركة rima) في animation
متبعين فيه نفس طريقتي

أولا: مشاركة Rima ماي نفس طريقتك لأنو مستخدمين Heap structure يللي حكيت عليها سابقاً.
ثانياً: المهم أنو تعقيد BuildList = O(n) 0 في حال كانت السلسلة مرتبة ولا مفشكلة، يعني بكل الأحوال نفس الشي O(n^2) 0.
ثالثاً: كأنو مناقشتنا صارت بلا طعمة، شو رأيك نتقاتل حول إذا كانت طريقتك O(n.Log(n)) 0 ولا لأ......لأنو متل ما قلت من قبل: لا يمكن تكون طريقتك أفضل من O(n.Log(n)) 0.