Talaan ng mga Nilalaman:
- Kahulugan - Ano ang kahulugan ng Burrows-Wheeler Transform (BWT)?
- Ipinaliwanag ng Techopedia ang Burrows-Wheeler Transform (BWT)
Kahulugan - Ano ang kahulugan ng Burrows-Wheeler Transform (BWT)?
Ang Burrows-Wheeler transform (BWT) ay isang algorithm na kumukuha ng mga bloke ng data, tulad ng mga string, at muling ayusin ang mga ito sa mga nagpapatakbo ng mga katulad na character. Matapos ang pagbabago, ang output block ay naglalaman ng parehong eksaktong mga elemento ng data bago ito nagsimula, ngunit naiiba sa pag-order. Ang likas na katangian ng algorithm ay may posibilidad na maglagay ng magkatulad na character sa tabi ng bawat isa, na ginagawang mas madali ang nagresultang pagkakasunud-sunod ng data. Samakatuwid ginagamit ito sa maraming mga algorithm ng compression.
Ipinaliwanag ng Techopedia ang Burrows-Wheeler Transform (BWT)
Ang Burrows-Wheeler algorithm algorithm ay isang medyo bagong algorithm na naimbento noong 1994 nina Michael Burrows at David Wheeler at batay sa isang hindi nai-publish na pagbabagong natuklasan ni Wheeler noong 1983, na inilathala sa kanilang papel na "Isang Block-sorting Lossless Data Compression Algorithm."
Sa pinaka-pangunahing, ang BWT ay tumatagal ng isang bloke ng data tulad ng isang string, pagdaragdag ng isang EOF character at pagkatapos ay pag-uuri ng lahat ng mga pag-ikot ng string na iyon sa pagkakasunud-sunod ng lexicographic. Ang sumusunod na pseudocode o mga hakbang ay naglalarawan ng algorithm:
- Lumikha ng isang talahanayan na naglalaman ng mga hilera na kumakatawan sa lahat ng posibleng pag-ikot ng isang pagtaas ng string.
- Pagsunud-sunurin ayon ang lahat ng mga hilera.
- I-output ang huling haligi ng talahanayan.
Halimbawa: ang salitang "saging"; ang pagdaragdag ng isang EOF character ay lumiliko ito sa "banana $" pagkatapos ay inilalapat namin ang algorithm:
1. Gumawa ng isang talahanayan na may mga hilera na kumakatawan sa lahat ng posibleng pag-ikot:
saging $
anana $ b
nana $ ba
may $ ban
na $ bana
isang $ saging
$ saging
2. Pagbukud-bukurin ang mga hilera ayon sa alpabeto / lexicographically batay sa unang haligi:
$ saging
isang $ saging
may $ ban
anana $ b
saging $
nana $ ba
na $ bana
3.Balikin ang huling haligi bilang output ng BWT: annb $ aa
Ang nagresultang string ay mas madaling i-compress dahil ang paulit-ulit na mga character ay bunched up sa tabi ng bawat isa. Ngunit kailangang magkaroon ng karagdagang data na naka-imbak gamit ang nabagong data upang ang isang reverse transformation ay maaaring gawin. Kahit na ang nagresultang nabago na data ay mas malaki kaysa sa orihinal na anyo ngunit ang katangian ng compressability ay nadagdagan nang maraming beses, mahalagang gawin itong isang "libre" na pamamaraan ng pagpapabuti ng kahusayan ng mga pamamaraan ng compression.
