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 มาให้ทดลองใช้กัน

ThaiLaTeX Hyphenation

จากที่ได้ blog ครั้งล่าสุด เกี่ยวกับ ThaiLaTeX ผมก็ได้ออกรุ่นซอฟต์แวร์ทั้งหมดที่เกี่ยวข้องไปแล้วตั้งแต่กลางเดือนกุมภา คือ Fonts-TLWG 0.5.0 และ Fonts-SIPA-Arundina 0.2.0 ซึ่งได้เปลี่ยนชื่อโครงการด้วย แล้วก็ตามด้วย ThaiLaTeX 0.4.7 ในคราวเดียวกัน เผอิญว่าติดธุระส่วนตัวมากจนไม่สามารถหาเวลานั่งเขียน blog ได้

เกี่ยวกับการเปลี่ยนชื่อโครงการฟอนต์ทั้งสองนี้ ก็ด้วยเหตุว่ามีการเปลี่ยนชื่อที่ปลายน้ำหลายจุดไปในทางเดียวกัน ไม่ว่าจะเป็นที่ Debian หรือ CTAN โดยสำหรับ Debian นั้น กลุ่มผู้ดูแลแพกเกจฟอนต์ของ Debian ได้กำหนดวิธีการตั้งชื่อแพกเกจฟอนต์ใหม่ ซึ่งก็ได้รับแรงบันดาลใจมาจาก Fedora อีกต่อหนึ่ง ส่วนที่ CTAN นั้น เขาต้องการชื่อแพกเกจที่สอดคล้องกันกับชื่อ style file ที่ติดตั้ง และไดเรกทอรีที่ติดตั้ง ควรมีเอกภาพเป็นชื่อเดียว ซึ่งก็ได้เลือกชื่อ fonts-tlwg สำหรับโครงการ ThaiFonts-Scalable อีกอย่าง ตอนนี้ linux.thai.net ก็ได้โฮสต์โครงการฟอนต์หลายโครงการ การตั้งชื่อที่กว้างเกินไปอย่าง ThaiFonts-Scalable ย่อมไม่เหมาะสมอีกต่อไป จึงได้เปลี่ยนชื่อเป็น Fonts-TLWG และฟอนต์ชุด Arundina ก็เปลี่ยนเป็น Fonts-SIPA-Arundina ในทำนองเดียวกัน

หลังจากที่เสร็จงานชุดนั้นไป ผมก็ได้นำประเด็นเรื่อง hyphenation ที่ได้ คิดไว้ ขึ้นมาพิจารณา โดยหารือร่วมกับนักพัฒนาในการประชุมระดมสมองโอเพนซอร์สภาษาไทยที่พัทยา เมื่อกลับมาแล้วก็ตกลงใจว่าจะเริ่มเดินหน้าต่อเลย

แนวทางที่คุยกันไว้นั้น เป็นไปได้หลายวิธี:

• ทำ hyphenation pattern สำหรับ TeX โดยใช้ patgen
• ปรับ swath ให้แทรก soft hyphen (\- สำหรับ TeX) ด้วย

สำหรับทางเลือกแรกที่ทำ pattern สำหรับ TeX นั้น หากทำสำเร็จจะสามารถใช้กับโครงการอื่น เช่น FOP ของ Apache รวมถึง LibreOffice ด้วย

ผมเริ่มจากทางแรกก่อน โดยอาศัย word list ของ libthai มาแทรกยัติภังค์ที่จุดที่เป็นไปได้ แล้วป้อนเข้า patgen สร้างเป็น hyphenation pattern ออกมา แล้วติดตั้งลงใน TeX ปรากฏว่าผลที่ได้เป็นที่น่าพอใจพอสมควร ดังตัวอย่างเปรียบเทียบการจัดย่อหน้าโดยใช้และไม่ใช้ยัติภังค์:

จะเห็นว่าช่องไฟที่โบ๋ ๆ ลดน้อยลง และทำให้ย่อหน้ากระชับเข้ามาอีก เมื่อสังเกตจุดตัดบรรทัดก็จะพบว่า TeX คำนวณจุดแบ่งบรรทัดโดยมองภาพรวมทั้งย่อหน้า ไม่ใช่คำนวณทีละบรรทัด

นี่เป็นผลในขั้นแรก ซึ่งได้ commit เข้าใน trunk ของ SVN ของ thailatex แล้ว โดยที่ผมยืมค่าพารามิเตอร์สำหรับ patgen มาจาก วิทยานิพนธ์ชิ้นหนึ่ง โดยยังไม่ได้ปรับละเอียดเองตามข้อมูลที่มี ซึ่งตรงนี้คงหาเวลาทำในโอกาสต่อไป