ThaiLaTeX Hyphenation Fine-tuning

ที่ผมเล่าใน blog ที่แล้ว ถึงการทำ hyphenation pattern สำหรับ TeX โดยใช้ patgen และใช้ค่าพารามิเตอร์จาก วิทยานิพนธ์ของ David Antoš นั้น เป็นการทดลองแบบ black box โดยที่ยังไม่เข้าใจโครงสร้างภายในของ patgen แต่เป็น proof-of-concept อีกขั้นหนึ่งเท่านั้น

หลังจากนั้น ผมก็ได้ศึกษาหลักการของ patgen โดยอ่าน วิทยานิพนธ์ของ Franklin Mark Liang จนพอเข้าใจหลักการ จึงสามารถนำมาปรับวิธีสร้าง pattern ของเราได้

Liang ได้เล่าถึงอัลกอริทึมต่าง ๆ สำหรับทำ hyphenation ที่มีอยู่ ซึ่งส่วนใหญ่จะเป็นการใช้กฎของภาษาอังกฤษ แต่งานของเขามุ่งจะสร้าง matching pattern โดยอัตโนมัติจากตัวอย่างข้อมูลที่มีอยู่ ซึ่งจะเป็นวิธีที่ไม่ขึ้นกับภาษา สามารถนำไปใช้กับภาษาใด ๆ ก็ได้

pattern ที่สร้างจะอยู่ในรูป n-gram ของอักขระ พร้อมระบุจุดที่สามารถแทรกยัติภังค์ได้ โดย n-gram ที่ว่านี้จะมีความยาวเท่าไรก็ได้ ขึ้นอยู่กับความเฉพาะเจาะจงของตัว pattern

ตัว pattern จะนำไปสร้างเป็น trie ทำให้ match กับข้อความได้อย่างรวดเร็ว และได้จุดที่สามารถแทรก hyphen ได้ออกมา

Liang พยายามจะให้ pattern ที่ได้สามารถรับประกันได้ว่าจะแทรกยัติภังค์ได้ถูกต้องทั้งหมดสำหรับคำที่อยู่ในพจนานุกรม (ยกเว้นกรณีกำกวมอย่าง re-cord กับ rec-ord ซึ่งภาษาไทยน่าจะไม่มี) ส่วนคำที่ไม่อยู่ในพจนานุกรมก็ปล่อยให้เป็นเรื่องของการอนุมานเอาจากกฎ

วิธีหนึ่งที่เป็นไปได้คือเก็บทุกคำในพจนานุกรมลงใน trie เลย แต่นั่นจะทำให้ฐานข้อมูลใหญ่โดยใช่เหตุ แต่วิธีที่ Liang เสนอคือ ให้แยกกฎเป็นสองกลุ่ม คือกฎสำหรับระบุจุดแทรก กับกฎที่เป็นข้อยกเว้นซึ่งห้ามแทรก ด้วยวิธีนี้ทำให้กฎชุดแรกสามารถอยู่ในรูปอย่างง่ายโดยไม่จำเป็นต้องถูกต้องสมบูรณ์ก็ได้ แล้วกฎชุดถัดมาจะตัดส่วนที่ผิดพลาดออกไป

ทีนี้ ก็สามารถมองต่อไปได้อีก ว่ากฎชุดที่สองนี้ ก็สามารถแบ่งเป็นกฎที่ห้ามแทรก กับกฎที่เป็นข้อยกเว้นให้แทรกได้ ทำให้กฎชุดที่สองสามารถอยู่ในรูปอย่างง่ายได้อีกเช่นกัน โดยข้อยกเว้นจะช่วยเพิ่มความถูกต้องให้อีกที

แล้วก็มองอย่างนี้สลับกันไปเรื่อย ๆ ก็จะได้ว่า กฎชุดที่ 1 แทรกยัติภังค์ก่อน, กฎชุดที่ 2 ลบยัติภังค์ออกจากชุดที่ 1, กฎชุดที่ 3 แทรกยัติภังค์เพิ่มจากชุดที่ 2, กฎชุดที่ 4 ลบยัติภังค์ออกจากชุดที่ 3 ฯลฯ กล่าวคือ กฎในลำดับขั้นคี่จะเป็นกฎแทรกยัติภังค์ กฎลำดับขั้นคู่จะเป็นกฎห้ามแทรกยัติภังค์ โดยกฎจะเพิ่มความละเอียดขึ้นเรื่อย ๆ จนถึงขั้นสุดท้ายที่จะได้ผลลัพธ์ที่ถูกต้อง 100% สำหรับคำที่อยู่ในพจนานุกรม ซึ่งปรากฏว่าการจัดชุดกฎแบบนี้ช่วยลดจำนวน pattern ที่ต้องใช้ลงได้มาก โดยยังคงความถูกต้องสมบูรณ์อยู่เหมือนเดิม

ในการสร้างกฎแต่ละขั้น patgen จะสแกนพจนานุกรมที่เป็นตัวอย่างการแทรกยัติภังค์ เก็บ pattern ที่มีความยาวในช่วงที่กำหนด แล้วประเมิน pattern ว่าสามารถทำได้ถูกต้องกี่กรณี (คือค่า good) ผิดกี่กรณี (คือค่า bad) แล้วเอามาคูณกับ weight ที่กำหนดให้ (คือ good_weight และ bad_weight) หักลบส่วนที่ถูกด้วยส่วนที่ผิดแล้วเลือกเอาเฉพาะ pattern ที่เกิน threshold ที่กำหนด

กล่าวคือในการสร้าง pattern แต่ละขั้น patgen จะถามค่าต่อไปนี้:

• pat_start, pat_finish คือช่วงความยาว pattern ที่จะสร้าง
• good weight, bad weight, threshold คือน้ำหนักของความถูกต้องของกฎที่จะกรองมาใช้ good weight คือน้ำหนักด้านการพบจุดแทรกที่ถูกต้อง (ถ้ามาก คือต้องการให้ครอบคลุมจุดที่แทรกได้ให้มากที่สุดไว้ก่อน ผิดไม่เป็นไร), bad weight คือน้ำหนักด้านการพบจุดแทรกที่ไม่ใช่ (ถ้ามาก คือต้องการเฉพาะกฎที่ถูกต้องไว้ก่อน ไม่เน้นการครอบคลุมจุดที่แทรกได้), threshold คือขีดต่ำสุดของคะแนนประเมินที่จะเลือกเอา pattern ไว้

เพื่อช่วยในการออกแบบ pattern ชั้นต่าง ๆ patgen ก็จะประเมินในขั้นสุดท้ายให้ด้วย ว่ากฎเท่าที่สร้างมา เมื่อนำกลับไปใช้กับพจนานุกรม สามารถครอบคลุมจุดแทรก (good) ไปแล้วกี่เปอร์เซนต์, มีจุดแทรกผิด (Liang เรียกว่า bad แต่เพื่อไม่ให้สับสนกับ bad weight ในที่นี้ขอเรียกว่า error) กี่เปอร์เซ็นต์ และยังมีจุดแทรกที่ยังไม่ได้แทรก (missed) กี่เปอร์เซ็นต์ (missed = 100% - good)

จากการทดลองหลาย ๆ แบบ Liang เสนอว่าควรแบ่งกฎเป็น 5 ชั้น โดยมีหลักการดังนี้:

• ชั้นสุดท้าย ให้เป็นชั้นแทรก (เลขคี่) เก็บรายละเอียดที่เหลือทั้งหมด โดยก่อนมาถึงขั้นนี้ error ควรจะเหลือศูนย์ มีแต่จะเน้นแทรกจุดที่ยังไม่ครอบคลุมเท่านั้น กฎในขั้นนี้ควรมี bad weight เป็นอนันต์ (ในทางปฏิบัติคือให้เป็นค่าสูงมาก ๆ) เพื่อให้แทรกเฉพาะจุดที่ถูกต้องโดยไม่เกิด error อีก
• ชั้นรองสุดท้าย ให้เป็นชั้นกำจัดจุดแทรกผิด (เลขคู่) โดยเน้นกำจัดแหลก เพื่อให้ error เหลือศูนย์ตามที่ว่าไป ดังนั้นในขั้นนี้ควรมี threshold เป็น 1 (คือเป็นค่าน้อยที่สุด) เพื่อให้ทุกกฎได้ทำงาน และตัวกฎไม่จำเป็นต้องเน้นความถูกต้องมากนัก กล่าวคือ สามารถยอมให้กำจัดจุดที่ถูกอยู่แล้วได้ เพราะถึงอย่างไรชั้นสุดท้ายก็จะครอบคลุมที่เหลือให้ทั้งหมดอยู่แล้ว
• ชั้นก่อนสองชั้นนี้ หากมีแค่ชั้นเดียวก็จะเป็นการกดดันมากเกินไป จะกลายเป็นว่าต้องการกฎละเอียดจำนวนมาก แต่ถ้าแบ่งเป็น 3 ชั้น ค่อย ๆ เพิ่มความละเอียดมากขึ้น ก็จะทำให้ได้จำนวนกฎน้อยลง

ด้วยโครงร่างแบบนี้ จึงออกแบบกฎเป็นชั้น ๆ ดังนี้:

• ชั้นที่ 1 กฎสั้น, เน้น bad weight เล็กน้อย, threshold สูง เพื่อคุมจำนวนกฎ
• ชั้นที่ 2 กฎยาวขึ้น, เน้น good weight เล็กน้อย เพื่อเน้นลดจำนวน error ถึงแม้จะมีการกำจัด hyphen ที่ถูกออกบ้างก็ไม่เป็นไร ยังมีชั้นที่ 3 ช่วยเติมให้, threshold ลดหลั่นลงจากชั้นที่ 1 เพราะกรณีเหลือน้อยลง สามารถปล่อยกฎผ่านได้มากขึ้น
• ชั้นที่ 3 กฎยาวขึ้นอีก, เน้น bad weight กว่าชั้นที่ 1 ตามระดับความละเอียดของเนื้องาน, threshold ลดหลั่นลงจากชั้นที่ 2
• ชั้นที่ 4 (รองสุดท้าย) กฎยาวขึ้นอีก, good/bad weight สูสีกัน (แต่ good weight ควรมากกว่า bad weight คล้ายชั้นที่ 2), threshold ควรเป็น 1 (ค่าที่น้อยที่สุด) ตามที่อธิบายไปข้างต้น
• ชั้นที่ 5 (ชั้นสุดท้าย) กฎยาวขึ้นอีก, bad weight เป็นอนันต์ (ค่าสูง ๆ), threshold เป็น 1 เพื่อให้ทุกกฎทำงาน

Liang บอกว่าไม่มีทฤษฎีอะไรมากกว่านี้อีกแล้ว ที่เหลือต้องทดลอง ทดลอง และทดลอง เพื่อหาพารามิเตอร์ที่ดีที่สุดของข้อมูล ซึ่งผมก็ต้องทดลองปรับค่าต่าง ๆ ทีละนิด หนักเอาการอยู่ จนกระทั่งได้ค่าที่คิดว่าเหมาะที่สุดเท่าที่เจอมาสำหรับข้อมูลพจนานุกรม libthai ที่ใช้แล้ว คือ:

level	good wt.	bad wt.	thres.	pats added	% good	% errors
1	1	2	6	375	90.30	10.61
2	2	1	4	250	88.88	1.61
3	1	3	2	524	96.21	1.66
4	3	2	1	295	95.98	0.00
5	1	5	1	726	100.00	0.00
Total patterns				2170

เทียบกับพารามิเตอร์เดิมที่ใช้ ได้จำนวน pattern ทั้งหมด 3029 ก็ลดจำนวน pattern ลงมาได้ราว 28%

commit เข้า SVN ไปแล้วครับ คิดว่าอีกไม่นานคง release มาให้ทดลองใช้กัน