| dbpprop:abstract
|
- The Burrows–Wheeler transform (BWT, also called block-sorting compression), is an algorithm used in data compression techniques such as bzip2. It was invented by Michael Burrows and David Wheeler in 1994 while working at DEC Systems Research Center in Palo Alto, California. It is based on a previously unpublished transformation discovered by Wheeler in 1983. When a character string is transformed by the BWT, none of its characters change value. The transformation permutes the order of the characters. If the original string had several substrings that occurred often, then the transformed string will have several places where a single character is repeated multiple times in a row. This is useful for compression, since it tends to be easy to compress a string that has runs of repeated characters by techniques such as move-to-front transform and run-length encoding. For example: The output is easier to compress because it has many repeated characters. In fact, in the transformed string, there are a total of six runs of identical characters: XX, SS, PP, II, and III, which together make 13 out of the 44 characters in it.
- Die Burrows-Wheeler-Transformation (BWT) ist ein Algorithmus, der in Datenkompressionstechniken wie bzip2 Anwendung findet, dabei allerdings selbst keine Datenkompression durchführt. Er wurde von Michael Burrows und David Wheeler entwickelt.
- Burrows-Wheelerova transformace, anglicky Burrows-Wheeler transform (BWT) je pomocný algoritmus používaný v technikách komprese dat. Transformaci objevili Michael Burrows a David Wheeler. Samotná transformace data nijak nekomprimuje. Způsobí pouze změnu pořadí symbolů. V případě, že vstupní řetězec symbolů má několik podřetězců, které se v něm vyskytují vícekrát, bude mít výstupní řetězec několik míst, kde se vyskytuje stejný symbol několikrát za sebou. To je výhodné například pro RLE kompresi. Transformace ovšem přidává k výstupnímu řetězci informaci o umístění symbolu konce původního řetězce (tzv. EOF symbol). Princip této transformace spočívá v tom, že se ze vstupního řetězce (zakončeného symbolem EOF) vytvoří všechny jeho možné rotace. Tyto se dále klasicky setřídí. Ze setříděného pole rotací původního řetězce se do výstupního zapíše postupně od počátku poslední symbol z každé rotace. Na výstupu je tedy transformovaný vstup rozšířený o ukazatel na konec původního řetězce. Příklad transformace textového řetězce "^BANANA@" (zavináč značí EOF symbol) je řetězec "BNN^AA@A". Příklad komprese je podrobně vysvětlen na en:Burrows-Wheeler transform. Tuto transformaci využívá například kompresní metoda bzip2.
- La transformée de Burrows-Wheeler, couramment appelée BWT (pour Burrows-Wheeler Transform) est une technique utilisée en compression de données. Elle fut inventée par Michael Burrows et David Wheeler. Cette technique fut rendue publique en 1994, à la suite de travaux précédents de Wheeler en 1983. Il ne s'agit pas à proprement parler d'un algorithme de compression, car aucune réduction de taille n'est effectuée, au contraire (voir ci-dessous), mais bien d'une méthode de réorganisation des données : les probabilités pour que des caractères identiques initialement éloignés les uns des autres se retrouvent côte à côte sont alors augmentées. Cette technique n'est pas très utilisée, mais l'on peut cependant remarquer qu'elle est présente dans le format bzip2 qui est actuellement l'un des formats offrant un des meilleurs taux de compression.
- La trasformata di Burrows-Wheeler (abbreviata con BWT) è un algoritmo usato nei programmi di compressione dati come bzip2. È stata inventata da Michael Burrows e David Wheeler. Quando una stringa di caratteri viene sottoposta alla BWT, nessuno di questi cambia di valore perché la trasformazione permuta soltanto l'ordine dei caratteri. Se la stringa originale contiene molte ripetizioni di certe sottostringhe, allora nella stringa trasformata troveremo diversi punti in cui lo stesso carattere si ripete tante volte. Ciò è utile per la compressione perché diventa facile comprimere una stringa in cui compaiono lunghe sequenze di caratteri tutti uguali. Per esempio, la stringa: TRENTATRE. TRENTINI. ANDARONO.A. TRENTO. TUTTI.E. TRENTATRE. TROTTERELLANDO verrebbe trasformata nella seguente: OIIEEAEO.. LDTTNN. RRRRRRRTNTTLEAAIOEEEENTRDRTTETTTTATNNTTNNAAO.... OU.T
- ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) とは、1994年にマイケル・バローズ (Michael Burrows) とデビッド・ホイーラー (David Wheeler) によって開発された可逆変換の一種で、主にデータ圧縮の前処理として用いられる。 単にブロックソートを施しただけではデータの大きさはほぼ不変であるが、データが整列されて圧縮され易くなる。 通常はMove To Front (MTF)、連長圧縮 (RLE)、エントロピー符号との組み合わせてデータ圧縮に応用される。 ブロックソートを用いた圧縮プログラムの実装としてはUNIXで主に用いられるbzip2がある。
- De Burrows-Wheelertransformatie (hieronder ook afgekort als BWT) is een transformatie van een tekenreeks naar een vorm waarin deze gemakkelijker te comprimeren is. De bekendste toepassing van de Burrows-Wheelertransformatie is het programma bzip2. De Burrows-Wheelertransformatie verandert de volgorde van de tekens in een tekenreeks, de tekens zelf blijven ongewijzigd. Na de BWT zullen veel tekens aaneengesloten naast elkaar zitten, zodat bijvoorbeeld het RLE-algoritme beter toegepast kan worden. Om een goede compressie te bereiken, moet de tekenreeks minimaal enkele kilobytes omvatten. De Burrows-Wheelertransformatie werd uitgevonden in 1983 door David Wheeler en gepubliceerd door M. Burrows en David Wheeler in 1994.
- Transformata Burrowsa-Wheelera to algorytm użyteczny przy bezstratnej kompresji danych. Dane po przetworzeniu tą transformacją dają się znacznie lepiej skompresować za pomocą klasycznych algorytmów kompresji. Operuje ona na blokach, przy czym jest tym efektywniejsza im bloki te są większe. Zazwyczaj używa się bloków o rozmiarach kilkuset kilobajtów. Transformata Burrowsa-Wheelera jest podstawą algorytmu BZIP2. Dla potrzeb kompresji, zwykle po transformacie Burrowsa-Wheelera używa się algorytmu Move To Front, po czym kompresuje się jakąś metodą kompresji bezstratnej, np. algorytmem Huffmana.
- O Método de Burrows-Wheeler, também conhecido pela sigla em inglês BWT, é um processamento estatístico de um bloco de dados que aumenta a redundância espacial, facilitando a aplicação de técnicas de compressão de dados. Diferentemente de outras técnicas usadas par a compressão de dados que trabalham com um fluxo contínuo de bytes tratados um a um, o método de Burrows-Wheeler trabalha com blocos geralmente grandes de dados que são processados em conjunto antes de serem comprimidos.
- викифицироватьПреобразование Барроуза — Уилера (Burrows-Wheeler transform, BWT, также исторически называется блочно-сортирующим сжатием, хотя сжатием и не является) — это алгоритм, используемый в техниках сжатия данных для преобразования исходных данных. BWT используется в архиваторе bzip2. Алгоритм был изобретён Майклом Барроузом и Дэвидом Уилером. Термином BWT также называют и полные алгоритмы сжатия, использующие BWT как один из шагов.
|
| rdfs:comment
|
- The Burrows–Wheeler transform (BWT, also called block-sorting compression), is an algorithm used in data compression techniques such as bzip2. It was invented by Michael Burrows and David Wheeler in 1994 while working at DEC Systems Research Center in Palo Alto, California. It is based on a previously unpublished transformation discovered by Wheeler in 1983. When a character string is transformed by the BWT, none of its characters change value.
- Die Burrows-Wheeler-Transformation (BWT) ist ein Algorithmus, der in Datenkompressionstechniken wie bzip2 Anwendung findet, dabei allerdings selbst keine Datenkompression durchführt. Er wurde von Michael Burrows und David Wheeler entwickelt.
- Burrows-Wheelerova transformace, anglicky Burrows-Wheeler transform (BWT) je pomocný algoritmus používaný v technikách komprese dat. Transformaci objevili Michael Burrows a David Wheeler. Samotná transformace data nijak nekomprimuje. Způsobí pouze změnu pořadí symbolů. V případě, že vstupní řetězec symbolů má několik podřetězců, které se v něm vyskytují vícekrát, bude mít výstupní řetězec několik míst, kde se vyskytuje stejný symbol několikrát za sebou.
- La transformée de Burrows-Wheeler, couramment appelée BWT (pour Burrows-Wheeler Transform) est une technique utilisée en compression de données. Elle fut inventée par Michael Burrows et David Wheeler. Cette technique fut rendue publique en 1994, à la suite de travaux précédents de Wheeler en 1983.
- La trasformata di Burrows-Wheeler (abbreviata con BWT) è un algoritmo usato nei programmi di compressione dati come bzip2. È stata inventata da Michael Burrows e David Wheeler. Quando una stringa di caratteri viene sottoposta alla BWT, nessuno di questi cambia di valore perché la trasformazione permuta soltanto l'ordine dei caratteri.
- De Burrows-Wheelertransformatie (hieronder ook afgekort als BWT) is een transformatie van een tekenreeks naar een vorm waarin deze gemakkelijker te comprimeren is. De bekendste toepassing van de Burrows-Wheelertransformatie is het programma bzip2. De Burrows-Wheelertransformatie verandert de volgorde van de tekens in een tekenreeks, de tekens zelf blijven ongewijzigd.
- Transformata Burrowsa-Wheelera to algorytm użyteczny przy bezstratnej kompresji danych. Dane po przetworzeniu tą transformacją dają się znacznie lepiej skompresować za pomocą klasycznych algorytmów kompresji. Operuje ona na blokach, przy czym jest tym efektywniejsza im bloki te są większe. Zazwyczaj używa się bloków o rozmiarach kilkuset kilobajtów. Transformata Burrowsa-Wheelera jest podstawą algorytmu BZIP2.
- O Método de Burrows-Wheeler, também conhecido pela sigla em inglês BWT, é um processamento estatístico de um bloco de dados que aumenta a redundância espacial, facilitando a aplicação de técnicas de compressão de dados. Diferentemente de outras técnicas usadas par a compressão de dados que trabalham com um fluxo contínuo de bytes tratados um a um, o método de Burrows-Wheeler trabalha com blocos geralmente grandes de dados que são processados em conjunto antes de serem comprimidos.
- викифицироватьПреобразование Барроуза — Уилера (Burrows-Wheeler transform, BWT, также исторически называется блочно-сортирующим сжатием, хотя сжатием и не является) — это алгоритм, используемый в техниках сжатия данных для преобразования исходных данных.
|
![[RDF Data]](/statics/sw-cube.png)
