Theppitak's blog

My personal blog.

28 มีนาคม 2555

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

ป้ายกำกับ: ,

9 ความเห็น:

  • 25 พฤษภาคม 2555 17:37 , Blogger wd แถลง…

    ทำยังไงจะให้ xetex ใช้ libthai ตัดคำแทน icu
    (มึนงงกับ tex มาหลายวันแล้วครับ ;D)

     
  • 25 พฤษภาคม 2555 17:49 , Blogger Thep แถลง…

    ต้องแก้ source ของ xetex แล้วล่ะมั้งครับแบบนั้นน่ะ :P

     
  • 25 พฤษภาคม 2555 18:09 , Blogger wd แถลง…

    งั้นเอาใหม่ หากต้องการใช้ฟอนต์ Angsana New กับ Browallia New ทำหนังสือ บนเดเบียน
    รบกวนบอกทางไปต่อทีครับ

    เดิมเคยใช้ Word บนวินโดวส์ แต่มันจัด style ตามที่ต้องการไม่ได้ คือต้องการให้แต่ละ Section มีสืพื้นหลังแตกต่างกัน
    เลยลองหันมาทาง Tex ซึ่งต้องใช้ฟอนต์ทรูไทป์ดังกล่าว เลยต้องใช้ XeTex ครับ

    (แต่ Tex ก็มึนงงมาก มันไม่ตรงไปตรงมาเหมือน HTML+CSS)

     
  • 25 พฤษภาคม 2555 18:40 , Blogger Thep แถลง…

    เรื่องฟอนต์ thailatex สามารถใช้ฟอนต์ kinnari, garuda ได้ ไม่รู้แทนกันได้ไหมครับ?

    ส่วนเรื่องจัดสีพื้นหลังของ section... ต้องขอค้นดูก่อนครับ

     
  • 25 พฤษภาคม 2555 18:41 , Blogger Thep แถลง…

    สีพื้นหลังของ section หมายถึงเฉพาะ title หรือว่าเนื้อความทั้งหมดครับ?

     
  • 25 พฤษภาคม 2555 18:52 , Blogger wd แถลง…

    ต้องเรียกว่า subsection ใน tex ครับ
    (พระไตรปิฎกพื้นขาว อรรถกถาพื้นเทาอ่อน)

     
  • 25 พฤษภาคม 2555 18:54 , Blogger wd แถลง…

    ฟอนต์แทนไม่ได้ครับ

     
  • 25 พฤษภาคม 2555 20:32 , Blogger Thep แถลง…

    เรื่อง section มีสีพื้น ค้นเจอแพกเกจ mdframed ช่วยได้ครับ เช่น:

    \usepackage{xcolor}
    \usepackage{mdframed}

    % annotation section
    \newenvironment{annosec}[1]{\begin{section}{#1}}{\end{section}}
    \renewmdenv[backgroundcolor=gray]{annosec}

    ...

    \begin{section}{หมวดของพระไตรปิฎก}
    ...
    \end{section}

    \begin{annosec}{อรรถกถา}
    ...
    \end{annosec}

     
  • 25 พฤษภาคม 2555 20:33 , Blogger Thep แถลง…

    ปล. อย่าลืมลองคำสั่ง \textpali{...} ด้วยนะครับ ;-)

     

แสดงความเห็น (มีการกลั่นกรองสำหรับ blog ที่เก่ากว่า 14 วัน)

<< กลับหน้าแรก

hacker emblem