Prediction by partial matching
التنبؤ بالتطابق الجزئي[عدل]
التنبؤ بالتطابق الجزئي (PPM) هي تقنية ضغط بيانات إحصائية تكيفية تستند إلى النمذجة السياقية والتنبؤ. تستخدم نماذج PPM مجموعة من الرموز السابقة في تدفق الرموز غير المضغوطة للتنبؤ بالرمز التالي في التدفق. يمكن أيضًا استخدام خوارزميات PPM لتجميع البيانات إلى مجموعات متوقعة في تحليل التجميع.
النظرية[عدل]
غالبًا ما يتم تقليل التنبؤات إلى ترتيب الرموز. يتم ترتيب كل رمز (حرف، بت، أو أي كمية أخرى من البيانات) قبل ضغطه، ويحدد نظام الترتيب الكلمة الشفرية المقابلة (وبالتالي معدل الضغط). في العديد من خوارزميات الضغط، يكون الترتيب مكافئًا لتقدير دالة الكتلة الاحتمالية. بناءً على الحروف السابقة (أو بناءً على سياق)، يتم تعيين احتمال لكل رمز. على سبيل المثال، في ترميز الحسابي، يتم ترتيب الرموز حسب احتمالات ظهورها بعد الرموز السابقة، ويتم ضغط التسلسل بأكمله إلى كسر واحد يتم حسابه وفقًا لهذه الاحتمالات.
يحدد عدد الرموز السابقة، n, ترتيب نموذج PPM الذي يُشار إليه باسم PPM(n). توجد أيضًا أنواع غير محدودة حيث لا توجد قيود على طول السياق وتُشار إليها باسم PPM*. إذا لم يتمكن من التنبؤ بناءً على جميع رموز السياق n, يتم محاولة التنبؤ مع n − 1 رموز. يتم تكرار هذه العملية حتى يتم العثور على تطابق أو لا تبقى رموز في السياق. في هذه المرحلة، يتم إجراء تنبؤ ثابت.
يتم إجراء الكثير من العمل في تحسين نموذج PPM من خلال معالجة المدخلات التي لم تحدث بعد في تدفق المدخلات. الطريقة الواضحة لمعالجتها هي إنشاء "رمز غير مرئي أبدًا" الذي يؤدي إلى تشغيل تسلسل الهروب. ولكن، ما هو الاحتمال الذي يجب تعيينه لرمز لم يتم رؤيته من قبل؟ يُسمى هذا مشكلة التواتر الصفري. يستخدم نوع واحد مقدر لابلاس، الذي يعين لـ "رمز غير مرئي أبدًا" عددًا ثابتًا من التعدادات الزائدة واحد. يزيد نوع آخر يُسمى PPMd من عدد التعدادات الزائدة لـ "رمز غير مرئي أبدًا" كلما تم استخدام "رمز غير مرئي أبدًا". (بمعنى آخر، يقدر PPMd احتمال رمز جديد على أنه نسبة عدد الرموز الفريدة إلى إجمالي عدد الرموز الملاحظة).
التنفيذ[عدل]
تختلف تنفيذات ضغط PPM كثيرًا في التفاصيل الأخرى. غالبًا ما يتم تسجيل اختيار الرمز الفعلي باستخدام ترميز الحسابي، على الرغم من أنه من الممكن أيضًا استخدام ترميز هافمان أو حتى نوع من أنواع تقنيات الترميز بالقاموس. يمكن أيضًا توسيع النموذج الأساسي المستخدم في معظم خوارزميات PPM للتنبؤ برموز متعددة. كما أنه من الممكن استخدام النمذجة غير الماركوفية لاستبدال أو تكميل النمذجة الماركوفية. يكون حجم الرمز عادةً ثابتًا، ويبلغ عادةً بايت واحد، مما يجعل معالجة أي تنسيق ملف عامةً سهلة.
تم العثور على الأبحاث المنشورة حول هذه العائلة من الخوارزميات منذ منتصف الثمانينيات. لم تكن تنفيذات البرامج شائعة حتى أوائل التسعينيات لأن خوارزميات PPM تتطلب كمية كبيرة من الرام. تعتبر تنفيذات PPM الحديثة من بين أفضل برامج ضغط بدون فقدان لنصوص اللغة الطبيعية.
PPMd هو تنفيذ عام لـ PPMII (PPM مع وراثة المعلومات) من قبل ديمتري شكارين الذي مر بعدة مراجعات غير متوافقة.[١] يتم استخدامه في تنسيق الملف RAR افتراضيًا. كما أنه متاح في تنسيقات الملفات 7z وzip.
أدت محاولات تحسين خوارزميات PPM إلى سلسلة PAQ من خوارزميات ضغط البيانات.
يتم استخدام خوارزمية PPM، بدلاً من استخدامها للضغط، لزيادة كفاءة إدخال المستخدم في برنامج طريقة إدخال بديلة Dasher.
انظر أيضًا[عدل]
المراجع[عدل]
- خطأ: لا توجد وحدة بهذا الاسم "Citation/CS1".
- خطأ: لا توجد وحدة بهذا الاسم "Citation/CS1".
- خطأ: لا توجد وحدة بهذا الاسم "Citation/CS1".
- C. Bloom, حل مشاكل النمذجة السياقية.
- W.J. Teahan, تقدير الاحتمالات لـ PPM, المصدر الأصلي من archive.org.
- خطأ: لا توجد وحدة بهذا الاسم "Citation/CS1".
- ↑ خطأ: لا توجد وحدة بهذا الاسم "citation/CS1". لاحظ: يتطلب تعيين الترميز "سيريليك (ويندوز)" يدويًا في المتصفح.
