Burrowsi-Wheeleri teisendus (BWT)

vaata, kuidas tsüklilised nihked sorditakse maatriksisse, mille viimane veerg koondab korduvad tähed — ja pööra see siis kadudeta tagasi

Algväärtused — Burrowsi-Wheeleri teisendus (BWT)

Sisendtekst	banana

Muuda ülal mõnda juhtelementi ja tulemused arvutatakse uuesti.

Interaktiivse simulatsiooni laadimine...

miks nihete sortimine tekitab kordusjadasid 🖖

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.

BWT paigutab ümber, ei kahanda 🖖

Üksi võttes ei muuda BWT teksti väiksemaks: väljund on täpselt sama pikk ja sisaldab samu märke, ainult teises järjekorras. Selle tegelik ülesanne on teksti pööratavalt ette valmistada, koondades ühesugused märgid lähestikku. Nii on järgnevatel tihendusmeetoditel, nagu ettepoole tõstmine, jadapikkuskodeerimine ning Huffmani või aritmeetiline kodeerimine, märksa lihtsam töö. Sõne „abracadabra$” väljundis on needsamad kaksteist märki; neli a-d paiknevad järjest, kuigi sisendis polnud kõrvuti ainsatki paari.

Sama nipp, mis kaardistab su DNA 🖖

Ü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.

Ülesanne täielikult lahendatud

"banana$" Burrowsi-Wheeleri teisendus kõigi seitsme sorteeritud pöördega 5 sammu
Leidke sõne "banana$" Burrowsi–Wheeleri teisendus ja otsustage seejärel, kas midagi on kokku pakitud. See on samm BWT väljund: lõpumärk lisatud, kõik seitse rotatsiooni sorteeritud, viimane veerg välja loetud.
1. Lõpumärk lisatakse enne kõike muud. Kuna $ sorteeritakse ettepoole igast tähest ja see esineb täpselt ühe korra, ei saa ükski kaks rotatsiooni osutuda võrdseks, seega on sorteerimisel üksainus ühene tulemus.
  
  $s = banana$ (n = 7), r_{k} = s [k :] + s [: k], k = 0, \dots, 6$
2. Rotatsioonide leksikograafiline sorteerimine on ainus töö, mida teisendus teeb. Seitset rida ülalt alla lugedes märkate, et sorteerimine on rühmitanud sõne selle järgi, mis tuleb iga positsiooni järel.
  
  $$banana, a$banan, ana$ban, anana$b, banana$, na$bana, nana$ba$
3. Rotatsiooni viimane märk on märk, mis seisab algses sõnes vahetult enne selle esimest märki. Seetõttu tekitabki sorteerimine sarju: read 1 ja 2 algavad mõlemad tähega 'a' ja lõpevad mõlemad tähega 'n', sest mõlemale nendest a-dest eelneb sõnas banana n. Võti on algse sõne reanumber ja ilma selleta ei saa teisendust tagasi pöörata.
  
  $L_{j} = s_{(k_{j} - 1) mod n} ⟹ L = annb$aa, key = 4$
4. Veel ei ole midagi kokku pakitud ja ei saanukski olla — väljund on sisendi permutatsioon, samad seitse märki teises järjekorras. Muutus vaid sarjade struktuur ja see ongi ainus asi, mis muutus.
  
  $b ∣ a ∣ n ∣ a ∣ n ∣ a ∣ $ : R = 7, \overset{r}{ˉ} = 1.00 ⟶ a ∣ nn ∣ b ∣ $ ∣ aa : R = 5, \overset{r}{ˉ} = \frac{7}{5} = 1.4$
5. RLE arvestab kaks baiti sarja kohta, seega viis sarja maksavad kümme baiti seitsmebaidise sisendi vastu. Selle tasuvuspiir ei muutu kunagi: sarjade arv peab olema alla poole pikkusest, mis siin tähendab kolme või vähemat.
  
  $2 R = 10 > N = 7 ⟹ \frac{7}{10} = 0.70 \times, 2 R < N ⟺ R < 3.5$
Vastus

Paneel kuvab annb$aa võtmega key = 4, keskmise sarja pikkusega 1,4 märki, 10 baiti RLE-d ja skooriga 0,70×. Teisendus tegi täpselt seda, mida lubab — see kasvatas keskmise sarja pikkust 40% ilma ühtegi märki puutumata — ja toru jäi ikka kahjumisse, sest seitse märki ei ole piisavalt tekstimahtu, et see võit kataks kaks baiti sarja kohta. Dubleerige sõna ja arvepidamine pöördub vastupidiseks. "bananabanana$" on kolmteist märki ja selle teisendus on annnnbba$aaaa: viie sarja asemel kuus sarja, samal ajal kui pikkus peaaegu dubleeriti, andes 12 baiti 13 vastu ja skoori 1,08×. See ongi kogu BWT mõte — sarjade arvu määrab see, kui palju erinevaid kontekste tekstis on, mitte selle pikkus, seega mida pikem on plokk, seda paremini see ära tasub, mis tõttu bzip2 teisendab kuni 900 kB pikkusi plokke, mitte sõnu.

$bananabanana$ : N = 13, R = 6 ⟹ 2 R = 12 < 13, \frac{13}{12} = 1.08 \times$

Õpitee

Käsitsi tihendamine

Allikad (3)

Insight blocks 1 and 2 — the transform itself: M. Burrows and D. J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm." Digital Systems Research Center, Research Report 124, 1994.
Insight block 3 — the aligners it turned into: B. Langmead, C. Trapnell, M. Pop and S. L. Salzberg, "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome." Genome Biology 10, R25, 2009.
And the one the block names outright: H. Li and R. Durbin, "Fast and accurate short read alignment with Burrows–Wheeler transform." Bioinformatics 25(14), 1754–1760, 2009.

42Mathi meeskond · Uuendatud 2026-08-17

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

banana - Sõnest „banana$” saab „annb$aa”: kolm a-d, mis enne polnud kordagi kõrvuti, paiknevad nüüd kahes rühmas ning jadade arv väheneb 7-lt 5-le.
mississippi - Sõnest „mississippi$” saab „ipssm$pissii”. See on klassikaline õpikunäide, kuid nii lühikese teksti korral jääb jadade arv endiselt 9-ks. Rühmitamisest hakkab kasu olema pikema teksti puhul.
abracadabra - Sõnest „abracadabra$” saab „ard$rcaaaabb”: neli a-d on järjest, kuigi algses sõnes polnud kaks a-d kordagi kõrvuti, ning jadade arv väheneb 12-lt 8-le. Siinse nelja näite seas koondab see ühesugused märgid kõige paremini.
DNA järjestus - Sõnest „AGATCAGA$” saab „AGC$GTAAA”: kolm A-d satuvad kõrvuti, kuigi algses sõnes polnud neist ükski kõrvuti. Genoomi puhul indekseerib FM-indeks just sellist teisendatud teksti.