Abstrakt: | Burrows-Wheelerová transformácia slúži na bezstratovú transformáciu vstupného textu
do podoby, ktorá je ďalej schopná kompresie. Reverzibilná technika kompresie zvaná
tunelovanie je následne aplikovaná na Burrows-Wheelerovú transformáciu, čo vedie k
skomprimovanej Burrows-Wheelerovej transformácii, ktorá je aj naďalej bezstratovo
zvratná. Optimálne Tunelovanie je NP-ťažký problém. V našej práci predkladáme
novú metódu riešiacu tento problém v polynomiálnom čase, a to použitím celočíselného
lineárneho programovania.
|
---|