Double-Array Trie got KISSed

เข้าถ้ำมาอาทิตย์เศษ เพื่อเริ่มกระบวนการรื้อโค้ดตัดคำใน libthai (คิดว่าจะไม่มีโอกาสได้ทำซะแล้ว) โดยขั้นแรกคือการแยก dictionary ออกมาจากซอร์สโค้ด จึงเริ่มจากเขียน Double-Array Trie ขึ้นมาใหม่ หลังจากที่เคยเขียน midatrie (multi-index double-array trie) เป็น C++ ไว้ที่เนคเทค (LGPL-2.1) ก็เอามาเขียนใหม่เป็นภาษา C และพยายามใช้หลัก KISS (Keep it Simple, Stupid) เข้าไว้

เหตุที่เขียนใหม่ แทนที่จะทำ C wrapper ก็เพราะมีหลายประเด็น ที่เกิดขึ้นระหว่างวิจัยและพัฒนา midatrie ที่เห็นควรตัดทิ้ง ได้แก่:

• virtual memory: ในขณะที่เขียน midatrie นั้น หน่วยความจำในเครื่อง PC ขนาด 8 MB นี่ก็นับว่าหรูแล้ว ในขณะที่ฐานข้อมูลที่จะใช้มีขนาดใหญ่ จึงใช้วิธีอ่านเข้ามาทีละส่วนตามการใช้งาน ซึ่งสุดท้าย ก็ได้เป็นรูปแบบคล้ายๆ virtual memory ในระบบปฏิบัติการ ซึ่งผลก็คือ trie ที่ได้ จะทำงานช้ากว่าการโหลดเข้าหน่วยความจำเต็ม ซึ่งมีมากพอแล้วในสมัยนี้ อีกทั้งขอบเขตปัญหา ถ้าฐานข้อมูลไม่ได้ใหญ่ขนาด NLP ที่ซับซ้อน การโหลดเข้าหน่วยความจำก็ไม่ควรจะเปลืองเกินไป
• ส่วนขยายของ trie ที่มีการลดขั้นตอน เช่น ใน key ที่เป็น substring ของ key อื่น จากที่ paper ของ Aoe ชี้ไปหา tail ที่ว่างเปล่าแล้วเก็บข้อมูลในนั้น ในแล็บก็เกิดแนวคิดที่จะลัดขั้นตอน ด้วยการเก็บข้อมูลใน double-array เลย โดยไม่ต้องชี้ไปที่ tail ซึ่งผลก็คือ ทำให้เกิดกรณีพิเศษขึ้น จากเดิมที่มีแต่ boolean ว่าเดินได้หรือไม่ได้ ก็มีกรณีที่สามให้จัดการในที่ต่างๆ ซึ่งขยายวงไปถึงการออกแบบโครงสร้างโปรแกรมใหม่ ให้มีชนิดที่มาใช้แทน boolean อีกด้วย ซึ่งทั้งหมดนี้ เห็นว่าไม่คุ้มกับขั้นตอนเล็กๆ น้อยๆ ที่ประหยัดลงได้
• utility routine: เมื่อเขียนโค้ด C++ แบบไม่ใช้ STL ไปมากๆ เข้า (ในขณะนั้น มาตรฐาน ISO C++ ยังอยู่ระหว่างการร่าง และ STL หรือแม้แต่การสนับสนุน template ยังไม่ได้มีในคอมไพเลอร์ต่างๆ) ก็จะมี utility class เพิ่มเข้ามาเรื่อยๆ ทั้งที่ใช้ใน midatrie เอง และที่ใช้ในโปรแกรมอื่นในโครงการเดียวกัน การเปลี่ยนมาใช้โครงสร้างข้อมูลแบบ C ง่ายๆ ทำให้สามารถตัดโค้ดพวกนี้ออกไปได้ (libpenknife++ ก็ไม่ต้องใช้เลยด้วยซ้ำ!)

นอกจากนี้ ยังมีทางเลือกให้ตัดสินใจอีก คือกลุ่มของอาจารย์ Aoe ได้พัฒนาโครงสร้าง two-trie และ link trie เพิ่มเติม โดยเขียนเป็น paper อีกสองฉบับใน IEEE แต่หลังจากที่อ่านแล้ว link trie ใช้กับโครงสร้างข้อมูลที่มีความสัมพันธ์ระหว่างคำ ไม่เกี่ยวกับที่จะใช้ ส่วน two-trie (การใช้ prefix trie กับ suffix trie ประกอบกัน เพื่อใช้ trie ตัวที่สอง compress suffix) นั้น มีจุดบอดเกี่ยวกับการเชื่อมโยงระหว่าง prefix node กับ suffix node เพราะเมื่อโครงสร้าง double-array มีการ relocate เพื่อหาที่ว่างใหม่ จะทำให้ index ของ suffix node เปลี่ยน และ link ก็จะขาดไปเลย เป็นจุดบอดที่เคยพบและขบคิดเมื่อหลายปีก่อน จนกระทั่งตัดสินใจเขียนเมลไปปรึกษาอาจารย์ Aoe ก็ปรากฏว่า ท่านก็ยอมรับว่ามีปัญหา แล้วก็ได้ paper เกี่ยวกับ link trie มาอ่านแทน (เป็นฉบับร่าง ซึ่งวันก่อน vee ช่วยหาฉบับจริงมาให้อีกที) และมารอบนี้ ก็ลงมือคิดใหม่อีกครั้ง ก็ไม่พบวิธีแก้ที่ง่ายและไม่เสียเวลาวิ่งค้นเลย

สรุปว่ากลับมาที่โครงสร้าง double-array + tail อีกครั้ง ซึ่งน่าจะเหมาะเจาะที่สุดละ

นั่งเขียนไปทดสอบไป ตอนนี้ก็เริ่มทำงานได้ละ มีการเปลี่ยนฟอร์แมตของแฟ้มด้วย เพราะไม่ต้องใช้ virtual memory แล้ว ทำให้เรียงข้อมูลชิดกันได้เต็มที่ ประหยัดเนื้อที่ได้อีก

โค้ดอยู่ที่ TLWG CVS ชื่อมอดูลคือ software/datrie ก็อาจ check out ได้โดย:

 
  cvs -d :pserver:anonymous@linux.thai.net:/home/cvs     co software/datrie

ชอบความเรียบง่ายของภาษา C ด้วยแฮะ เทียบกับ C++ อาจจะใช้ภาษา C ต่อไปเรื่อยๆ :-)