CSC-SY

لدينا ملف مكون من عدد من المحارف.
تتوزع المحارف في الملف بشكل اعتباطي.
سنفترض للتسهيل عدد المحارف أربعة
وأن المحارف هي
A B C D

مثال

AACABBACDDACADAACDAADAB

(طبعاً هذه ليست سلسلة الخيارات لفحص مؤتمت...)

حجم الملف من هذا النوع هو
حجم الملف = عدد المحارف في الملف × حجم المحرف.

عدد المحارف في الملف يفرضه المستخدم صاحب الملف

حجم المحرف: يتعلق بعدد المحارف المتوفرة في الأبجدية المستخدمة.

في المثال السابق هناك أربعة محارف مستقلة فقط، ومنه يمكن تمييز المحرف بـ 2 بت أي أن حجم المحرف هو 2 بت.
فمثلاً نرمز كالتالي
A=00
B=00
C=00
D=00

لنفترض ملفاً يتكون من مليون محرف موزعة بالشكل التالي
500 ألف محرف A
350 ألف محرف B
130 ألف محرف C
20 ألف محرف D

حجم الملف = 1 مليون × 2 بت = 2 مليون بت

نريد ضغط الملف أي استبداله بملف جديد ذو حجم أضغر من الحجم السابق.

طريقة هوفمان
------
إن الترميز السابق يسمى الترميز ذو الطول الثابت
Fixed-Length Encoding
أي أن جميع المحارف تأخذ تراميز متساوية الطول (2 بت في المثال السابق)
وهو أبسط أنواع التراميز.

لاحظ هوفمان أنه في كثير من الملفات المفيدة لا تكون الأحرف متكررة بنفس العدد
(فمثلاً في المثال السابق حرف A هو الأكثر تكراراً).
ووجد أنه من غير العادل أن نعطي أحرف ذات تواترات مختلفة تراميز متساوية بالطول
بل يجب إعطاء الأحرف الأكثر وروداً تراميز قصيرة والأثل وروداً تراميز طويلة.

في المثال السابق لنعطي الأحرف التراميز التالية
ِA = 0
B = 10
C = 110
D = 111

فمثلاً إذا كان لدينا الملف

A A B  C   A C   D   A  نرمزه بـ
0 0 10 110 0 110 111 0

الشرط على أي ترميز ألا يكون رمز هو بادئة لرمز آخر
لأنه لو كان ذلك لما أمكن عند فك الترميز معرفة أي من
المحرفين نختار (البادئة أم المبدوء...)

إن الطول المطلوب لتخزين الأحرف:

ِA 1
B 2
C 3
D 3

وبذلك يصبح حجم الملف الكلي:

1 × 500 ألف +
2 × 350 ألف +
3 × 130 ألف +
3 × 20 ألف =
1650000 بت
وهو أضغر من حجم الملف الأصلي

تبقى عدة نقاط للمناقشة:
----------
1- التوفير السابق يبدو قليل، ولكن في الحالات العملية (ملف نصي على أبجدية ASCII) يكون هذا الترميز أكثر من فعال حيث يقل حجم الملف عادة إلى أقل من النصف.
2- إبجاد التراميز: القاعدة البديهية هي إعطاء الأحرف الأكثر وروداً تراميز قصيرة والأثل وروداً تراميز طويلة
لكن هناك بعض النظريات هنا لم أود ذكرها. المهم يجب بناء خوارزمية توجد ذه التراميز
3- حتى يتم فك الضغط نحتاج إلى
الملف المضغوط
تكرارات محارف الأبجدية المستخدمة
من تكرارات محارف الأبجدية المستخدمة يمكن إيجاد ترميز كل محرف
ومن جدول تراميز المحارف يمكن التعرف على الملف

هذه المرة سأتوقف هنا وأطلب من الأعضاء النشيطين متابعة الموضوع
(توفير الخوارزمية، شرح كيفية الضغط...)

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

بكرا رح حاول اشرح يلي بعرفه عن تقنية هوفمان يلي يمكن كل طلاب السنة التالتة بجامعة دمشق عندهم فكرة عنها لإنها كانت انطلبت منا كوظيفة السنة الماضية
على كل حال يلي بيحب يشوف الكود كمان فيني ابعتله ياه و هو مكتوب بالـ 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 ل ويندوز أو للينكس يقلي ....

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

[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 f[c]. 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
واضح كتير

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

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.