التنبؤ عن طريق المطابقة الجزئية

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

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

يُحدد عدد الرموز السابقة، n ، رتبة نموذج PPM، ويُرمز له بـ PPM( n ). توجد أيضًا متغيرات غير محدودة، حيث لا توجد قيود على طول السياق، ويُرمز لها بـ PPM* . إذا تعذر التنبؤ باستخدام جميع رموز السياق n ، تُجرى محاولة تنبؤ باستخدام n  -  1 رمزًا. تُكرر هذه العملية حتى يتم العثور على تطابق أو حتى نفاد الرموز في السياق. عندئذٍ، يُعتمد تنبؤ ثابت.

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

تختلف تطبيقات ضغط PPM اختلافًا كبيرًا في التفاصيل الأخرى. عادةً ما يتم تسجيل اختيار الرموز باستخدام الترميز الحسابي ، مع إمكانية استخدام ترميز هوفمان أو حتى نوع من تقنيات ترميز القاموس . يمكن أيضًا توسيع النموذج الأساسي المستخدم في معظم خوارزميات PPM للتنبؤ برموز متعددة. كما يمكن استخدام نمذجة غير ماركوفية إما لاستبدال نمذجة ماركوف أو استكمالها. عادةً ما يكون حجم الرمز ثابتًا، بايت واحد في الغالب، مما يُسهّل التعامل مع أي تنسيق ملف.

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

PPMd هو تطبيق مجاني لـ PPMII (PPM مع توريث المعلومات) من تطوير ديمتري شكارين، وقد خضع لعدة تعديلات غير متوافقة. ^{[ 1 ]} يُستخدم افتراضيًا بصيغة ملف RAR ، وهو متوفر أيضًا بصيغتي 7z و zip .

أدت محاولات تحسين خوارزميات PPM إلى ظهور سلسلة خوارزميات ضغط البيانات PAQ .

يتم استخدام خوارزمية PPM، بدلاً من استخدامها للضغط، لزيادة كفاءة إدخال المستخدم في برنامج طريقة الإدخال البديلة Dasher .

• نموذج اللغة
• n -gram

• كليري، ج.؛ ويتن، إ. (أبريل 1984). "ضغط البيانات باستخدام الترميز التكيفي ومطابقة السلاسل الجزئية". مجلة IEEE للمعاملات في الاتصالات 32 (4): 396-402 . CiteSeerX 10.1.1.14.4305 . doi : 10.1109/TCOM.1984.1096090 . 
• موفات، أ. (نوفمبر 1990). "تطبيق نظام ضغط البيانات PPM". مجلة IEEE للمعاملات في الاتصالات، 38 (11): 1917-1921 . CiteSeerX 10.1.1.120.8728 . doi : 10.1109/26.61469 . 
• كليري، جي جي؛ تيهان، دبليو جيه؛ ويتن، آي إتش (1997). "سياقات الطول غير المحدودة لـ PPM" . مجلة الكمبيوتر . 40 (2_و_3). أكسفورد، إنجلترا: مطبعة جامعة أكسفورد: 67-75 . doi : 10.1093/comjnl/40.2_and_3.67 . ISSN 0010-4620 . 
• سي. بلوم، حل مشاكل نمذجة السياق .
• WJ Teahan، تقدير الاحتمالية لـ PPM ، المصدر الأصلي من archive.org .
• شورمان، T.؛ غراسبيرجر، ب. (سبتمبر 1996). “تقدير الإنتروبيا لتسلسلات الرمز”. فوضى . 6 (3): 414– 427. أرخايف : cond-mat/0203436 . بيب كود : 1996الفوضى...6..414S . دوى : 10.1063/1.166191 . بميد 12780271 . S2CID 10090433 .