LibThai 0.1.21

LibThai 0.1.21 ออกแล้ว โดยรุ่นนี้ นอกเหนือจากการปรับพจนานุกรมตัดคำตามปกติ ก็ยังมีการเพิ่มสมรรถนะของตัวตัดคำเล็กน้อยด้วย

ตอนที่ยกเครื่องตัวตัดคำของ LibThai เขียนใหม่เมื่อ 8 ปีที่แล้วนั้น (การประเมินผลขณะ merge เข้า trunk) ก็ได้คิดเผื่ออัลกอริทึมแบบอื่นไว้ขณะออกแบบเหมือนกัน กะว่าอาจมาปรับเพิ่มในอนาคต แต่ก็ไม่ได้กลับไปดู จนมาถูกกระตุ้นด้วยการเปิดไฟล์ HTML บางไฟล์ด้วย Firefox/Iceweasel แล้ว พบว่าใช้เวลานาน จึงได้เอาความคิดนี้มาปัดฝุ่นใหม่ โดยพยายาม refactor โค้ดเตรียมรองรับอัลกอริทึมอื่นไว้

และก็ได้คิดออกแบบอัลกอริทึมแบบ longest matching ดู โดยอาศัยโครงจากอัลกอริทึม maximal matching ปัจจุบัน แต่ขณะสำรวจและวิเคราะห์โค้ดเดิม ก็กลับเกิดไอเดียที่จะลดขั้นตอนของโค้ดเดิมขึ้นมาแทน

ผมใช้ callgrind วัดเวลาที่ใช้ในฟังก์ชันต่าง ๆ ก็พบว่าฟังก์ชันที่กินเวลามากที่สุดคือ brk_recover_try() ซึ่งใช้สำหรับหาจุด recover จากคำที่ไม่อยู่ในพจนานุกรม จึงพยายามมุ่งมาลดขั้นตอนในฟังก์ชันนี้

ผมมีสมมุติฐานมากมาย ตั้งแต่การลดการ assign การคัดลอก และการตรวจค่าเล็ก ๆ น้อย ๆ ที่ไม่จำเป็นออก ไปจนถึงการปรับกระบวนการคิดของอัลกอริทึม แล้วก็ต้องโยนทิ้งไปหลายเรื่อง เพราะบางเรื่องเอาเข้าจริงกลับทำให้ใช้เวลาเพิ่มขึ้น มีเพียงเรื่องเดียวที่ทำให้ลดเวลาได้อย่างจริงจัง คือการปรับวิธีตรวจสอบจุด recover จากการ match คล้ายการตัดคำปกติ มาเป็นการ match แบบละโมบ (greedy) โดยพยายาม match คำให้ได้มากคำที่สุดสำหรับแต่ละทางเลือกที่หยิบออกมา ซึ่งมีผลทำให้พบคำตอบได้อย่างรวดเร็วในกรณีที่จุดนั้นสามารถ recover ได้ อีกทั้งไม่ต้องไปเสียเวลาเลือกทางเลือกมาพิจารณาให้มากเกินไป เพราะจุดประสงค์ของการ recover ก็แค่พิจารณาว่าแต่ละจุดสามารถ recover จาก error ได้หรือไม่เท่านั้น ไม่ได้ต้องการ solution ที่สวยงามว่า recover แล้วต้องได้การตัดคำที่ดีที่สุด

ความจริงแนวคิดนี้ก็เคยทำไปแล้วตั้งแต่รุ่นแรก ๆ ด้วยการหยุดทันทีที่พบคำตอบแรก ไม่ต้องไปสนใจลองคำตอบอื่น แต่ครั้งนี้ได้เร่งให้พบคำตอบแรกเร็วขึ้นไปอีก

แนวคิดอื่นที่ยังทำไม่สำเร็จก็เช่น ลดจำนวนการ recover ลง, ลดขนาดของ search space ลง, ทำ cut-off แต่ไว้ค่อยคิดต่อไป รวมถึงการสร้างอัลกอริทึมแบบอื่นด้วย แต่ตอนนี้ขอออกรุ่นที่ปรับสมรรถนะเล็กน้อยนี้ก่อน ให้ทันใช้ใน Jessie ที่กำลังจะ freeze ในเดือนตุลานี้ โดยถือหลัก ออกเนิ่น ๆ ออกถี่ ๆ (release early, release often) เพื่อให้ตัวไลบรารีถูกทดสอบแต่เนิ่น ๆ ด้วย

สำหรับสมรรถนะตัวตัดคำที่เพิ่มขึ้นในรุ่นนี้ วัดเวลาจากกรณีทดสอบโดยใช้ callgrind:

• ก่อนปรับ: 48,094,350
• หลังปรับ: 46,893,901

คิดเป็นเวลาที่ลดลง = 2.50%

แต่นี่นับรวมทั้งหมดตั้งแต่เปิดพจนานุกรม, ตัดคำ, ปิดพจนานุกรม ซึ่งเวลาที่ใช้เกี่ยวกับพจนานุกรมนับเป็นสัดส่วนที่มากเอาการอยู่ และเป็น fixed cost ที่เกิดเพียงครั้งเดียวเท่านั้นตลอดโพรเซสที่เรียกตัวตัดคำของ libthai ดังนั้น ผมจึงวัดเวลาที่ใช้ในการเปิด-ปิดพจนานุกรมมาหักลบใหม่:

• เฉพาะเปิด-ปิดพจนานุกรม: 32,961,393

เมื่อหักลบเวลาเปิด-ปิดพจนานุกรม จะเหลือเวลาสำหรับช่วงตัดคำจริง ๆ คือ:

• ก่อนปรับ: 15,132,957
• หลังปรับ: 13,932,508

คิดเป็นเวลาที่ลดลง = 7.93%

หรืออัตราเร็วที่เพิ่มขึ้น = 1 / (1 - 0.0793) - 1 = 0.0861 หรือ 8.61%