Unicode datrie

จาก แผนงานครั้งที่แล้ว ที่ได้วางแผนปรับฟอร์แมตของแฟ้มและปรับ API ไปนั้น ตอนนี้ทำเสร็จไปแล้วใน CVS

ในครั้งนี้ ได้เพิ่มข้อมูล alphabet map ลงในแฟ้ม trie ด้วย จากเดิมที่แยกโค้ด Trie กับ SBTrie (single-byte-domain trie) ออกจากกัน โดย SBTrie เป็น wrapper สำหรับแปลงรหัสอักขระไบต์เดียว (TIS-620 หรือรหัส 8 บิตอื่น ๆ) ให้เป็นชุดอักขระที่เป็นโดเมนของ trie คือเป็นค่าลำดับ 1, 2, 3, ... ของแต่ละอักขระเป็นค่าต่อเนื่องกัน เพื่อจำกัดขนาดของโดเมน และเพิ่มความกระชับของ sparse table ที่แทน transition ของแต่ละ state โดยในครั้งนี้ ได้ตัดสินใจผนวก map นี้เข้าใน Trie เสียเลย และเขียนข้อมูลลงในแฟ้มไบนารีของ trie ด้วย เพื่อลดความสับสนของการแยกแฟ้ม *.sbm ใน datrie รุ่นก่อน

แต่ก็หมายความว่า แผนเดิมที่คิดจะทำ wrapper แยกระหว่างรหัสอักขระ 8 บิตกับยูนิโค้ด เช่น SBTrie, UniTrie, ... ก็กลายเป็นว่าต้องรองรับทุกอย่างในโค้ดเดียว จึงถือโอกาสเพิ่มแผนงานอีกอย่าง คือรองรับยูนิโค้ดไปเลย แล้วให้ client แปลงทุกอย่างให้เป็นยูนิโค้ดเอา หรือจะใช้รหัส 8 บิตตามเดิมแต่เก็บในเนื้อที่อักขระ 32 บิตแทนก็ตามแต่ เพราะไม่ว่าจะมาแบบไหน trie ก็จะแปลงเป็นโดเมนของ trie อยู่แล้ว ขอให้ใช้รหัสแบบเดียวกันทั้งตอนสร้าง trie และตอนสืบค้นเป็นอันใช้ได้

ขณะที่แก้ ๆ ไปนั้น กลายเป็นการแก้โค้ดขนานใหญ่ เพราะมีหลายประเด็นให้ทำพร้อมกัน โดยที่ไม่สามารถทดสอบโค้ดในระหว่างกลางได้เลย เพราะเป็นการแก้ API ไปด้วย จึงคอมไพล์ไม่ผ่านจนกว่าจะแก้เสร็จ

เพราะฉะนั้น จึงแยกแพตช์ที่จะ commit นั้นออกเป็นแพตช์ย่อย ๆ ทำทีละเรื่อง เพราะในโครงการซอฟต์แวร์ใด ๆ ก็ตาม:

อย่าทำทุกอย่างในแพตช์เดียว ให้แยกแพตช์เป็นเรื่อง ๆ ค่อย ๆ เปลี่ยนทีละขั้น

การค่อย ๆ เปลี่ยนทีละขั้นนี้ เปิดโอกาสให้ได้ทดสอบและแก้บั๊กทีละเรื่องได้ ช่วยลดโอกาสการเกิดบั๊ก และลดความซับซ้อนในการดีบั๊กได้

ก็เลย checkout CVS ออกมาอีกชุดหนึ่ง แล้วแยกร่างแพตช์ใหญ่นั้นมาทำทีละเรื่อง พร้อมทดสอบก่อน commit ทุกขั้น ขั้นที่ทำเพิ่มไปก็คือ:

• ผนวก alphabet map เข้าใน class Trie และตัด class SBTrie ออกไป (เขียนภาษาซีแต่เรียก class ซะงั้น เพราะแนวคิดในการออกแบบก็เป็นกึ่ง ๆ OOP อยู่แล้ว)
• ปรับ API เพื่อให้สามารถใช้ trie แบบไม่อ่าน-เขียนแฟ้มได้ด้วย โดยยังมีเมธอดให้อ่านเขียนแฟ้มได้ถ้าต้องการ

ขั้นต่อไปที่จะทำ ซึ่ง blog นี้จะบอกกล่าวไว้ก่อนสำหรับผู้ที่อาจจะนำ datrie ไปใช้ คือต่อไป datrie จะใช้อักขระขนาด 32 บิตแล้ว แต่ชุด alphabet ที่รองรับ ก็ยังคงจำกัดที่ไม่เกิน 255 ตัวอยู่ดี เพราะไม่มีประโยชน์ที่จะรองรับ alphabet ขนาดโต ๆ (เช่นภาษาจีน) เนื่องจาก transition table จะกว้างเกินเหตุ และทำให้แฟ้ม trie ใช้เนื้อที่อย่างไม่มีประสิทธิภาพ

ช่วงนี้ขอจดจ่อหน่อยนะครับ เรื่องอื่นขอพักไว้ก่อน