| dbo:abstract
|
- Burrowsova-Wheelerova transformace, anglicky Burrows-Wheeler transform (BWT) je pomocný algoritmus používaný v technikách komprese dat. Transformaci objevili a . Samotná transformace data nijak nekomprimuje. Způsobí pouze změnu pořadí symbolů (permutaci). 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 lexikograficky seřadí. Ze seřazené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. K transformaci se používá datová struktura sufixový strom, která umožňuje rychlé operace s řetězci. Tuto transformaci využívá například kompresní metoda bzip2. (cs)
- The Burrows–Wheeler transform (BWT, also called block-sorting compression) rearranges a character string into runs of similar characters. 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. More importantly, the transformation is reversible, without needing to store any additional data except the position of the first original character. The BWT is thus a "free" method of improving the efficiency of text compression algorithms, costing only some extra computation. The Burrows–Wheeler transform is an algorithm used to prepare data for use with data compression techniques such as bzip2. It was invented by Michael Burrows and David Wheeler in 1994 while Burrows was working at DEC Systems Research Center in Palo Alto, California. It is based on a previously unpublished transformation discovered by Wheeler in 1983. The algorithm can be implemented efficiently using a suffix array thus reaching linear time complexity. (en)
- Die Burrows-Wheeler-Transformation (BWT) ist ein Algorithmus, der in Datenkompressionstechniken wie bzip2 Anwendung findet, dabei allerdings selbst keine Datenkompression durchführt. Die Transformation wurde von Michael Burrows und David Wheeler 1994 am (SRC) in Palo Alto entwickelt und basiert auf einer nicht veröffentlichten Transformation von Wheeler aus dem Jahr 1983. (de)
- La transformación de Burrows–Wheeler (BWT del inglés Burrows–Wheeler transform, también conocida como compresión por ordenación de bloques), es un algoritmo usado en técnicas de compresión de datos como en bzip2. Fue inventado por Michael Burrows y David Wheeler en 1994 mientras trabajaban en el en Palo Alto, California. Se basa en una transformación previamente descubierta por Wheeler que no se encuentra publicada. Cuando se transforma una cadena de caracteres mediante la BWT, ninguno de sus caracteres cambia de valor. La transformación permuta el orden de los caracteres. Si la cadena original contiene muchas subcadenas que aparecen a menudo, entonces la cadena transformada contendrá múltiples posiciones en las que un mismo carácter esté repetido varias veces en una fila. Esto es útil para la compresión, ya que tiende a ser fácil comprimir una cadena que contiene secuencias de caracteres repetidos con técnicas como y run-length encoding. Por ejemplo: La salida es más fácil de comprimir ya que tiene muchos caracteres repetidos.De hecho, en la cadena transformada, aparece un total de seis secuencias de caracteres idénticos: XX,SS,PP,..,II,yIII, que juntos representan 13 de los 44 caracteres. (es)
- La transformée de Burrows-Wheeler, couramment désignée par le sigle BWT (pour anglais : Burrows-Wheeler Transform) est un prétraitement utilisé en compression de données. Inventée par Michael Burrows et David Wheeler, elle a été publiée en 1994, à la suite de travaux précédents de Wheeler en 1983. Il ne s'agit pas d'un algorithme de compression, car aucune réduction de taille n'est effectuée. Il s'agit d'une méthode de réorganisation des données : la probabilité que des caractères identiques initialement éloignés les uns des autres se retrouvent côte à côte dans le résultat est accrue. La technique est à la base de l'algorithme de compression bzip2 qui est actuellement l'un de ceux offrant un des meilleurs taux de compression. Elle est aussi très utilisée en génomique, par exemple pour les problèmes d'alignement de lectures courtes issues des nouvelles technologies de séquençage d'ADN (ou d'ARN) ou pour des problèmes de comptage de mots (détection de répétitions). (fr)
- La trasformata di Burrows-Wheeler (abbreviata con BWT) è un algoritmo usato nei programmi di compressione dati come bzip2. È stata inventata da 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 (it)
- 버로우즈-휠러 변환(BWT, Burrows-Wheeler transform) 또는 블록 정렬 알고리즘은 데이터 압축에 관련된 알고리즘으로, 1994년에 와 데이비드 휠러가 개발하였다. 버로우즈-휠러 변환은 직접적으로 압축을 수행하는 알고리즘은 아니며, 변환을 거친 데이터의 크기는 변하지 않는다. 하지만 원본 데이터에 중복되는 글자가 많이 있다면, 변환 과정을 거친 결과물에는 중복되는 글자가 비슷한 위치에 몰리게 된다. 버로우즈-휠러 변환은 이기 때문에 주로 실제 압축 알고리즘을 적용하기 전에 적용하는 경우가 많다. 이 알고리즘을 쓰는 대표적인 압축 포맷으로 bzip2가 있다. (ko)
- De Burrows-Wheelertransformatie 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. (nl)
- ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) は、1994年にマイケル・バローズ (Michael Burrows) とデビッド・ホイーラー (David Wheeler) が開発した可逆変換の方式で、データ圧縮の前処理に応用される。 ブロックソート自体はデータの大きさを変えない。しかし、データを整列することでデータ中に出現するパターンを、いくつかのよく知られている手法で圧縮し易いものにできる。後処理としてMove To Front (MTF)・連長圧縮 (RLE)・エントロピー符号と組み合わせて、データを圧縮する。 実装はbzip2等。 (ja)
- Transformata Burrowsa-Wheelera – 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ę dowolną metodą kompresji bezstratnej, np. algorytmem Huffmana. (pl)
- 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 para 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. (pt)
- Перетворення Берроуза-Вілера (англ. Burrows-Wheeler Transform, BWT) — метод перестановки символів у стрічці в іншу стрічку , таким чином, що із можна отримати початкову послідовність, але в той же час вона краще придатна для стиснення. Щоб знайти від стрічки довжиною слід згенерувати циклічних ротацій цієї стрічки, відсортувати їх у лексикографічному порядку і отримати нову стрічку з останніх символів цих ротацій. Якщо вихідна стрічка містить багато повторів (як, наприклад, природна мова або геноми живих організмів), то трансформована міститиме багато серій (послідовностей, в яких один і той же символ зустрічається кілька разів поспіль). Перетворення Берроуза-Вілера використовують для стиснення даних без втрат, зокрема воно є частиною алгоритму bzip2, а також для індексування. Наприклад, у біоінформатиці воно дозволяє скоротити витрати пам'яті під час картування фрагментів, отриманих шляхом секвенування ДНК, стосовно референсних геномів. Цей метод перетворення послідовностей запропонували у 1994 році і . (uk)
- Преобразование Барроуза — Уилера (Burrows-Wheeler transform, BWT, также исторически называется блочно-сортирующим сжатием, хотя сжатием и не является) — это алгоритм, используемый в техниках сжатия данных для преобразования исходных данных. BWT используется в архиваторе bzip2. Алгоритм был изобретён и . Термином BWT также называют и полные алгоритмы сжатия, использующие BWT как один из шагов. (ru)
- Burrows–Wheeler Transform（简称BWT，也称作块排序压缩），是一个被应用在数据压缩技术（如bzip2）中的算法。该算法于1994年被和在位于加利福尼亚州帕洛阿尔托的发明。它的基础是之前Wheeler在1983年发明的一种没有公开的转换方法。 当一个字符串用该算法转换时，算法只改变这个字符串中字符的顺序而并不改变其字符。如果原字符串有几个出现多次的子串，那么转换过的字符串上就会有一些连续重复的字符，这对压缩是很有用的。该方法能使得基于处理字符串中连续重复字符的技术（如MTF变换和游程编码）的编码更容易被压缩。 举个例子： 该算法的输出因为有更多的重复字符而更容易被压缩了。 (zh)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 32955 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:class
|
- preprocessing for lossless compression (en)
|
| dbp:data
| |
| dbp:name
|
- Burrows–Wheeler transform (en)
|
| dbp:space
| |
| dbp:time
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Die Burrows-Wheeler-Transformation (BWT) ist ein Algorithmus, der in Datenkompressionstechniken wie bzip2 Anwendung findet, dabei allerdings selbst keine Datenkompression durchführt. Die Transformation wurde von Michael Burrows und David Wheeler 1994 am (SRC) in Palo Alto entwickelt und basiert auf einer nicht veröffentlichten Transformation von Wheeler aus dem Jahr 1983. (de)
- 버로우즈-휠러 변환(BWT, Burrows-Wheeler transform) 또는 블록 정렬 알고리즘은 데이터 압축에 관련된 알고리즘으로, 1994년에 와 데이비드 휠러가 개발하였다. 버로우즈-휠러 변환은 직접적으로 압축을 수행하는 알고리즘은 아니며, 변환을 거친 데이터의 크기는 변하지 않는다. 하지만 원본 데이터에 중복되는 글자가 많이 있다면, 변환 과정을 거친 결과물에는 중복되는 글자가 비슷한 위치에 몰리게 된다. 버로우즈-휠러 변환은 이기 때문에 주로 실제 압축 알고리즘을 적용하기 전에 적용하는 경우가 많다. 이 알고리즘을 쓰는 대표적인 압축 포맷으로 bzip2가 있다. (ko)
- De Burrows-Wheelertransformatie 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. (nl)
- ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) は、1994年にマイケル・バローズ (Michael Burrows) とデビッド・ホイーラー (David Wheeler) が開発した可逆変換の方式で、データ圧縮の前処理に応用される。 ブロックソート自体はデータの大きさを変えない。しかし、データを整列することでデータ中に出現するパターンを、いくつかのよく知られている手法で圧縮し易いものにできる。後処理としてMove To Front (MTF)・連長圧縮 (RLE)・エントロピー符号と組み合わせて、データを圧縮する。 実装はbzip2等。 (ja)
- Transformata Burrowsa-Wheelera – 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ę dowolną metodą kompresji bezstratnej, np. algorytmem Huffmana. (pl)
- 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 para 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. (pt)
- Преобразование Барроуза — Уилера (Burrows-Wheeler transform, BWT, также исторически называется блочно-сортирующим сжатием, хотя сжатием и не является) — это алгоритм, используемый в техниках сжатия данных для преобразования исходных данных. BWT используется в архиваторе bzip2. Алгоритм был изобретён и . Термином BWT также называют и полные алгоритмы сжатия, использующие BWT как один из шагов. (ru)
- Burrows–Wheeler Transform（简称BWT，也称作块排序压缩），是一个被应用在数据压缩技术（如bzip2）中的算法。该算法于1994年被和在位于加利福尼亚州帕洛阿尔托的发明。它的基础是之前Wheeler在1983年发明的一种没有公开的转换方法。 当一个字符串用该算法转换时，算法只改变这个字符串中字符的顺序而并不改变其字符。如果原字符串有几个出现多次的子串，那么转换过的字符串上就会有一些连续重复的字符，这对压缩是很有用的。该方法能使得基于处理字符串中连续重复字符的技术（如MTF变换和游程编码）的编码更容易被压缩。 举个例子： 该算法的输出因为有更多的重复字符而更容易被压缩了。 (zh)
- Burrowsova-Wheelerova transformace, anglicky Burrows-Wheeler transform (BWT) je pomocný algoritmus používaný v technikách komprese dat. Transformaci objevili a . Samotná transformace data nijak nekomprimuje. Způsobí pouze změnu pořadí symbolů (permutaci). 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). (cs)
- The Burrows–Wheeler transform (BWT, also called block-sorting compression) rearranges a character string into runs of similar characters. 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. More importantly, the transformation is reversible, without needing to store any additional data except the position of the first original character. The BWT is thus a "free" method of improving the efficiency of text compression algorithms, costing only some extra computation. The Burrows–Wheeler transform is an algorithm used to prepare data for use with data compression techniques such as bzip2. It was invented by Michael Burrows and David Wheeler in 1994 while Burrow (en)
- La transformación de Burrows–Wheeler (BWT del inglés Burrows–Wheeler transform, también conocida como compresión por ordenación de bloques), es un algoritmo usado en técnicas de compresión de datos como en bzip2. Fue inventado por Michael Burrows y David Wheeler en 1994 mientras trabajaban en el en Palo Alto, California. Se basa en una transformación previamente descubierta por Wheeler que no se encuentra publicada. Por ejemplo: XX,SS,PP,..,II,yIII, que juntos representan 13 de los 44 caracteres. (es)
- La transformée de Burrows-Wheeler, couramment désignée par le sigle BWT (pour anglais : Burrows-Wheeler Transform) est un prétraitement utilisé en compression de données. Inventée par Michael Burrows et David Wheeler, elle a été publiée en 1994, à la suite de travaux précédents de Wheeler en 1983. Il ne s'agit pas d'un algorithme de compression, car aucune réduction de taille n'est effectuée. Il s'agit d'une méthode de réorganisation des données : la probabilité que des caractères identiques initialement éloignés les uns des autres se retrouvent côte à côte dans le résultat est accrue. (fr)
- La trasformata di Burrows-Wheeler (abbreviata con BWT) è un algoritmo usato nei programmi di compressione dati come bzip2. È stata inventata da 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. (it)
- Перетворення Берроуза-Вілера (англ. Burrows-Wheeler Transform, BWT) — метод перестановки символів у стрічці в іншу стрічку , таким чином, що із можна отримати початкову послідовність, але в той же час вона краще придатна для стиснення. (uk)
|
| rdfs:label
|
- Burrows–Wheeler transform (en)
- Burrowsova–Wheelerova transformace (cs)
- Burrows-Wheeler-Transformation (de)
- Compresión de Burrows-Wheeler (es)
- Transformée de Burrows-Wheeler (fr)
- Trasformata di Burrows-Wheeler (it)
- 버로우즈-휠러 변환 (ko)
- ブロックソート (ja)
- Burrows-Wheelertransformatie (nl)
- Transformata Burrowsa-Wheelera (pl)
- Método de Burrows-Wheeler (pt)
- Преобразование Барроуза — Уилера (ru)
- Burrows-Wheeler变换 (zh)
- Перетворення Берроуза-Вілера (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
