Burrows-wheeler transform (bwt) คืออะไร? - คำจำกัดความจาก techopedia

คำจำกัดความ - Burrows-Wheeler Transform (BWT) หมายถึงอะไร

การแปลง Burrows-Wheeler (BWT) เป็นอัลกอริธึมที่รับบล็อกของข้อมูลเช่นสตริงและจัดเรียงใหม่ในการทำงานของตัวละครที่คล้ายกัน หลังจากการแปลงบล็อกผลลัพธ์มีองค์ประกอบข้อมูลที่แน่นอนเหมือนกันก่อนที่จะเริ่ม แต่แตกต่างกันในการสั่งซื้อ ลักษณะของอัลกอริธึมมีแนวโน้มที่จะใส่อักขระที่คล้ายกันซึ่งทำให้ลำดับข้อมูลส่งผลให้บีบอัดได้ง่าย ดังนั้นมันถูกใช้ในอัลกอริธึมการบีบอัดมากมาย

Techopedia อธิบายการแปลง Burrows-Wheeler (BWT)

อัลกอริธึมการแปลง Burrows-Wheeler เป็นอัลกอริธึมที่คิดค้นขึ้นใหม่ในปี 1994 โดย Michael Burrows และ David Wheeler และขึ้นอยู่กับการเปลี่ยนแปลงที่ไม่ได้เผยแพร่ที่ค้นพบโดย Wheeler ในปี 1983 ตีพิมพ์ในกระดาษของพวกเขา

ในขั้นพื้นฐานที่สุด BWT รับบล็อกข้อมูลเช่นสตริงเพิ่มอักขระ EOF แล้วเรียงลำดับการหมุนทั้งหมดของสตริงนั้นลงในคำสั่งพจนานุกรม pseudocode หรือขั้นตอนต่อไปนี้แสดงให้เห็นถึงอัลกอริทึม:

1. สร้างตารางที่มีแถวที่แสดงถึงการหมุนเพิ่มขึ้นหนึ่งครั้งที่เป็นไปได้ทั้งหมดของสตริง
2. เรียงแถวทั้งหมดตามตัวอักษร
3. เอาท์พุทคอลัมน์สุดท้ายของตาราง

ตัวอย่างเช่น: คำว่า "Banana"; การเพิ่มตัวอักษร EOF จะเปลี่ยนเป็น“ Banana $” จากนั้นเราใช้อัลกอริทึม:

1. สร้างตารางที่มีแถวที่แสดงการหมุนที่เป็นไปได้ทั้งหมด:

กล้วย $

Anana $ ข

nana $ บริติชแอร์เวย์

ana $ ห้าม

na $ bana

A $ Banan

$ กล้วย

2. เรียงลำดับแถวตามตัวอักษร / พจนานุกรมตามคอลัมน์แรก:

$ กล้วย

A $ Banan

ana $ ห้าม

Anana $ ข

กล้วย $

nana $ บริติชแอร์เวย์

na $ bana

3. ส่งคืนคอลัมน์สุดท้ายเป็นเอาต์พุต BWT: annb $ aa

สตริงผลลัพธ์จะบีบอัดได้ง่ายกว่าเนื่องจากมีการทำซ้ำตัวอักขระซึ่งอยู่ติดกัน แต่ต้องมีข้อมูลเพิ่มเติมที่เก็บไว้กับข้อมูลที่ถูกแปลงเพื่อให้สามารถทำการแปลงกลับได้ แม้ว่าข้อมูลที่ได้จากการแปลงข้อมูลจะมีขนาดใหญ่กว่ารูปแบบดั้งเดิม แต่คุณสมบัติการบีบอัดของข้อมูลนั้นเพิ่มขึ้นหลายเท่า แต่โดยพื้นฐานแล้ววิธีการนี้ทำให้เป็น "ฟรี" ในการปรับปรุงประสิทธิภาพของวิธีการบีบอัด