Az algoritmusok a részleges elismerés becslés (vagy PPM számára Jóslás részleges Matching ) egy család algoritmusok, adattömörítés veszteség nélkül, statisztikák és adaptív által feltalált John Cleary és Ian Witten a 1984 .
A részleges felismerés előrejelzése kontextusmodellezésen alapul, hogy értékelje a különböző szimbólumok megjelenésének valószínűségét.
Általában a kontextus olyan szimbólumkészlet, amely már találkozott az adatforrással (fájl, adatfolyam). Az előrejelzéshez használt kontextus hossza megadja a sorrendjét a PPM-nek. PPM (N) -vel jelöljük az N. rendű PPM-et. Például a PPM (1) az 1. rendű PPM; vagyis csak az előző szimbólum alapján jósolja meg a következő mintát. A PPM * -vel végtelen sorrendű PPM-et jelölünk; vagyis a már elemzett teljes adatforrás alapján megjósolja a következő mintát.
A kontextus lehetővé teszi a különböző szimbólumok valószínűségének meghatározását a bejegyzések előzményeinek köszönhetően: minden kontextushoz társulnak a különböző szimbólumok megjelenési frekvenciái.
Általában minél hosszabb ideig használjuk a kontextust, annál jobb az előrejelzés.
A hosszú összefüggések használatának egyik problémája az üres történelem esete: amikor egy adott kontextussal először találkozunk. A két leggyakoribb megoldás az előre rögzített valószínűségek használata és a prediktor sorrendjének dinamikus változása. Például, ha egy PPM (8) nem rendelkezik előzményekkel a 8 hosszúságú kontextushoz, akkor egy előzményt keres egy 7, majd 6 hosszúságú kontextusra, amíg meg nem talál egy előzményt vagy a -1 sorrendre esik , ebben az esetben előre meghatározott valószínűségeket használnak.
A kapott jóslat bemenetként szolgál az entrópia kódolásához , leggyakrabban aritmetikai kódoláshoz , bár bármilyen entrópia kódolás ( Huffman-kódolás ...) használható.
Számos PPM kombinálható egymással és más típusú prediktorokkal a kontextusok súlyozásával , ami lehetővé teszi a modellezett tartomány kiterjesztését vagy a modellezés pontosságának javítását.
A PPM egy szimmetrikus algoritmus. Ez azt jelenti, hogy ugyanezt teszi a tömörítéshez és a kicsomagoláshoz. Ez azt is jelenti, hogy sebessége mindkét esetben azonos (ha nem vesszük figyelembe az I / O bonyolultságait), és hogy a szükséges memória mennyisége (az előzmények és a kontextusok tárolásához) azonos.
A legtöbb PPM implementáció a tömörítés során frissíti modelljét (ezt adaptív statisztikai tömörítésnek nevezik), ami alkalmassá teszi az algoritmust adatfolyamok ( adatfolyamok ) feldolgozására , mivel soha nem szükséges ismerni az eljövendő szimbólumokat.
A PPM-ek által elért tömörítési arányok a manapság legjobban elért eredmények, különösen a szöveg esetében.
A szükséges memória mennyisége nagyon kevéstől a sokig változik. A PPM (0) nagyon kevés memóriát igényel, míg a PPM * végtelen memóriát használhat.
A sebesség, különösen a dekompresszió, a PPM gyenge pontja. Az aszimmetrikus algoritmustól (például a Lempel-Ziv család ) ellentétben , amelyeknél a dekompresszió sokkal kevesebb lépést tartalmaz, mint a tömörítés, a PPM dekompressziója szigorúan megegyezik a tömörítéssel.
Bár a legtöbb PPM implementáció bájtokon dolgozik, így bármilyen típusú fájlt képes speciális feldolgozás nélkül feldolgozni, egyes változatok más típusú szimbólumokat használnak. A szöveg speciális változata az, hogy a szavakat szimbólumként használja, nem pedig karakterként.
Hasonló megközelítést alkalmaznak a dinamikus Markov-modellező algoritmusok is.
A megbízhatóbb előrejelzések érdekében egyes algoritmusok több statisztikai modellt kombinálnak.
A PPM az automatikus kiegészítés parancsaihoz is használható néhány Unix rendszerben.