libthai wordbreak revamp

หลังจากทำ double-array trie ตัวใหม่ ไปแล้วอาทิตย์ก่อน ก็กลับเข้าถ้ำอีกรอบ เพื่อลงมือยกเครื่องโค้ดตัดคำใน libthai ใหม่ จุดประสงค์ก็คือ ต้องการโค้ดที่สะอาดๆ และแยกพจนานุกรมออกจากโค้ด เพื่อให้ปรับแต่งได้อย่างอิสระ

แต่ต้องบอกว่า ปัญหาเรื่องตัดคำนี้ ผมเองไม่เคยสนใจมาก่อน และตอนที่ตั้งโครงการ libthai ก็คิดไว้ว่าจะชวนคนที่เคยคุยกันเรื่องแนวคิดของไลบรารีภาษาไทยอย่างพี่สัมพันธ์ หรือ อ. พฤษภ์ มาร่วม ก็พอดีว่าอ๊อทซึ่งร่วมตั้งโครงการด้วย ได้เสนอเอาโค้ดของ cttex ของพี่ฮุ้ยมาใช้ พร้อมทั้งอาสาลงมือทำเอง จนสามารถใช้การได้ และกลายเป็นส่วนที่มีประโยชน์ที่สุดของ libthai ในช่วงที่ผ่านมา ไม่ว่าจะเป็นการสนับสนุนการตัดคำใน Qt, Pango, Firefox และทำให้ libthai เป็นที่รู้จักมากขึ้น จนล่าสุดสามารถผลักดันเข้า Ubuntu และ Debian ได้ และการเป็นที่รู้จัก ก็ทำให้ได้ feedback เข้ามามากมาย โดยที่ได้ยินบ่อยที่สุดก็คือส่วนตัดคำนี่แหละ ซึ่งผมเองก็คิดเห็นเมือนเขาหลายอย่างเหมือนกัน และเขียนลง TODO list ไว้นานแล้ว ว่า "ยกเครื่องตัดคำใน libthai" แต่ก็ค้างคามาหลายปี จนเพิ่งมีเวลาว่างกลับมาดู

ด้วยความที่ไม่เคยคิดว่าจะทำมาก่อน ก็ต้องศึกษา paper ที่มีเสียก่อน ก็ไปรื้อกรุเอกสารเก่าที่เก็บไว้ ได้บทความของพี่สัมพันธ์มาอ่าน เอามาปะติดปะต่อกับแนวคิดของงานอื่นๆ ที่เคยได้ฟังมา แล้วก็ทดลองเขียนอยู่ 2-3 แบบ คิดเองเพิ่มเข้าไปบ้าง ทดลองไปมาจนคิดว่าได้แบบที่คิดว่าเหมาะที่สุดละ

เท้าความก่อนว่า การตัดคำไทยด้วยพจนานุกรม (ขอข้ามยุคการตัดคำด้วยกฎไป) สามารถวิเคราะห์ได้หลายระดับ ซึ่งทำให้ได้คุณภาพการตัดคำที่ต่างกัน เริ่มจากในระดับ lexical analysis ธรรมดาแบบ longest matching, การหา optimum แบบ maximal matching, การวิเคราะห์ไวยากรณ์เชิงสถิติด้วย n-gram, การวิเคราะห์ feature ด้วย machine learning อย่าง winnow (คล้ายๆ neural net แบบย่อมๆ) ไปจนถึงเทคนิค unsupervised learning ก็มีคนวิจัยกันมาแล้ว

สำหรับ libthai ที่เอาไว้ใช้ตัดบรรทัดหรือหาจุดหยุดเคอร์เซอร์ทีละคำแบบทันกาล (real-time) ในโปรแกรมประยุกต์ทั่วไป คงไม่ต้องการความถูกต้องแม่นยำมากขนาดที่จะใช้หลักสถิติหรือ machine learning แต่ขอให้ทำงานเร็วเข้าไว้ ผมจึงเริ่มจาก longest matching ตามบทความของพี่สัมพันธ์ก่อน แต่ก็คิดว่า เพื่อให้ได้ความถูกต้องเพิ่มขึ้น น่าจะลองขยับขึ้นมาที่ maximal matching ด้วย

บทความพี่สัมพันธ์ แม้จะเขียนไว้นานแล้ว (ป่านนี้พี่เขาอาจปรับปรุงแนวคิดไปไกลกว่านั้นมากแล้ว) แต่เป็นจุดเริ่มต้นที่ดี เพราะสรุปแนวคิดที่จำเป็นไว้ครบ คือการเดินด้วย trie, การ backtrack, การ recover จากบริเวณ error โดยเท่าที่ดูโค้ดเดิมของ libthai ก็จะเห็นเค้าของแนวคิดนี้ ซึ่งลักษณะการหาคำตอบจะเป็น longest matching

แต่เมื่อคิดต่อยอดเป็น maximal matching ก็จะเห็นอาการของ search problem ที่ต่างออกไป โดย longest matching จะเป็น depth-first search ถ้าจะปรับเป็นการหา optimum แบบ maximal matching (คือพยายาม match คำในพจนานุกรมให้มากที่สุด ซึ่งผลคือจะได้จำนวนคำน้อยที่สุด ต่างกับ longest matching ที่เป็นการพยายาม match คำปัจจุบันให้ยาวที่สุด โดยไม่ได้พิจารณาทั้งข้อความ ซึ่งอาจจะไม่ได้จำนวนคำน้อยที่สุด) ก็เพียงแต่วิ่งแบบ breadth-first เท่านั้น ซึ่งดูจะลงตัวมากๆ กับปัญหาการตัดคำ เพราะบริเวณกำกวมโดยปกติจะแบ่งเป็นช่วงๆ ทำให้ search graph มีการ merge เป็นช่วงๆ ไม่มี explosion เหมือน search problem ทั่วไป และสามารถตัดแนวคิดเรื่อง backtrack limit ที่แฝงใน depth-first search ตามบทความพี่สัมพันธ์ได้

ในอีกทางหนึ่ง ก็ไปคุยกับวีร์ที่ทำ textbreak framework เพื่อฟังแนวคิดด้วย แต่ทางนั้นเหมือนทำ framework ที่ล้วงลึกลงมาในกลไกการตัดคำ โดยตัดสินเลือกคำตอบด้วย shortest path ใน DAG (directed acyclic graph) เลยทีเดียว แต่โค้ดที่ผมเขียน ไม่ได้มีการสร้างกราฟจริงขนาดนั้น เป็นแต่จัดการ search pool และเก็บคำตอบที่ดีที่สุดขณะใดขณะหนึ่งเท่านั้น

เพื่อให้ครบ ก็ศึกษาโค้ด swath ของคุณไพศาล (TLWG version) ที่เป็นเครื่องมือตัดคำที่โอเพนซอร์สอีกตัวหนึ่งด้วย แต่ดูเหมือนว่าจะไม่ได้เน้น optimization สักเท่าไร คือพยายามสร้างการตัดคำที่เป็นไปได้ทั้งหมดก่อน แล้วเลือกคำตอบเอาตามกำหนด ว่าจะเป็น longest หรือ maximal matching ดูแล้ว น่าจะเป็นการพัฒนาเพื่อเปรียบเทียบนโยบายต่างๆ ของการตัดคำมากกว่า แต่ทั้งนี้ ยังไม่ได้ดูเวอร์ชันที่คุณไพศาลพัฒนาต่อเอง ซึ่งอาจมีการปรับปรุงไปมากกว่านี้แล้ว แต่โดยสรุปก็คือ คงไม่ใช้แนวคิดของ swath เช่นกัน

สรุปว่าได้ libthai word break ตัวใหม่ที่ตัดคำแบบ maximal matching อยู่ใน branch datrie_wbrk-branch ของ libthai CVS ตอนนี้พยายามทดสอบ-ปรับแก้อยู่ ไว้พร้อมเมื่อไรค่อย merge เข้า trunk เพื่อแทนที่โค้ดเดิม