Move-to-front transform (original) (raw)
Move to front (englisch „Nach vorne verschieben“, auch: Rotierende Kodierung) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows-Wheeler-Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu können.
| Property | Value |
|---|---|
| dbo:abstract | Move-to-front (MTF; česky „přesuň na začátek“) transformace je transformace používaná v algoritmech pro kompresi dat. Obvykle se používá po provedení Burrowsovy-Wheelerovy transformace; ještě před použitím . Transformace mění entropii vstupních dat. Základní myšlenkou je nahrazovat symboly vstupní abecedy za jejich indexy ze seznamu symbolů a naopak (transformace je invertibilní). Přičemž aktuálně kódovaný symbol je přesunut v tomto seznamu vždy na počátek (odtud název). Lokálně tedy platí, že často vyskytující se symboly jsou umístěny blíže začátku seznamu. Transformace pracuje proudově, nikoli blokově. Data se musejí dekódovat ve stejném pořadí, v jakém byla zakódována, protože kodér i dekodér si musejí udržovat seznam symbolů a musejí pracovat ve shodě. Seznam má velikost rovnu počtu symbolů vstupní abecedy. Typicky se používá v kompresních metodách jako druhá fáze po Burrowsově-Wheelerově transformaci. Právě tyto transformace využívá například kompresní metoda bzip2. Metoda byla několikrát vylepšena a následně nahrazena sofistikovanějšími algoritmy . (cs) Move to front (englisch „Nach vorne verschieben“, auch: Rotierende Kodierung) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows-Wheeler-Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu können. (de) The move-to-front (MTF) transform is an encoding of data (typically a stream of bytes) designed to improve the performance of entropy encoding techniques of compression. When efficiently implemented, it is fast enough that its benefits usually justify including it as an extra step in data compression algorithm. This algorithm was first published by B. Ryabko under the name of "book stack" in 1980. Subsequently, it was rediscovered by J.K. Bentley et al. in 1986, as attested in the explanatory note. (en) L'algorithme MTF (pour move-to-front : « déplacer vers l'avant ») est un système de transformation de flot utilisé notamment dans le domaine de la compression de données en informatique. Il consiste à remplacer chaque caractère par un indice, donné par un tableau évoluant de manière dynamique. Cette technique est notamment utilisable en conjonction avec la transformée de Burrows-Wheeler. (fr) De haal-naar-vorencodering is een transformatie die een tekenreeks gemakkelijker te bewerken maakt. Een tekenreeks zal na toepassen van haal-naar-vorencodering uit een reeks relatief kleine getallen bestaan. Dat is er een reden voor dat de codering in de datacompressie wordt gebruikt. Het is vooral als reorganisatiestap handig. Het is na de codering gemakkelijker om de huffmancodering toe te passen. Vergelijk het ook met de Burrows-Wheelertransformatie en het gebruik van bzip2. Het Alt-Tabsysteem in Microsoft Windows is in feite een haal-naar-vorensysteem. Er is een lijst van vensters en de gebruiker kiest door de Tab een aantal malen in te drukken welk venster vooraan in de lijst komt te staan. Op deze manier minimaliseer je het aantal tab-aanslagen als je vaak tussen twee vensters wisselt. (nl) Move to Front（先頭移動法、MTF）とは、の一種で、再帰順位符号化（receny rank）法や book stack とも呼ばれる符号。実装に配列やリストを使用して、要素を先頭に移動する操作をメインとすることからこの呼称で呼ばれることが多い。 ブロックソートを行ったデータをMTF処理すると圧縮しやすいデータになることから、主にブロックソートを用いる圧縮プロセスの一部として利用されている。 動作原理は単純ながら、非定常であるため、その理論的性能の解析は困難であった。2005年に、1次の特定の状況においてのみ、エントロピーレートを達成することが明らかになっている。 (ja) Move To Front (MTF) – prosta transformacja strumienia danych, używana jako część niektórych procesów kompresji, której zastosowanie może spowodować zmniejszenie entropii. Co za tym idzie, algorytmy kompresji zależne od tej własności (kodowanie Shannona, Shannona-Fano, Huffmana, arytmetyczne) dają lepsze wyniki; mogą także wyprodukować sekwencje lepiej kompresowane metodą RLE. To, czy zastosowanie MTF rzeczywiście doprowadzi do zmniejszenia entropii, zależy od danych – zmniejszenie entropii występuje, gdy częstotliwości występowania symboli wykazują lokalną spójność. Dane o takiej charakterystyce są tworzone przez transformatę Burrowsa-Wheelera, dlatego MTF jest zwykle używana w połączeniu właśnie z nią. (Uwaga: sama transformata Burrowsa-Wheelera nie powoduje zmniejszenia entropii). Jak wspomniano, algorytm kodowania i dekodowania jest bardzo prosty, dlatego jego implementacje są bardzo efektywne. (pl) Перемещение к началу (англ. move-to-front, MTF) — преобразование для кодирования данных (обычно потока байтов), разработанное для улучшения производительности энтропийного кодирования. При хорошей реализации оно достаточно быстро для включения как дополнительный шаг в алгоритмах сжатия данных. Также может использоваться совместно с BWT, преобразованием Барроуза — Уилера. (ru) MTF（Move-To-Front）是一种数据编码方式，作为一个额外的步骤，用于提高数据压缩技术效果。MTF主要使用的是数据“空间局部性”，也就是最近出现过的字符很可能在接下来的文本附近再次出现。 (zh) |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20001003063538/http:/www.arturocampos.com/ac_mtf.html |
| dbo:wikiPageID | 1039739 (xsd:integer) |
| dbo:wikiPageLength | 11744 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123734182 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Python_(programming_language) dbr:Algorithm dbc:Data_compression dbr:Entropy_(information_theory) dbr:Entropy_encoding dbc:Lossless_compression_algorithms dbr:Byte dbr:Data dbr:Data_compression dbr:Linked_list dbr:ASCII dbr:Self-organizing_list dbr:Array_data_structure dbc:Articles_with_example_Python_(programming_language)_code dbc:Transforms dbr:Big_O_notation dbr:Code dbr:Plain_text dbr:To_be,_or_not_to_be dbr:Burrows–Wheeler_transform dbr:List_(computing) |
| dbp:wikiPageUsesTemplate | dbt:Examples dbt:Clarify dbt:Code dbt:Confusing dbt:Main dbt:More_citations_needed dbt:Reflist dbt:Compression_methods |
| dct:subject | dbc:Data_compression dbc:Lossless_compression_algorithms dbc:Articles_with_example_Python_(programming_language)_code dbc:Transforms |
| rdf:type | 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 | Move to front (englisch „Nach vorne verschieben“, auch: Rotierende Kodierung) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows-Wheeler-Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu können. (de) The move-to-front (MTF) transform is an encoding of data (typically a stream of bytes) designed to improve the performance of entropy encoding techniques of compression. When efficiently implemented, it is fast enough that its benefits usually justify including it as an extra step in data compression algorithm. This algorithm was first published by B. Ryabko under the name of "book stack" in 1980. Subsequently, it was rediscovered by J.K. Bentley et al. in 1986, as attested in the explanatory note. (en) L'algorithme MTF (pour move-to-front : « déplacer vers l'avant ») est un système de transformation de flot utilisé notamment dans le domaine de la compression de données en informatique. Il consiste à remplacer chaque caractère par un indice, donné par un tableau évoluant de manière dynamique. Cette technique est notamment utilisable en conjonction avec la transformée de Burrows-Wheeler. (fr) Move to Front（先頭移動法、MTF）とは、の一種で、再帰順位符号化（receny rank）法や book stack とも呼ばれる符号。実装に配列やリストを使用して、要素を先頭に移動する操作をメインとすることからこの呼称で呼ばれることが多い。 ブロックソートを行ったデータをMTF処理すると圧縮しやすいデータになることから、主にブロックソートを用いる圧縮プロセスの一部として利用されている。 動作原理は単純ながら、非定常であるため、その理論的性能の解析は困難であった。2005年に、1次の特定の状況においてのみ、エントロピーレートを達成することが明らかになっている。 (ja) Перемещение к началу (англ. move-to-front, MTF) — преобразование для кодирования данных (обычно потока байтов), разработанное для улучшения производительности энтропийного кодирования. При хорошей реализации оно достаточно быстро для включения как дополнительный шаг в алгоритмах сжатия данных. Также может использоваться совместно с BWT, преобразованием Барроуза — Уилера. (ru) MTF（Move-To-Front）是一种数据编码方式，作为一个额外的步骤，用于提高数据压缩技术效果。MTF主要使用的是数据“空间局部性”，也就是最近出现过的字符很可能在接下来的文本附近再次出现。 (zh) Move-to-front (MTF; česky „přesuň na začátek“) transformace je transformace používaná v algoritmech pro kompresi dat. Obvykle se používá po provedení Burrowsovy-Wheelerovy transformace; ještě před použitím . Transformace mění entropii vstupních dat. Základní myšlenkou je nahrazovat symboly vstupní abecedy za jejich indexy ze seznamu symbolů a naopak (transformace je invertibilní). Přičemž aktuálně kódovaný symbol je přesunut v tomto seznamu vždy na počátek (odtud název). Lokálně tedy platí, že často vyskytující se symboly jsou umístěny blíže začátku seznamu. (cs) De haal-naar-vorencodering is een transformatie die een tekenreeks gemakkelijker te bewerken maakt. Een tekenreeks zal na toepassen van haal-naar-vorencodering uit een reeks relatief kleine getallen bestaan. Dat is er een reden voor dat de codering in de datacompressie wordt gebruikt. Het is vooral als reorganisatiestap handig. Het is na de codering gemakkelijker om de huffmancodering toe te passen. Vergelijk het ook met de Burrows-Wheelertransformatie en het gebruik van bzip2. (nl) Move To Front (MTF) – prosta transformacja strumienia danych, używana jako część niektórych procesów kompresji, której zastosowanie może spowodować zmniejszenie entropii. Co za tym idzie, algorytmy kompresji zależne od tej własności (kodowanie Shannona, Shannona-Fano, Huffmana, arytmetyczne) dają lepsze wyniki; mogą także wyprodukować sekwencje lepiej kompresowane metodą RLE. To, czy zastosowanie MTF rzeczywiście doprowadzi do zmniejszenia entropii, zależy od danych – zmniejszenie entropii występuje, gdy częstotliwości występowania symboli wykazują lokalną spójność. (pl) |
| rdfs:label | Move-to-front transformace (cs) Move to front (de) Move-to-front (fr) Move To Front (ja) Move-to-front transform (en) Haal-naar-vorencodering (nl) Move To Front (pl) Move-To-Front (ru) Move-to-front变换 (zh) |
| owl:sameAs | freebase:Move-to-front transform yago-res:Move-to-front transform wikidata:Move-to-front transform dbpedia-cs:Move-to-front transform dbpedia-de:Move-to-front transform dbpedia-fr:Move-to-front transform dbpedia-ja:Move-to-front transform dbpedia-nl:Move-to-front transform dbpedia-pl:Move-to-front transform dbpedia-ru:Move-to-front transform dbpedia-zh:Move-to-front transform https://global.dbpedia.org/id/2c25x |
| prov:wasDerivedFrom | wikipedia-en:Move-to-front_transform?oldid=1123734182&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Move-to-front_transform |
| is dbo:wikiPageDisambiguates of | dbr:MTF |
| is dbo:wikiPageRedirects of | dbr:Move-to-front dbr:Move-to-front_coder dbr:Move-to-front_heuristic dbr:Move_to_front dbr:MTF_transform |
| is dbo:wikiPageWikiLink of | dbr:List_of_archive_formats dbr:Bzip2 dbr:Algorithm_BSTW dbr:Daniel_Sleator dbr:Burrows–Wheeler_transform dbr:Chain_code dbr:MTF dbr:Self-organising_heuristic dbr:Move-to-front dbr:Move-to-front_coder dbr:Move-to-front_heuristic dbr:Move_to_front dbr:MTF_transform |
| is foaf:primaryTopic of | wikipedia-en:Move-to-front_transform |