Burrowsi-Wheeleri teisendus (BWT)

Kui sordid kõik teksti tsüklilised nihked, satuvad kõik sama sufiksiga nihked üksteise kõrvale. Viimane veerg — täht vahetult enne iga sorditud eesliidet — kogub kokku tähed, mis eelnesid algtekstis samale kontekstile. Korduvad mustrid tähendavad, et paljud nihked jagavad ühist sufiksit, mistõttu sama eelnev täht ilmub viimases veerus mitu korda järjest. Just neid kordusjadasid kasutavad ära RLE ja move-to-front kodeerimine. Teisendus on kadudeta, sest esimene veerg F (sorditud BWT) ja viimane veerg L (BWT ise) kodeerivad koos täieliku vastenduse — LF-vastenduse —, mis võimaldab algteksti taastada täht-tähe haaval ainult neist kahest veerust ja võtmest.

Iseenesest ei tee BWT teksti väiksemaks: väljund on täpselt sama pikk ja samade sümbolitega, ainult teises järjekorras. Tema tegelik ülesanne on olla pöörduv ettevalmistussamm, mis koondab ühesugused sümbolid kokku, nii et järgnevatel tihendajatel — move-to-front, jooksupikkuse kodeerimine ning seejärel Huffmani või aritmeetiline kodeerimine — on kerge. Point: võit pole mitte BWT väljundi suuruses, vaid selles, kui palju paremini tihendatavaks see väljund muutub.

Üks tihendamise idee sai vaikselt genoomika nurgakiviks. Struktuuri nimega FM-indeks sisse pakituna võimaldab BWT otsida lühikest DNA-fragmenti 3 miljardi tähega inimgenoomist, hoides seda genoomi vaid paaris gigabaidis. Joondajad nagu Bowtie ja BWA — Burrows-Wheeler Aligner — on sellele ehitatud, nii et 1994. aasta tihendamisnipp kannab tänapäeval miljonite sekveneerimislugemite igapäevast joondamist.