โครงสร้างข้อมูลแบบย่อส่วน (Succinct)

 (blog.startifact.com)
20 คะแนน โดย GN⁺ 2025-03-07 | 2 ความคิดเห็น | แชร์ทาง WhatsApp
  • ระหว่างอ่านงานวิจัยเพื่อปรับแต่งประสิทธิภาพ ได้รู้จักแนวคิดของ Succinct Data Structures (โครงสร้างข้อมูลแบบย่อส่วน) เป็นครั้งแรก
  • ระหว่างค้นหางานวิจัยที่เกี่ยวข้อง ก็ได้ติดต่อพูดคุยโดยตรงกับศาสตราจารย์ Gonzalo Navarro นักวิจัยผู้มีชื่อเสียง
  • จึงเริ่มสงสัยว่าทำไมโครงสร้างข้อมูลลักษณะนี้จึงยังไม่ถูกใช้อย่างแพร่หลาย ต่างจากอาร์เรย์ แฮชแมป หรือต้นไม้แบบเดิม
  • บทความนี้จึงต้องการอธิบายเรื่องนี้แบบสั้น ๆ

ภาพรวมของ Succinct Data Structures

  • คล้ายกับการบีบอัดข้อมูลทั่วไป คือ เก็บข้อมูลในรูปแบบบีบอัด แต่ยังสามารถนำไปใช้งานได้โดยตรงแม้อยู่ในสภาพที่บีบอัด
  • ความต่างจากวิธีบีบอัดแบบเดิม: สามารถเข้าถึงและจัดการข้อมูลได้ โดยไม่ต้องคลายการบีบอัด
  • เป็นสาขาที่มีการวิจัยอย่างคึกคักมาตลอด 25 ปีที่ผ่านมา

การใช้งานใน Rust

  • ใน การเขียนโปรแกรมระบบ ประสิทธิภาพและการใช้หน่วยความจำมีความสำคัญมาก จึงมีโอกาสสูงที่โครงสร้างข้อมูลลักษณะนี้จะมีประโยชน์
  • งานวิจัยเดิมส่วนใหญ่ทำใน C++ แต่ก็เริ่มมีการค้นหาและพัฒนา implementation ใน Rust มากขึ้น
  • ขอแนะนำไลบรารีที่น่าจะเป็นประโยชน์สำหรับนักพัฒนา Rust

Bit Vectors (บิตเวกเตอร์)

  • ตัวอย่างอาร์เรย์บิต: [0, 1, 0, 1, 1, 0, 1, 0]
  • ในระบบ 64 บิต สามารถเก็บบิต 64 ตัวไว้ในจำนวนเต็มตัวเดียวได้ จึงช่วยประหยัดพื้นที่
  • ตัวบิตเวกเตอร์เองยังไม่ใช่โครงสร้างแบบ succinct แต่มี วิธีนำไปใช้ให้เกิดประสิทธิภาพสูง

Rank/Select Bit Vector

  • การดำเนินการ Rank: คำนวณว่าก่อนถึงดัชนีที่กำหนด มีค่า 1 ปรากฏกี่ครั้ง
    • ตัวอย่าง: rank(3) → 2
  • การดำเนินการ Select: คืนค่าตำแหน่งที่ 1 ตัวที่กำหนดปรากฏ
    • ตัวอย่าง: select(2) → 3
  • ทำงานได้ใน ความซับซ้อนเวลา O(1)
  • มี memory overhead ต่ำ และมีประโยชน์เมื่อจัดการกับสตริงขนาดใหญ่
  • กรณีการใช้งาน
    • มีประโยชน์เมื่อเก็บสตริงขนาดใหญ่โดยแยกเป็นหน่วยสตริงย่อยขนาดเล็ก
    • สามารถค้นหาได้อย่างมีประสิทธิภาพว่าดัชนีหนึ่ง ๆ อยู่ในสตริงย่อยส่วนใด
    • ใช้ วิธีจัดเก็บแบบบีบอัด เพื่อลดการใช้หน่วยความจำ พร้อมทั้งยังค้นหาได้รวดเร็ว
  • ไลบรารี Rust
    • vers: ให้ประสิทธิภาพสูงและมี overhead ต่ำมาก
    • sucds: รองรับ implementation แบบ sparse เช่น SArray
    • vers เด่นด้าน การสร้างโครงสร้างข้อมูลอย่างมีประสิทธิภาพ และมีแผนจะรองรับ implementation แบบ sparse ในอนาคต

Wavelet Matrix (เวฟเล็ตเมทริกซ์)

  • ขยายแนวคิด Rank/Select ไปสู่ ข้อมูลที่มี alphabet ขนาดใหญ่กว่า
  • ตัวอย่าง: การวิเคราะห์ลำดับ DNA (A, C, G, T) หรือ การค้นหาข้อความ (อักขระ UTF-8, สัญลักษณ์ 256 แบบ)
  • ทำงานโดยอาศัย Rank/Select bit vector เป็นพื้นฐาน
  • ไลบรารี Rust
    • vers มี implementation ของเวฟเล็ตเมทริกซ์รวมอยู่ด้วย

FM-Index (ดัชนีสตริงแบบบีบอัด)

  • รองรับ การค้นหา ไปพร้อมกับการจัดเก็บข้อมูลข้อความจำนวนมากในรูปแบบบีบอัด
  • ฟังก์ชันหลัก:
    • count(pattern): คำนวณว่ามีแพตเทิร์น (สตริง) ที่กำหนดปรากฏกี่ครั้ง
    • locate(pattern): คืนค่า ดัชนีทั้งหมด ที่แพตเทิร์นนั้นปรากฏ
  • มีประโยชน์กับ การค้นหาลำดับ DNA และ การค้นหาข้อความขนาดใหญ่
  • ไลบรารี Rust
    • ใช้งานไลบรารี fm-index ได้
    • เดิมใช้ fid แต่หลังย้ายไป vers แล้วประสิทธิภาพดีขึ้น

Balanced Parentheses (การแทนวงเล็บแบบสมดุล)

  • บีบอัดการเก็บโครงสร้างต้นไม้ให้เหลือระดับ 2 บิตต่อโหนด
  • ตัวอย่างต้นไม้:
   a  
 /   \\  
b     c
  • สามารถแทนได้ในรูป (()())
  • และแปลงเป็น 1 (วงเล็บเปิด) กับ 0 (วงเล็บปิด) ได้เป็น 110100
  • ใช้การดำเนินการ Rank/Select เพื่อ ปรับปรุงประสิทธิภาพของการนำทางภายในต้นไม้
  • ไลบรารี Rust
    • กำลังพัฒนาอยู่ในสาขา dev-bp ของ vers

การประยุกต์ใช้: การจัดเก็บและประมวลผล XML

  • สามารถเก็บ XML โดยใช้ การแทนวงเล็บแบบสมดุล
  • ใช้ Rank/Select bit vector เพื่อจัดการ XML tag (p, div เป็นต้น) ได้อย่างมีประสิทธิภาพ
  • ใช้ FM-Index เพื่อ เพิ่มประสิทธิภาพการค้นหาข้อความ

บทสรุป

  • โครงสร้างข้อมูลแบบ succinct มอบทั้ง การใช้หน่วยความจำต่ำ และ การประมวลผลที่รวดเร็ว ไปพร้อมกัน
  • แม้จะมีงานวิจัยใน C++ มาก แต่ใน Rust ก็มีการนำมาพัฒนาอย่างจริงจังเช่นกัน
  • การร่วมงานกับนักวิจัยและนักพัฒนาโอเพนซอร์สทำให้ค้นพบความเป็นไปได้อีกมาก
  • มีแนวโน้มสูงว่าจะถูกใช้งานอย่างแพร่หลายมากขึ้นในสาขาวิทยาการคอมพิวเตอร์หลากหลายด้านในอนาคต

บทความที่เกี่ยวข้อง

2 ความคิดเห็น

 
qwqwhs 2025-03-09

โครงสร้างแบบบีบอัดที่ใช้ Wavelet ถูกนำมาใช้เป็นมาตรฐานใน Djvu ได้อย่างดี การบีบอัดภาพยอดเยี่ยมจริง ๆ
 
GN⁺ 2025-03-07
ความคิดเห็นใน Hacker News

  • ฉันส่งอีเมลไปถาม Gonzalo Navarro และผลลัพธ์คือได้ร่วมเขียนบทความวิจัยกับเขา

    • งานวิจัยอีกชิ้นของเขาว่าด้วยการทำ implementation ของ bitvector rank/select แบบเรียบง่าย โดยผสานแนวคิดที่สง่างามหลายอย่างเข้าด้วยกัน
    • ช่วงนั้นฉันสนใจโครงสร้างข้อมูลแบบย่อมาก จึงเขียนไลบรารี Rust ที่ implement bitvector หลายประเภทและ wavelet matrix
    • ในมุมมองของการทำภาพข้อมูล ฉันสงสัยว่าโครงสร้างข้อมูลที่ใช้พื้นที่อย่างมีประสิทธิภาพจะช่วยยกระดับการสำรวจชุดข้อมูลขนาดใหญ่แบบโต้ตอบฝั่งไคลเอนต์ได้อย่างเป็นรากฐานหรือไม่

  • ฉันอยู่ในสายนี้มานานกว่า 30 ปีแล้ว แต่เพิ่งเคยได้ยินคำว่า "โครงสร้างข้อมูลแบบย่อ"

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

  • โครงสร้างข้อมูลแบบย่ออาจไม่ได้เร็วกว่าวิธีดั้งเดิม หากชุดข้อมูลยังพอดีกับหน่วยความจำ

    • แต่สำหรับชุดข้อมูลขนาดใหญ่ เวลาในการเข้าถึงสตอเรจจะกลายเป็นปัจจัยหลัก จึงทำให้โครงสร้างข้อมูลแบบย่อได้เปรียบ
    • ต้นไม้แบบย่อเหมือนงานศิลปะ

  • ฉันได้ยินแนวคิดเรื่องโครงสร้างข้อมูลแบบย่อครั้งแรกจาก Edward Kmett

    • เขาเป็นนักพัฒนาไลบรารี Haskell ชื่อดัง และเคยบรรยายเรื่องโครงสร้างข้อมูลแบบย่อไว้นานแล้ว

  • โครงสร้างข้อมูลแบบย่อนั้นสนุกมาก

    • ฉันเคย implement มันด้วย Zig และ implementation หลักคือฟังก์ชันแฮชสมบูรณ์แบบขั้นต่ำที่ใช้สมาชิกน้อยกว่า 4 บิต
    • การ implement อัลกอริทึมเหล่านี้ให้ความรู้สึกเหมือนเวทมนตร์

  • หนังสือของ Navarro เป็นงานสำรวจที่ยอดเยี่ยม

    • บทบรรยายของ Erik Demaine เกี่ยวกับโครงสร้างข้อมูลแบบย่อก็ยอดเยี่ยมเช่นกัน

  • ฉันใช้เวลาช่วงเช้าไปกับการศึกษาโครงสร้างข้อมูลแบบย่อ และประสิทธิภาพด้านหน่วยความจำนั้นน่าทึ่งมาก

    • ฉันกำลังใช้ RAM จำนวนมากในโปรเจ็กต์วิเคราะห์ไฟล์ XML ขนาดใหญ่
    • แนวคิดของ wavelet matrix ดูมีอนาคตสำหรับงานที่เน้นข้อความ

  • มีวิธีทำให้การแทนโหนดของโครงสร้างขนาดใหญ่ในหน่วยความจำมีประสิทธิภาพ

    • จัดสรรออฟเซ็ตให้ฟิลด์ที่ไม่ค่อยถูกใช้ และใช้ bitmask เพื่อระบุการมีอยู่ของฟิลด์
    • การ masking และ popcount ช่วยให้เข้าถึงได้รวดเร็ว

  • Marisa trie เป็นโครงสร้างข้อมูลแบบย่อที่ทั้งเจ๋งและมีประโยชน์มาก

    • มีการกล่าวถึงมันในหนังสือ High Performance Python ด้วย

  • ไลบรารีพื้นฐานของฉันสำหรับโครงสร้างข้อมูลแบบย่อคือ SDSL-Lite