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

• ระหว่างอ่านงานวิจัยเพื่อปรับแต่งประสิทธิภาพ ได้รู้จักแนวคิดของ 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 ก็มีการนำมาพัฒนาอย่างจริงจังเช่นกัน
• การร่วมงานกับนักวิจัยและนักพัฒนาโอเพนซอร์สทำให้ค้นพบความเป็นไปได้อีกมาก
• มีแนวโน้มสูงว่าจะถูกใช้งานอย่างแพร่หลายมากขึ้นในสาขาวิทยาการคอมพิวเตอร์หลากหลายด้านในอนาคต

[qwqwhs]

โครงสร้างแบบบีบอัดที่ใช้ Wavelet ถูกนำมาใช้เป็นมาตรฐานใน Djvu ได้อย่างดี การบีบอัดภาพยอดเยี่ยมจริง ๆ

[GN⁺]

ความคิดเห็นใน 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