Prediction by partial matching (original) (raw)
El algoritmo Prediction by Partial Matching (en español Predicción por Coincidencia Parcial) o PPM es una técnica adaptativa estadística de compresión de datos basada en el y predicción. Los modelos PPM usan un conjunto de símbolos previos en el flujo de símbolos no comprimidos para predecir el siguiente símbolo en dicho flujo.
| Property | Value |
|---|---|
| dbo:abstract | Prediction by Partial Matching (PPM, englisch) ist eine Familie anpassender statistischer Datenkompressionsalgorithmen, die auf Kontextmodellen und Prognosen aufbaut. PPM-Modelle benutzen einen Satz von Symbolen aus dem vorangegangenen Symbolstrom, um das nächste Symbol des Stromes vorherzusagen. Voraussagen werden üblicherweise auf Wertungen der Symbole beschränkt. Die Zahl vorhergehender Symbole, , legt die Ordnung des PPM-Modelles fest, das als PPM(n) festgehalten wird. Unbegrenzte Varianten ohne Beschränkungen der Länge des Kontextes existieren auch und werden mit PPM* bezeichnet. Wenn aufgrund aller n Kontextsymbole keine Vorhersage gemacht werden kann, so wird eine Prognose aufgrund von versucht. Dieses Vorgehen wird wiederholt, bis ein Treffer gefunden wird oder keine Symbole im Kontext verbleiben. Zu diesem Zeitpunkt wird eine Vorhersage festgelegt. Dieser Prozess ist die Umkehrung dessen, gefolgt von dynamischen Markow-Vorhersagen, die von einem Modell der Ordnung 0 aufbauen. Ein großer Teil der Arbeit an der Optimierung eines PPM-Modells betrifft den Umgang mit Eingaben, die im Eingabestrom noch nicht auftraten. Der offensichtliche Weg damit umzugehen besteht darin, ein „Unbekannt-Symbol“ zu erzeugen, das die Escape-Sequenz auslöst. Doch welche Wahrscheinlichkeit soll einem Symbol zugeordnet werden, das noch nie aufgetreten ist? Dies wird das Problem der 0-Häufigkeit genannt. Eine Vorgehensweise teilt dem „Unbekannt-Symbol“ einen festgelegten Pseudowert von 1 zu. Eine PPM-D genannte Variante erhöht den Pseudowert bei jedem Auftritt des „Unbekannt-Symbols“. (Anders ausgedrückt schätzt PPM-D also die Wahrscheinlichkeit eines neuen Symbols als das Verhältnis der Anzahl einzigartiger Symbole zur Anzahl aller Symbole insgesamt.) Umsetzungen von Kompression mittels PPM sind in anderen Details sehr unterschiedlich. Die eigentliche Symbolauswahl wird üblicherweise arithmetisch kodiert, obwohl auch Huffman-Kodierung oder auch eine Art Wörterbuchkodierung möglich sind. Das zugrunde liegende Modell der meisten PPM-Algorithmen kann auch erweitert werden, um mehrere Symbole vorherzusagen. Es ist auch möglich, andere als die Markow-Modellerstellung zu verwenden, um diese entweder ganz zu ersetzen oder zu ergänzen. Die Symbolgröße ist für gewöhnlich statisch, typischerweise ein einzelnes Byte, was die generische Unterstützung jeglicher Dateiformate leicht macht. Veröffentlichungen über Forschungen an dieser Algorithmusfamilie finden sich bis zurück in die Mitte der 1980er Jahre. Softwareumsetzungen erfreuten sich bis zu den frühen 1990er Jahren keiner Beliebtheit, da PPM-Algorithmen eine beachtliche Menge an Arbeitsspeicher benötigen. Neuere Umsetzungen von PPM finden sich unter den leistungsfähigsten verlustfreien Datenkompressionsverfahren für Text in natürlichen Sprachen. Der Versuch, PPM-Algorithmen zu verbessern, führte zu den PAQ-Kompressionsalgorithmen. (de) El algoritmo Prediction by Partial Matching (en español Predicción por Coincidencia Parcial) o PPM es una técnica adaptativa estadística de compresión de datos basada en el y predicción. Los modelos PPM usan un conjunto de símbolos previos en el flujo de símbolos no comprimidos para predecir el siguiente símbolo en dicho flujo. (es) Prediction by partial matching (PPM) is an adaptive statistical data compression technique based on context modeling and prediction. PPM models use a set of previous symbols in the uncompressed symbol stream to predict the next symbol in the stream. PPM algorithms can also be used to cluster data into predicted groupings in cluster analysis. (en) Les algorithmes de prédiction par reconnaissance partielle (ou PPM pour Prediction by Partial Matching) constituent une famille d'algorithmes de compression de données sans perte, statistiques et adaptatifs inventée par et en 1984. (fr) Prediction by partial matching (PPM) è un algoritmo adattivo di compressione dei dati basato su un modello di previsione statistica.PPM analizza le occorrenze dei dati non compressi presenti nell'insieme già tradotto per prevedere gli elementi successivi nelflusso da tradurre. (it) Prediction by Partial Matching(PPM)は1984年にとによって考案されたデータ圧縮アルゴリズムの1つ。この改良版が7-zip等に用いられている。非常に高い圧縮率の反面、圧縮速度はかなり遅くメモリも多く消費するアルゴリズムである。 この亜種として、、等がある。 (ja) PPM (ang. Prediction by Partial Matching) – przewidywanie przez częściowe dopasowanie) to algorytm kompresji danych oparty na kontekstowym modelowaniu statystycznym oraz predykcji. Algorytm PPM wykorzystuje układ symboli w strumieniu danych do przewidywania kolejnego symbolu. Zwykle predykcja opiera się na tworzeniu statystycznego rankingu występowania symboli. Pewna liczba poprzednich symboli wykorzystywanych w danym kroku do predykcji (n) jest określana jako rząd modelu PPM, który oznacza się jako PPM(n). Istnieją warianty algorytmu, w których rząd modelu nie jest z góry narzucany, oznaczane jako PPM*. Jeżeli przewidywanie nie może zostać dokonane w oparciu o model o rzędzie n-tym, to jego rząd jest zmniejszany o jeden. Proces jest powtarzany aż do uzyskania poprawnej predykcji lub gdy strumień danych został wyczerpany. W tym momencie wykonywana jest ustalona predykcja. Implementacje algorytmu PPM często różnią się znacznie wieloma szczegółami. Symbole mogą być kodowane poprzez kodowanie arytmetyczne, Huffmana bądź też pewne typy kodowania słownikowego. Podstawowy algorytm może zostać rozszerzony, aby przewidywać kilka symboli naraz. Rozmiar symbolu jest najczęściej stały i odpowiada jednemu bajtowi, co ułatwia przetwarzanie różnorodnych typów plików. Algorytm PPM opracowali i opublikowali w 1984 roku Cleary oraz Witten, jednak implementacje nie stały się powszechne do wczesnych lat 90., ponieważ algorytmy PPM mają duże wymagania odnośnie do pamięci RAM. Drugą negatywną cechą, która wpływa na rzadkie stosowanie algorytmu PPM, jest czas dekompresji, który jest podobny do czasu samej kompresji. Obecnie implementacje algorytmu PPM są jednymi z najlepszych algorytmów do kompresji języków naturalnych, a co za tym idzie – do kompresji plików tekstowych i baz danych zawierających duże ilości znaków alfanumerycznych. (pl) PPM (англ. Prediction by Partial Matching — передбачення щодо часткового збігу) — адаптивний статистичний алгоритм стиснення даних без втрат, що базується на і передбаченні. Модель PPM використовує контекст — множину символів у нестиснутому потоці, що передують даному, щоб передбачати значення символу на основі статистичних даних. Сама модель PPM лише пророкує значення символу, безпосереднє стиснення здійснюється за алгоритмами ентропійного кодування, наприклад, алгоритмом Гаффмана або арифметичного кодування. Довжина контексту, який використовується для передбачення, зазвичай дуже обмежена. Вона позначається n і визначає порядок моделі PPM, що позначається як PPM(n). Необмежені моделі також існують і позначаються PPM*. Якщо передбачити символ за контексту з n символів не можна, то робиться спроба передбачити його за допомогою n-1 символів. Рекурсивний перехід до моделей з меншим порядком відбувається, поки в одній з моделей не відбудеться передбачення, або коли контекст досягне нульової довжини (n=0). Моделі мірою 0 і -1 слід описати окремо. Модель нульового порядку еквівалента випадку контекстно-вільного моделювання, коли ймовірність символу визначається виключно з частоти появи у стискуваному потоці даних. Подібна модель зазвичай застосовується разом з кодуванням за Гаффманом. Модель порядку -1 — це статична модель, що присвоює ймовірності символу певне фіксоване значення; зазвичай усі символи, які можуть зустрітися в стискуваному потоці даних, при цьому вважаються рівноймовірними. Для отримання хорошої оцінки ймовірності символу слід враховувати контексти різних довжин. PPM являє собою варіант стратегії перемішування, коли оцінки ймовірностей, зроблені на підставі контекстів різних довжин, об'єднуються в одну загальну ймовірність. Отримана оцінка кодується будь-яким ентропійним кодером (ЕК), зазвичай це певний різновид арифметичного кодування. На етапі ентропійного кодування і відбувається власне стискання. Велике значення для алгоритму PPM має проблема обробки нових символів, які ще не зустрічалися у вхідному потоці — проблема нульової частоти. Деякі варіанти реалізацій PPM вважають лічильник нового символу рівним фіксованій величині, наприклад, одиниці. Інші реалізації, як наприклад, PPM-D, збільшують псевдолічильник нового символу кожен раз, коли в потоці дійсно з'являється новий символ (іншими словами, PPM-D оцінює ймовірність появи нового символу як відношення числа унікальних символів до загального числа використовуваних символів). Опубліковані дослідження алгоритмів сімейства PPM з'явилися в середині 1980-х років. Програмні реалізації не були популярні до 1990-х років, оскільки моделі PPM вимагають значної кількості оперативної пам'яті. Сучасні реалізації PPM належать до найкращих серед алгоритмів стиснення без втрат для текстів природною мовою. (uk) PPM (англ. Prediction by Partial Matching — предсказание по частичному совпадению) — адаптивный статистический алгоритм сжатия данных без потерь, основанный на и предсказании. Модель PPM использует контекст — множество символов в несжатом потоке, предшествующих данному, чтобы предсказывать значение символа на основе статистических данных. Сама модель PPM лишь предсказывает значение символа, непосредственное сжатие осуществляется алгоритмами энтропийного кодирования, как например, алгоритм Хаффмана, арифметическое кодирование. Длина контекста, который используется при предсказании, обычно сильно ограничена. Эта длина обозначается n и определяет порядок модели PPM, что обозначается как PPM(n). Неограниченные модели также существуют и обозначаются просто PPM*. Если предсказание символа по контексту из n символов не может быть произведено, то происходит попытка предсказать его с помощью n-1 символов. Рекурсивный переход к моделям с меньшим порядком происходит, пока предсказание не произойдёт в одной из моделей либо когда контекст станет нулевой длины (n=0). Модели степени 0 и −1 следует описать особо. Модель нулевого порядка эквивалента случаю контекстно-свободного моделирования, когда вероятность символа определяется исключительно из частоты его появления в сжимаемом потоке данных. Подобная модель обычно применяется вместе с кодированием по Хаффману. Модель порядка −1 представляют собой статическую модель, присваивающую вероятности символа определенное фиксированное значение; обычно все символы, которые могут встретиться в сжимаемом потоке данных, при этом считаются равновероятными. Для получения хорошей оценки вероятности символа необходимо учитывать контексты разных длин. PPM представляет собой вариант стратегии перемешивания, когда оценки вероятностей, сделанные на основании контекстов разных длин, объединяются в одну общую вероятность. Полученная оценка кодируется любым энтропийным кодером (ЭК), обычно это некая разновидность арифметического кодера. На этапе энтропийного кодирования и происходит собственно сжатие. Большое значение для алгоритма PPM имеет проблема обработки новых символов, ещё не встречавшихся во входном потоке. Это проблема носит название . Некоторые варианты реализаций PPM полагают счётчик нового символа равным фиксированной величине, например, единице. Другие реализации, как например, PPM-D, увеличивают псевдосчётчик нового символа каждый раз, когда, действительно, в потоке появляется новый символ (другими словами, PPM-D оценивает вероятность появления нового символа как отношение числа уникальных символов к общему числу используемых символов). Опубликованные исследования алгоритмов семейства PPM появились в середине 1980-х годов. Программные реализации не были популярны до 1990-х годов, потому как модели PPM требуют значительного количества оперативной памяти.Современные реализации PPM являются одними из лучших среди алгоритмов сжатия без потерь для текстов на естественном языке. (ru) |
| dbo:wikiPageExternalLink | http://compression.ru/ds/ http://cotty.16x16.com/compress/peppm.htm http://www.cbloom.com/papers/ppmz.zip http://www3.sympatico.ca/mt0000/bicom/bicom.html https://marknelson.us/posts/1991/02/01/arithmetic-coding-statistical-modeling-data-compression.html%23part2 https://academic.oup.com/comjnl/article-abstract/40/2_and_3/67/360793 https://en.wikibooks.org/wiki/Data_Compression/The_zero-frequency_problem https://github.com/rene-puschinger/ppm http://mattmahoney.net/dc/text.html |
| dbo:wikiPageID | 527918 (xsd:integer) |
| dbo:wikiPageLength | 6629 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102526205 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Pseudocount dbr:N-gram dbr:Escape_sequence dbr:Arithmetic_coding dbr:Lossless_compression dbr:Statistics dbr:Cluster_analysis dbc:Lossless_compression_algorithms dbr:Data_compression dbr:Language_model dbr:7-Zip dbr:7z dbr:Dasher_(software) dbr:PAQ dbr:Dictionary_coder dbr:Prediction dbr:RAR_(file_format) dbr:IEEE_Transactions_on_Communications dbr:Natural_language dbr:Random_Access_Memory dbr:Huffman_encoding dbr:Laplace_estimator dbr:Context_modeling |
| dbp:wikiPageUsesTemplate | dbt:Compression_Methods dbt:Cite_journal dbt:Clarify dbt:External_links dbt:In_lang dbt:No_footnotes dbt:Reflist |
| dcterms:subject | dbc:Lossless_compression_algorithms |
| gold:hypernym | dbr:Technique |
| rdf:type | dbo:TopicalConcept yago:WikicatCompressionAlgorithms yago:WikicatLosslessCompressionAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment | El algoritmo Prediction by Partial Matching (en español Predicción por Coincidencia Parcial) o PPM es una técnica adaptativa estadística de compresión de datos basada en el y predicción. Los modelos PPM usan un conjunto de símbolos previos en el flujo de símbolos no comprimidos para predecir el siguiente símbolo en dicho flujo. (es) Prediction by partial matching (PPM) is an adaptive statistical data compression technique based on context modeling and prediction. PPM models use a set of previous symbols in the uncompressed symbol stream to predict the next symbol in the stream. PPM algorithms can also be used to cluster data into predicted groupings in cluster analysis. (en) Les algorithmes de prédiction par reconnaissance partielle (ou PPM pour Prediction by Partial Matching) constituent une famille d'algorithmes de compression de données sans perte, statistiques et adaptatifs inventée par et en 1984. (fr) Prediction by partial matching (PPM) è un algoritmo adattivo di compressione dei dati basato su un modello di previsione statistica.PPM analizza le occorrenze dei dati non compressi presenti nell'insieme già tradotto per prevedere gli elementi successivi nelflusso da tradurre. (it) Prediction by Partial Matching(PPM)は1984年にとによって考案されたデータ圧縮アルゴリズムの1つ。この改良版が7-zip等に用いられている。非常に高い圧縮率の反面、圧縮速度はかなり遅くメモリも多く消費するアルゴリズムである。 この亜種として、、等がある。 (ja) Prediction by Partial Matching (PPM, englisch) ist eine Familie anpassender statistischer Datenkompressionsalgorithmen, die auf Kontextmodellen und Prognosen aufbaut. PPM-Modelle benutzen einen Satz von Symbolen aus dem vorangegangenen Symbolstrom, um das nächste Symbol des Stromes vorherzusagen. Der Versuch, PPM-Algorithmen zu verbessern, führte zu den PAQ-Kompressionsalgorithmen. (de) PPM (ang. Prediction by Partial Matching) – przewidywanie przez częściowe dopasowanie) to algorytm kompresji danych oparty na kontekstowym modelowaniu statystycznym oraz predykcji. Algorytm PPM wykorzystuje układ symboli w strumieniu danych do przewidywania kolejnego symbolu. Zwykle predykcja opiera się na tworzeniu statystycznego rankingu występowania symboli. Pewna liczba poprzednich symboli wykorzystywanych w danym kroku do predykcji (n) jest określana jako rząd modelu PPM, który oznacza się jako PPM(n). Istnieją warianty algorytmu, w których rząd modelu nie jest z góry narzucany, oznaczane jako PPM*. Jeżeli przewidywanie nie może zostać dokonane w oparciu o model o rzędzie n-tym, to jego rząd jest zmniejszany o jeden. Proces jest powtarzany aż do uzyskania poprawnej predykcji lub gdy (pl) PPM (англ. Prediction by Partial Matching — предсказание по частичному совпадению) — адаптивный статистический алгоритм сжатия данных без потерь, основанный на и предсказании. Модель PPM использует контекст — множество символов в несжатом потоке, предшествующих данному, чтобы предсказывать значение символа на основе статистических данных. Сама модель PPM лишь предсказывает значение символа, непосредственное сжатие осуществляется алгоритмами энтропийного кодирования, как например, алгоритм Хаффмана, арифметическое кодирование. (ru) PPM (англ. Prediction by Partial Matching — передбачення щодо часткового збігу) — адаптивний статистичний алгоритм стиснення даних без втрат, що базується на і передбаченні. Модель PPM використовує контекст — множину символів у нестиснутому потоці, що передують даному, щоб передбачати значення символу на основі статистичних даних. Сама модель PPM лише пророкує значення символу, безпосереднє стиснення здійснюється за алгоритмами ентропійного кодування, наприклад, алгоритмом Гаффмана або арифметичного кодування. (uk) |
| rdfs:label | Prediction by Partial Matching (de) Prediction by Partial Matching (algoritmo de compresión) (es) Prédiction par reconnaissance partielle (fr) Prediction by Partial Matching (it) Prediction by Partial Matching (ja) Prediction by partial matching (en) PPM (kompresja) (pl) Алгоритм сжатия PPM (ru) PPM (алгоритм стиснення) (uk) |
| owl:sameAs | freebase:Prediction by partial matching yago-res:Prediction by partial matching wikidata:Prediction by partial matching dbpedia-de:Prediction by partial matching dbpedia-es:Prediction by partial matching dbpedia-fr:Prediction by partial matching dbpedia-it:Prediction by partial matching dbpedia-ja:Prediction by partial matching dbpedia-pl:Prediction by partial matching dbpedia-ru:Prediction by partial matching dbpedia-uk:Prediction by partial matching https://global.dbpedia.org/id/2PZnT |
| prov:wasDerivedFrom | wikipedia-en:Prediction_by_partial_matching?oldid=1102526205&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Prediction_by_partial_matching |
| is dbo:wikiPageDisambiguates of | dbr:PPM |
| is dbo:wikiPageRedirects of | dbr:PPMd dbr:Prediction_by_Partial_Matching dbr:PPM_compression_algorithm |
| is dbo:wikiPageWikiLink of | dbr:Normalized_compression_distance dbr:List_of_archive_formats dbr:Dynamic_Markov_compression dbr:FreeArc dbr:Lempel–Ziv–Markov_chain_algorithm dbr:Lossless_compression dbr:Zstd dbr:PPM dbr:Adaptive_algorithm dbr:Additive_smoothing dbr:Data_compression dbr:John_G._Cleary dbr:7-Zip dbr:Dasher_(software) dbr:PAQ dbr:RAR_(file_format) dbr:PPMD dbr:PPMd dbr:Prediction_by_Partial_Matching dbr:PPM_compression_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Prediction_by_partial_matching |