Преглед садржаја:
- Дефиниција - Шта значи трансформација Бурровс-Вхеелер (БВТ)?
- Техопедија објашњава Бурров-Вхеелер Трансформ (БВТ)
Дефиниција - Шта значи трансформација Бурровс-Вхеелер (БВТ)?
Трансформација Бурровс-Вхеелер (БВТ) је алгоритам који узима блокове података, као што су жице и преуређује их у низове сличних карактера. Након трансформације, излазни блок садржи исте тачне елементе података пре него што је започео, али се разликује у редоследу. Природа алгоритма има тенденцију да сличне знакове поставља један поред другог, што резултирајући редослед података олакшава компримирање. Због тога се користи у многим алгоритмима компресије.
Техопедија објашњава Бурров-Вхеелер Трансформ (БВТ)
Алгоритам трансформације Бурровс-Вхеелер релативно је нови алгоритам који су 1994. године изумили Мицхаел Бурровс и Давид Вхеелер и заснован на необјављеној трансформацији коју је открио Вхеелер 1983. године, а објављеној у свом раду „Алгоритам компресије података без губитака по блоковима“.
Најосновније, БВТ узима блок података као што је низ, додаје ЕОФ знак и затим разврстава све ротације тог низа у лексикографски ред. Следећи псеудо код или кораци илуструју алгоритам:
- Направите табелу која садржи редове који представљају све могуће ротације низа у једном кораку.
- Поредајте све редове по абецеди.
- Изнесите последњу колону табеле.
На пример: реч „банана“; додавање ЕОФ карактера претвара га у „банана $“, а затим примењујемо алгоритам:
1. Направите табелу са редовима који представљају све могуће ротације:
банана $
анана $ б
нана $ ба
ана $ бан
на $ бана
$ банан
$ банана
2. Редове сортирајте абецедно / лексикографски на основу првог ступца:
$ банана
$ банан
ана $ бан
анана $ б
банана $
нана $ ба
на $ бана
3.Вратите последњу колону као БВТ излаз: аннб $ аа
Резултирајући низ је лакше компримовати јер се поновљени знакови спајају један поред другог. Али морају бити додатни подаци похрањени уз трансформисане податке да би се могла извршити обрнута трансформација. Иако су добијени трансформисани подаци већи од изворног облика, али се његова карактеристика стисљивости повећава вишеструко, што у суштини чини „бесплатном“ методом побољшања ефикасности метода компресије.
