مبرمج القاموس

مُشفِّر القاموس ، المعروف أيضاً باسم مُشفِّر الاستبدال ، هو فئة من خوارزميات ضغط البيانات غير الفاقد للبيانات ، والتي تعمل عن طريق البحث عن تطابقات بين النص المراد ضغطه ومجموعة من السلاسل النصية الموجودة في بنية بيانات (تُسمى "القاموس") يحتفظ بها المُشفِّر. عندما يجد المُشفِّر مثل هذا التطابق، فإنه يستبدل مرجعاً إلى موضع السلسلة النصية في بنية البيانات.

يستخدم بعض مُبرمجي القواميس "قاموسًا ثابتًا"، وهو قاموس تُحدد مجموعته الكاملة من السلاسل النصية قبل بدء عملية الترميز ولا تتغير خلالها. يُستخدم هذا الأسلوب غالبًا عندما تكون الرسالة أو مجموعة الرسائل المراد ترميزها ثابتة وكبيرة؛ على سبيل المثال، يقوم تطبيق يخزن محتويات كتاب في مساحة التخزين المحدودة لجهاز مساعد رقمي شخصي (PDA) عادةً بإنشاء قاموس ثابت من مُفهرس النص، ثم يستخدم هذا القاموس لضغط الآيات. تُسمى هذه الطريقة، التي تستخدم ترميز هوفمان لتمثيل الفهارس في مُفهرس النص، "هاف وورد". ^{[ 1 ]}

في طريقة مشابهة وأكثر عمومية، يُبنى قاموس من البيانات الزائدة المستخرجة من بيئة البيانات (تدفقات إدخال متنوعة)، ثم يُستخدم هذا القاموس بشكل ثابت لضغط تدفق إدخال آخر. على سبيل المثال، يُبنى قاموس من نصوص إنجليزية قديمة ثم يُستخدم لضغط كتاب. ^{[ 2 ]}

تُعدّ الطرق التي يبدأ فيها القاموس بحالة مُحددة مُسبقًا، ولكن يتغير محتواه أثناء عملية التشفير بناءً على البيانات التي تم تشفيرها مُسبقًا، أكثر شيوعًا. تعمل خوارزميتا LZ77 و LZ78 على هذا المبدأ. في LZ77، يحتوي مخزن مؤقت دائري يُسمى "النافذة المنزلقة" على آخر N بايت من البيانات المُعالجة. تعمل هذه النافذة كقاموس، حيث تُخزن فعليًا كل سلسلة فرعية ظهرت في آخر N بايت كإدخالات في القاموس. بدلًا من استخدام فهرس واحد لتحديد إدخال القاموس، يلزم وجود قيمتين: الطول ، الذي يُشير إلى طول النص المُطابق، والإزاحة ( وتُسمى أيضًا المسافة )، التي تُشير إلى أن التطابق موجود في النافذة المنزلقة بدءًا من إزاحة بايت قبل النص الحالي.

يستخدم LZ78 بنية قاموس أكثر وضوحًا؛ في بداية عملية التشفير، يكون القاموس فارغًا. تُستخدم قيمة الفهرس صفر لتمثيل نهاية السلسلة، لذا فإن الفهرس الأول في القاموس هو واحد. في كل خطوة من خطوات عملية التشفير، إذا لم يكن هناك تطابق، يُضاف آخر فهرس مطابق (أو صفر) والحرف إلى القاموس ويُخرجان إلى دفق البيانات المضغوطة. أما إذا كان هناك تطابق، فيُحدَّث فهرس العمل إلى الفهرس المطابق، ولا يُخرج أي شيء.

تُشبه خوارزمية LZW خوارزمية LZ78، إلا أن قاموسها مُهيأٌ بجميع الرموز المُمكنة. يعمل التطبيق النموذجي برموز 8 بت، لذا فإن "رموز" القاموس من 00 إلى FF (العشري 255) مُحددة مُسبقًا. تُضاف إدخالات القاموس بدءًا من القيمة 100. على عكس LZ78، إذا لم يتم العثور على تطابق (أو إذا كانت البيانات قد انتهت)، فسيتم إخراج رمز القاموس فقط. يُسبب هذا مشكلة مُحتملة لأن مُخرجات المُفكِّك تكون مُتأخرة بخطوة واحدة عن القاموس. راجع LZW لمعرفة كيفية معالجة هذه المشكلة. تشمل التحسينات في LZW التعامل مع أحجام الرموز الأخرى غير 8 بت، ووجود رموز مُخصصة لإعادة ضبط القاموس وللإشارة إلى نهاية البيانات.

يُعدّ Brotli مثالاً على مُشفّر شائع الاستخدام، يتم تهيئته بقاموس مُعرّف مسبقًا، ولكنه ينتقل لاحقًا إلى استخدام نماذج محتوى أكثر تطورًا. يتألف قاموس Brotli في معظمه من كلمات اللغة الطبيعية ومقاطع HTML وJavaScript، استنادًا إلى تحليل حركة مرور الويب. ^{[ 3 ]}

• كود قائم على القواعد النحوية
• ترميز الإنتروبيا