كيفية ضغط البيانات باستخدام تشفير هوفمان: 10 خطوات

جدول المحتويات:

كيفية ضغط البيانات باستخدام تشفير هوفمان: 10 خطوات
كيفية ضغط البيانات باستخدام تشفير هوفمان: 10 خطوات

فيديو: كيفية ضغط البيانات باستخدام تشفير هوفمان: 10 خطوات

فيديو: كيفية ضغط البيانات باستخدام تشفير هوفمان: 10 خطوات
فيديو: هنا بيروت - رفيق نصرالله - 26-07-2023 2024, مارس
Anonim

تُستخدم خوارزمية هوفمان لضغط البيانات أو ترميزها. عادةً ، يتم تخزين كل حرف في ملف نصي على هيئة ثمانية بت (أرقام ، إما 0 أو 1) يتم تعيينها لهذا الحرف باستخدام ترميز يسمى ASCII. يكسر الملف المشفر بواسطة Huffman بنية 8 بت الصلبة بحيث يتم تخزين الأحرف الأكثر استخدامًا في عدد قليل من البتات (يمكن أن تكون "a" "10" أو "1000" بدلاً من ASCII ، وهي "01100001"). إذن ، غالبًا ما تستغرق الأحرف الأقل شيوعًا أكثر من 8 بت (قد تكون 'z' هي "00100011010") ، ولكن نظرًا لحدوثها نادرًا ، فإن تشفير Huffman ، بشكل عام ، ينشئ ملفًا أصغر بكثير من الملف الأصلي.

خطوات

جزء 1 من 2: التشفير

ضغط البيانات باستخدام ترميز هوفمان الخطوة 1
ضغط البيانات باستخدام ترميز هوفمان الخطوة 1

الخطوة الأولى. عد تكرار كل حرف في الملف ليتم تشفيره

قم بتضمين شخصية وهمية لوضع علامة على نهاية الملف - سيكون هذا مهمًا لاحقًا. في الوقت الحالي ، أطلق عليه اسم EOF (نهاية الملف) وقم بتمييزه على أنه يحتوي على تردد 1.

على سبيل المثال ، إذا كنت تريد ترميز ملف نصي بقراءة "ab ab cab" ، سيكون لديك "a" مع التردد 3 ، "b" مع التردد 3 ، "(مسافة) مع التردد 2 ،" c "مع التردد 1 ، و EOF بتردد 1

ضغط البيانات باستخدام تشفير هوفمان الخطوة 2
ضغط البيانات باستخدام تشفير هوفمان الخطوة 2

الخطوة 2. قم بتخزين الأحرف كعقد شجرية ووضعها في قائمة انتظار ذات الأولوية

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

  • الشجرة الثنائية هي تنسيق بيانات حيث تكون كل قطعة من البيانات عبارة عن عقدة يمكن أن تحتوي على ما يصل إلى أحد الوالدين وطرفين فرعيين. غالبًا ما يتم رسمها كشجرة متفرعة ، ومن هنا جاءت تسميتها.
  • قائمة الانتظار هي عبارة عن مجموعة بيانات مسماة بشكل مناسب حيث يكون أول شيء يتم إدخاله في قائمة الانتظار هو أيضًا أول شيء يخرج (مثل الانتظار في الطابور). في قائمة انتظار الأولوية ، يتم تخزين البيانات حسب أولويتها ، بحيث يكون أول شيء يخرج هو الشيء الأكثر إلحاحًا ، الشيء ذو الأولوية الأقل ، بدلاً من الشيء الأول المدرج في القائمة.
  • في مثال "ab ab cab" ، ستبدو قائمة انتظار الأولوية لديك على النحو التالي: {'c': 1، EOF: 1، ': 2،' a ': 3،' b ': 3}
ضغط البيانات باستخدام تشفير هوفمان الخطوة 3
ضغط البيانات باستخدام تشفير هوفمان الخطوة 3

الخطوة 3. ابدأ في بناء شجرتك

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

تبدو قائمة انتظار الأولوية الآن كما يلي: {'': 2 ، عقدة جديدة: 2 ، 'a': 3 ، 'b': 3}

ضغط البيانات باستخدام تشفير هوفمان الخطوة 4
ضغط البيانات باستخدام تشفير هوفمان الخطوة 4

الخطوة 4. الانتهاء من بناء شجرتك:

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

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

الخطوة 5. إنشاء خريطة ترميز. المشي من خلال الشجرة للوصول إلى كل شخصية. في كل مرة تزور فيها الطفل الأيسر للعقدة ، يكون هذا الرقم "0". في كل مرة تزور فيها الطفل المناسب للعقدة ، يكون هذا الرقم "1". عندما تصل إلى شخصية ما ، قم بتخزين الشخصية بتسلسل 0 و 1 الذي استغرقه للوصول إلى هناك. هذا التسلسل هو ما سيتم ترميزه في الملف المضغوط. تخزين الشخصيات وتسلسلها في الخريطة.

  • على سبيل المثال ، ابدأ من الجذر. قم بزيارة الطفل الأيسر للجذر ، ثم قم بزيارة الطفل الأيسر لتلك العقدة. نظرًا لأن العقدة التي أنت الآن ليس لديها أي أطفال ، فقد وصلت إلى شخصية. هذا هو ' '. نظرًا لأنك مشيت إلى اليسار مرتين للوصول إلى هنا ، فإن تشفير "" هو "00".
  • بالنسبة لهذه الشجرة ، ستبدو الخريطة على النحو التالي: {'': "00"، 'a': "10"، 'b': "11"، 'c': "010"، EOF: "011"}.
ضغط البيانات باستخدام تشفير هوفمان الخطوة 6
ضغط البيانات باستخدام تشفير هوفمان الخطوة 6

الخطوة 6. في ملف الإخراج ، قم بتضمين خريطة الترميز كرأس

سيسمح ذلك بفك تشفير الملف.

ضغط البيانات باستخدام تشفير هوفمان الخطوة 7
ضغط البيانات باستخدام تشفير هوفمان الخطوة 7

الخطوة 7. قم بتشفير الملف

لكل حرف في الملف ليتم تشفيره ، اكتب التسلسل الثنائي الذي قمت بتخزينه في الخريطة. بمجرد الانتهاء من ترميز الملف ، تأكد من إضافة EOF إلى النهاية.

  • بالنسبة للملف "ab ab cab" ، سيبدو الملف المرمز بالشكل التالي: "1011001011000101011011".
  • يتم تخزين الملفات على هيئة بايت (8 بت أو 8 أرقام ثنائية). نظرًا لأن خوارزمية Huffman Encoding لا تستخدم تنسيق 8 بت ، فغالبًا ما لا تحتوي الملفات المشفرة على أطوال مضاعفات 8. سيتم ملء الأرقام المتبقية بأصفار. في هذه الحالة ، ستتم إضافة صفرين في نهاية الملف ، والتي تبدو كمساحة أخرى. قد تكون هذه مشكلة: كيف يعرف مفكك الشفرة متى يتوقف عن القراءة؟ ومع ذلك ، نظرًا لأننا قمنا بتضمين حرف نهاية الملف ، فسوف تصل وحدة فك التشفير إلى هذا ثم تتوقف ، متجاهلة أي شيء آخر تمت إضافته بعد ذلك.

جزء 2 من 2: فك التشفير

ضغط البيانات باستخدام تشفير هوفمان الخطوة 8
ضغط البيانات باستخدام تشفير هوفمان الخطوة 8

الخطوة الأولى: اقرأ في ملف Huffman-encoded

أولاً ، اقرأ العنوان ، الذي يجب أن يكون خريطة الترميز. استخدم هذا لبناء شجرة فك التشفير بنفس الطريقة التي بنيت بها الشجرة التي استخدمتها لترميز الملف. يجب أن تكون الشجرتان متطابقتين.

ضغط البيانات باستخدام تشفير هوفمان الخطوة 9
ضغط البيانات باستخدام تشفير هوفمان الخطوة 9

الخطوة الثانية: اقرأ الرقم الثنائي رقمًا واحدًا في كل مرة

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

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

ضغط البيانات باستخدام تشفير هوفمان الخطوة 10
ضغط البيانات باستخدام تشفير هوفمان الخطوة 10

الخطوة 3. كرر حتى تصل إلى EOF

تهانينا! لقد قمت بفك تشفير الملف.

موصى به: