แทนที่ฐานข้อมูล SQLite ขนาด 3GB ด้วยไบนารี FST (ตัวแปลงสถานะจำกัด) ขนาด 10MB

 (til.andrew-quinn.me)
1 คะแนน โดย GN⁺ 5 시간 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Taskusanakirja เป็นพจนานุกรมฟินแลนด์-อังกฤษที่รองรับการค้นหาแบบคำนำหน้าระหว่างพิมพ์
  • เมื่อขยายรูปผันภาษาฟินแลนด์ จำนวนรายการเพิ่มขึ้นเป็น 40–60 ล้านรายการ จน trie เริ่มถึงขีดจำกัด
  • วิธีแก้ชั่วคราวด้วย SQLite FTS ทำงานได้เร็ว แต่ต้องดาวน์โหลดครั้งแรกถึง 3GB
  • FST ที่สร้างด้วย Rust ย่อข้อมูลจาก SQLite ลงเหลือไบนารีราว 10MB ลดขนาดได้ประมาณ 300 เท่า
  • FST แชร์ทั้งคำนำหน้าและ คำลงท้าย จึงเหมาะกับรูปแบบการผันซ้ำ ๆ ได้ดี

โครงสร้างการค้นหาของ Taskusanakirja และข้อจำกัดในช่วงแรก

  • Taskusanakirja หรือย่อว่า tsk เป็น พจนานุกรมฟินแลนด์-อังกฤษ ที่มีฟังก์ชันค้นหาแบบค่อยเป็นค่อยไประหว่างพิมพ์
  • โดยพื้นฐานแล้วฟีเจอร์นี้คือปัญหา การค้นหาแบบคำนำหน้า และวิธีมาตรฐานสำหรับการค้นหาแบบคำนำหน้าเพื่อทำ autocomplete ก็คือการใช้ trie
  • เวอร์ชันแรกเขียนด้วย Go และเป้าหมายการออกแบบตั้งแต่ต้นคือแจกจ่ายทั้งโปรแกรมเป็น .exe เดียว, .app เดียว หรือไบนารีแบบ static link ไฟล์เดียว
  • เพื่อหลีกเลี่ยงการจับคู่รายการทั้งหมด ซึ่งบางครั้งอาจกินสัดส่วนเป็นเลขเปอร์เซ็นต์หลักเดียวของชุดคำระดับเลข 6 หลักกลาง ๆ ระบบจะคืนผลลัพธ์เพียง 50 หรือ 100 รายการแรก และทำ memoization สำหรับชุดอักขระยาว 1, 2, 3 ตัว
  • ด้วยวิธีนี้สามารถบรรจุ trie ที่ปรับแต่งพื้นฐานแล้วไว้ในพื้นที่ราว 60MB ได้ และแม้จะใช้งานส่วนตัวอย่างหนักเป็นเวลา 1 ปีก็ไม่รู้สึกถึงความหน่วง

ปัญหาด้านสเกลจากข้อมูลการผันภาษาฟินแลนด์

  • ภาษาฟินแลนด์เป็น ภาษาคำติดต่อ ดังนั้นคำพื้นฐานหนึ่งคำอาจมี ปัจจัยต่อท้ายเกิน 100 แบบ เมื่อคำนึงถึงทุกการผสม
  • การผสมเหล่านี้ไม่ได้เป็นระเบียบตรงไปตรงมา และระบบการเขียนภาษาฟินแลนด์ที่มีความเป็นระเบียบสูงก็มักถ่ายทอดรูปที่ผู้พูดใช้จริงลงในตัวเขียนโดยตรง ทำให้คำพื้นฐานเมื่อรวมกับปัจจัยต่อท้ายแล้วเกิดการยืด เลื่อน และแปรรูป
  • ผู้เรียนระดับต้นมักติดขัดกับคำบางคำในประโยคอย่าง “Opiskelijassammekin on leijonan sydän” และ tsk ตั้งใจจะบรรจุข้อมูลที่ช่วยแยกคำตามขอบเขตที่ถูกต้องด้วย
  • ในเชิงภาษาศาสตร์ การแปรรูปนี้เกี่ยวข้องกับ การสลับพยัญชนะ และ ความกลมกลืนของสระ ซึ่งภาษาฟินแลนด์ใช้ทั้งสองอย่างพร้อมกัน
  • ตัวอย่างเช่น katu แปลว่า “street” แต่รูปแสดงความเป็นเจ้าของไม่ใช่ katun แต่เป็น kadun เพราะ t อ่อนเสียงเป็น d เนื่องจากพยางค์ปิด
  • เมื่อนำโครงสร้างนี้ไปคูณกับ 15 การก, รูปพหูพจน์ 2 แบบ, ปัจจัยแสดงความเป็นเจ้าของ 6 แบบ และคำต่อพ่วงอีกจำนวนไม่แน่นอน trie แบบตรงไปตรงมาจะไม่สามารถเฉลี่ยต้นทุนของส่วนท้ายที่คำหลายพันคำใช้ร่วมกันอย่าง -ssa-mme-kin ได้
  • ราว 400,000 รายการ ยังพอเก็บไว้ใน trie ด้วย RAM ประมาณ 50MB ได้ แต่แนวทางเดียวกันไม่สามารถขยายไปถึง 40–60 ล้านรายการได้
  • วิธีแก้ชั่วคราวคือเก็บรูปผันไว้ในฐานข้อมูล SQLite FTS แยกต่างหากแล้วค้นหาเมื่อจำเป็น ซึ่งใช้งานได้โดยไม่รู้สึกหน่วง แต่ต้องดาวน์โหลดครั้งแรก 3GB

ผลลัพธ์หลังเปลี่ยนมาใช้ Rust และ FST

  • ผ่านไป 9 เดือน เมื่อกลับมาลองใหม่ด้วย Rust จึงเขียนโปรแกรม Rust ขนาดเล็กเพื่อดึงข้อมูลออกจากฐานข้อมูล SQLite ขนาด 3GB แล้วบีบอัดเป็น FST
  • แรงบันดาลใจมาจากบทความของ BurntSushi หรือ Andrew Gallant เรื่อง Index 1,600,000,000 Keys with Automata and Rust ซึ่งชี้ให้เห็นว่าเครื่องสถานะจำกัดสามารถแทนเซ็ตหรือแมปของสตริงที่เรียงลำดับแล้วให้มีขนาดเล็กและเร็วได้
  • ไบนารีที่ได้มีขนาดราว 10MB ทำให้ประหยัดพื้นที่ได้ประมาณ 300 เท่าเมื่อเทียบกับฐานข้อมูล SQLite ขนาด 3GB
  • กรณีใช้งานนี้ยังเหมาะอย่างยิ่งกับ fst crate เพราะเป็นปัญหาการแมปรูปผันและรูปการใช้งานของภาษาที่เป็นคำติดต่อสูงกลับไปยังคำนิยามดั้งเดิม
  • trie บีบอัดได้เฉพาะ คำนำหน้า แต่ FST บีบอัดได้ทั้งคำนำหน้าและ คำลงท้าย
  • ในคอร์ปัสพจนานุกรมภาษาฟินแลนด์มีคำลงท้ายยอดนิยมเพียงไม่กี่แบบที่ปรากฏซ้ำบ่อยมาก ดังนั้นการแชร์คำลงท้ายจึงให้ผลดีมาก
  • ข้อมูลนี้เป็น ข้อมูลคงที่ ที่ไม่เปลี่ยนระหว่างรัน จึงหลีกเลี่ยงจุดอ่อนที่ใหญ่ที่สุดของ fst ได้

เหตุผลที่ FST เล็กกว่า trie

  • หัวใจสำคัญที่ทำให้ FST เล็กกว่า trie มากในข้อมูลภาษาธรรมชาติคือ การแชร์คำลงท้าย
  • trie แชร์คำนำหน้า เช่น kadun กับ kaduille แชร์โหนด 3 ตัวแรกเหมือนกัน แต่เส้นทางคำลงท้ายที่ต่างกันจะยังถูกเก็บแยกกัน
  • ออโตมาตอนสถานะจำกัดเชิงกำหนดแบบไม่เป็นวัฏจักรชนิดมินิมัล จะรวมซับทรีสองชุดที่มีโครงสร้างเหมือนกันเข้าด้วยกัน
  • ในคอร์ปัสที่มีคำ 100,000 คำลงท้ายด้วยรูปแบบการผันราว 12 แบบเดียวกัน การรวมเช่นนี้จึงลดหน่วยความจำได้มาก
  • ฮิวริสติกหลักของกรณีนี้คือการแทนฐานข้อมูลอเนกประสงค์ที่ประกอบขึ้นเฉพาะหน้าด้วยโครงสร้างข้อมูลเฉพาะทางขนาดเล็กและคงที่ ซึ่งทำเฉพาะงานที่ต้องการจริง ๆ แล้วได้ การลดหน่วยความจำ 300 เท่า

บทบาทที่ยังเหลือของวิธี SQLite ชั่วคราวและขนาดการแจกจ่าย

  • การเลือก SQLite เมื่อ 9 เดือนก่อนเป็นผลจากการเลือก “ของที่แย่แต่ทำง่าย” แทน “ของที่ดีกว่าแต่ทำไม่ได้” และมันก็ใช้งานได้จริง
  • เพราะเข้าใจ B-tree ของ SQLite และ ส่วนขยาย Full Text Search อยู่แล้ว จึงเป็นทางแก้ที่ทดลองได้รวดเร็วในตอนนั้น
  • ส่วนขยาย FTS เดียวกันนี้ยังถูกใช้กับฟีเจอร์บางอย่างที่ใช้น้อยและยังไม่มีใน tsk v2.0.0 alpha แต่หากมันทำลาย memory footprint ปัจจุบัน ก็อาจถูกถอดออกทั้งหมด
  • เวอร์ชัน Pro ของ v2 ตั้งเป้าขนาดรวมทุกอย่างไว้ที่ประมาณ 20MB ซึ่งเล็กกว่าเวอร์ชันฟรี v1 ถึง 3 เท่า
  • เดิม tsk เริ่มจากโปรแกรม TUI ที่เขียนด้วย Go และพัฒนาต่อมาจากต้นแบบที่ใช้ fzf ชื่อ finstem โดยเชื่อมโยงกับบทความ the highest-ROI program I’ve written so far
  • taskusanakirja ในภาษาฟินแลนด์แปลว่า “pocket dictionary” และยังยึดเกณฑ์เดิมว่า ถ้ายังใส่ในแล็ปท็อปเก่าไม่ได้ มันก็ไม่ใช่พจนานุกรมพกพา แต่ใกล้เคียงพจนานุกรม Oxford ฉบับเก่าที่คอมไพล์ได้มากกว่า
  • มีแนวคิดซ้ำ ๆ ว่า “แก้ปัญหาเดิมสองครั้งก็ไม่เป็นไร” โดยมองว่าการลงมือสร้างล้อขึ้นใหม่เองบ้าง จะช่วยให้ไปแตะขอบเขตจริงได้เร็วกว่า การหยุดเพราะรู้สึกผิดว่าควรต้องไปหาวิธีที่ดีกว่าที่มีอยู่แล้ว
  • มุมมองนี้เชื่อมโยงกับ Caplanian view เรื่อง “การฝึกฝน” และ Do Ten Times as Much ที่ถูกเสนอเป็นคำแนะนำซึ่งแม้ชวนอึดอัดแต่ใช้ได้ผล

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

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

 
GN⁺ 5 시간 전
ความคิดเห็นจาก Lobste.rs

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

    • ประเด็นสำคัญที่เกี่ยวข้องในบทความคือ แม้แต่ การติดตั้งแบบ brute-force ที่ไม่มีประสิทธิภาพซึ่งทำด้วย SQLite DB ก็ยังมีคุณค่าในฐานะ implementation อ้างอิง
      เพราะอย่างน้อยมันมี implementation อ้างอิงที่ใช้งานได้ก่อนแล้ว จึงทำให้สร้าง implementation ที่มีประสิทธิภาพกว่ามาแทนได้ง่ายขึ้น
    • ตรงกับปัญหาที่ผมเจออยู่ตอนนี้เป๊ะ ผมอยากทำอะไรที่ปรับให้เหมาะกับ problem space ของตัวเอง แต่ก็หยุดอยู่เพราะรู้ว่าปัญหาแบบ generalized นั้นมีคนแก้ไปแล้ว
      แต่พอไปดูวิธีแก้ที่มีอยู่ ก็พบว่ามันมีภาระส่วนเกินที่ผมไม่ต้องการติดมาด้วยเยอะ จากประสบการณ์ ผมก็รู้ว่าไอเดียของตัวเองน่าจะคุ้มค่าที่จะลองดันต่อ แต่ก็อดคิดไม่ได้ว่าหรือผมกำลังพลาดอะไรอยู่ พอได้อ่านอันนี้แล้วก็ตัดสินใจว่าจะลองทำดูเลย อย่างน้อยถ้าล้มเหลวก็ยังได้เรียนรู้อะไรจากกระบวนการ

  • เจ๋งมาก ทำให้นึกถึง Compressing Icelandic name declension patterns into a 3.27 kB trie

  • ตอนทำบอต Scrabble ผมได้รู้จักโครงสร้างข้อมูลที่เกี่ยวข้องชื่อ DAWG (Directed Acyclic Word Graph) และดูเหมือนว่ามันจะค่อนข้างพบได้บ่อยในงานลักษณะนี้
    ความต่างหลักเมื่อเทียบกับ fst crate ดูจะเป็นตรงที่มันไม่ได้แมปแต่ละคำไปเป็นจำนวนเต็มที่ไม่ซ้ำกัน ผลลัพธ์ก็คล้ายกันคือขนาดเล็กลงมากและประสิทธิภาพดีขึ้นแบบมหาศาล บอต Scrabble โดยพื้นฐานต้องกรองทั้งพจนานุกรมเพื่อหาคำที่ตรงกับ regex ง่าย ๆ อย่าง ..cat.. แต่ในทางปฏิบัติคือต้องรองรับ regex ง่าย ๆ ทุกแบบที่เป็นไปได้จากกระดานปัจจุบัน งานที่เมื่อก่อนต้องรอประมาณ 1 นาที กลายเป็นเร็วเสียจนแทบไม่รู้สึกถึงความหน่วง

  • บทความที่ลิงก์ไว้ก็น่าอ่านเช่นกัน: https://burntsushi.net/transducers/

  • ท้ายที่สุด fst ก็กลายเป็นเครื่องมือที่ถูกใช้กับการรองรับภาษาเยอรมันของ srgn ด้วย หลังจากที่ Andrew แนะนำด้วยตัวเอง
    มันอยู่ใน problem space เดียวกัน คือการบีบอัด prefix และ suffix ที่ซ้ำกัน และมันทำงานได้ดีมาก อีกอย่างเพราะเป็นเครื่องมือ CLI ก็เลยต้องการ ต้นทุนการเริ่มต้นที่ต่ำที่สุด ด้วย ซึ่ง fst crate รองรับ การโหลดแบบ zero-copy จึงแทบไม่มี runtime overhead เลย โดย FST จะถูกสร้างขึ้นตั้งแต่ขั้นตอนคอมไพล์

  • เจ๋งจริง ๆ และอยากให้มีอะไรแบบนี้สำหรับ ภาษาเยอรมันกับภาษาอังกฤษ ด้วย คำประสมในภาษาเยอรมันยังทำให้ผมสับสนได้บ่อย ๆ