การตัดคำของ cttex

ว่าจะเขียนมานานแล้ว เพราะเอาโปรแกรมตัวเองมาดูทีไร ต้องนั่งนึกทุกทีว่าตอนนั้นคิดอะไรอยู่ ทำไมทำแบบนี้ จดเอาไว้เป็นเรื่องเป็นราวก็ดีเหมือนกัน ความจริงก็จดไว้เยอะแล้วใน README.note เอามาแปะซะเลย

หลักการทำงานของโปรแกรม cttex

ความจริงมันก็ไม่มีอะไรมาก cttex ตัดคำโดยเอาคำที่มีอยู่ในรายการคำ มาเทียบกับ วลีที่ป้อนเข้ามาให้ตัด โดยอาศัยหลักการ

"ตัดออกมาแล้วให้ได้จำนวนคำและจำนวนอักษรที่ไม่เป็นคำ น้อยที่สุด"

Longest word match with minimal word counts and unknown bytes.

หมายเหตุ ตัวอย่างการตัดแบบต่างๆในเอกสารนี้ ได้มาจากการระบุให้ cttex ทำงานในโหมด debug คือ "cttex -d 32 < inputfile"

1. เลือกใช้คำที่ยาวที่สุด

   เช่น ผู้ใช้ป้อนวลี "ทำการบ้าน" และในรายการคำมี "ทำ", "การ", "บ้าน", "การบ้าน" ซึ่งทำให้ สามารถตัดได้สองแบบ คือ
   a) ทำ การบ้าน
   b) ทำ การ บ้าน

   cttex จะเลือก a) เนื่องจาก "การบ้าน" ยาวกว่าคำว่า "การ" และ ในขณะเดียวกัน ทำให้ได้จำนวนคำรวมน้อยกว่าด้วย

2. ตัดให้ได้จำนวนคำน้อยที่สุด

   การตัดโดยเลือกคำที่ยาวที่สุดก่อนเพียงอย่างเดียว ไม่สามารถรับประกัน ได้ว่าจะได้จำนวนคำน้อยที่สุดเสมอไป เช่น

   มีนโยบาย
   => มีน โย บาย

   เนื่องจาก "มีน", "โย", "บาย" ล้วนเป็นคำที่มีอยู่ในรายการคำ

   ในกรณีนี้ cttex จะต้องทดลองตัดคำแรกที่ตำแหน่งสั้นลง คือ "มี" ทำให้ได้

   => มี นโยบาย

   ซึ่งมีจำนวนคำรวมน้อยกว่า ตัวอย่างอื่น ได้แก่

   ->รินโยบาย
   =ริน โย บาย Err(0) Word(3)
   =ริ นโยบาย Err(0) Word(2)
   ริ นโยบาย

   ->ขึ้นมาบริหาร
   =ขึ้น มาบ ริ หาร Err(0) Word(4)
   =ขึ้น มา บริหาร Err(0) Word(3)
   ขึ้น มา บริหาร

   อาจสังเกตว่า ปัญหานี้หลีกเลี่ยงได้ หากไม่มีคำว่า "ริ" ในรายการคำ แต่ก็ไม่สามารถรับประกันได้ว่า จะไม่มีปัญหาทำนองเดียวกันนี้กับคำอื่นๆ (ในที่นี้ ริ มาจากรายการคำของราชบัณฑิต)

   ดังนั้น cttex จึงต้องทดลองตัดทุกรูปแบบที่เป็นไปได้

3. ให้โอกาสคำหลัง

   ข้อนี้เป็นผลพลอยได้ของการตัดทุกรูปแบบในข้อ 2 ในบางกรณี หากตัดคำแรกยาวที่สุดแล้ว จะทำให้ไม่สามารถหาคำมาจับคู่กับ วลีที่ตามหลังมาได้ เช่น ("ผลก" เป็นคำในรายการคำ)

   ->ผลการดำเนินงาน
   a) =ผลก *า รด *ำ เนิน งาน Err(2) Word(4)
   b) =ผลก *า #ร ดำเนินงาน Err(2) Word(2)
   c) =ผล การ ดำเนินงาน Err(0) Word(3)

   c) เป็นคำตอบที่ดีที่สุด ซึ่งได้มาเมื่อตัดคำแรกให้สั้นลง

4. อักษรที่ไม่เป็นคำน้อยที่สุด

   ถึงแม้ว่าคำหน้าจะอยู่ในรายการคำ ก็ไม่ได้หมายความ ว่าเป็นคำที่สมควรมีอยู่จริง เช่น คำว่า "กก" ในคำต่อไปนี้

   ->กกบฎ
   a) กก บ*ฎ*
   b) ก* กบฎ
   ก กบฎ

   หากยึดมั่นในตัว "กก"จะได้ผลแบบ a) คือ มีอักษรที่ไม่เป็นคำสองตัว "บฎ" แต่หากยอมเสียสละ "กก" ก่อน จะได้วิธีการตัดที่ดีกว่า่ใน b) คือ เหลืออักษรที่ไม่เป็นคำเพียงตัวเดียว "ก"

   หลักการนี้ ทำให้ได้มาซึ่งข้อ b) ในกฎข้อที่ 3. ด้วย คือ ยอมสละ "รด" เพื่อให้ได้ "ดำเนินงาน" ซึ่ง b) เป็นคำตอบ ที่ดีกว่า หากคำว่า ผล ไม่มีในรายการคำ ( c) เป็นไปไม่ได้)

   ปัญหาที่เกิดขึ้นคือ การยอมเสียสละคำหน้าเมื่อไม่สามารถตัดวลีหลังได้นี้ ทำให้มีรูปแบบการตัดให้ตรวจสอบเพิ่มขึ้นมากเป็น exponential ตามความยาว ที่เพิ่มขึ้นของวลี ดังเช่นตัวอย่างในไฟล์ testfile/solong ซึ่ง cttex จะใช้เวลานานมากในการตัดวลียาวๆนั้น

   วลีที่ไม่มีเครื่องหมายวรรคตอนใดๆคั่นเลยนี้ มีโอกาสพบน้อย แต่ก็ไม่ถึงกับไม่มีเลย

5. การใช้กฎง่ายๆในการระบุตำแหน่งห้ามตัด

   เพื่อช่วยให้การตัดคำที่ไม่มีในรายการคำทำได้ถูกต้องมากยิ่งขึ้น cttex จะไม่ตัดในตำแหน่งต่อไปนี้

   • อยู่ท้ายสระนำ เ แ โ ไ ฯลฯ
   • ขึ้นต้นด้วยวรรณยุกต์ หรือสระที่อยู่ในตำแหน่งบนล่าง
   • ขึ้นต้นด้วยสระที่ควรตามหลังพยัญชนะ เช่น ะ า ฯลฯ

TODO

• ปัญหาเวลากับประโยคยาว ในข้อ 4.
• กฎมากขึ้นในข้อ 5. เช่น สระ เ-ีย

โปรแกรม digdict

เดือน กุมภาพันธ์ 2004: หลังจากตัดได้จำนวนคำและอักษรที่ไม่เป็นคำน้อยที่สุดแล้ว ปัญหาถัดมา คือ กรณีที่จำนวนคำมันเท่ากัน เช่น ตา กลม = ตาก ลม ฯลฯ ซึ่งอาจจะต้องใช้ ข้อมูลทางสถิติ หรือ Language Model ฯลฯ มาช่วย

ก่อนอื่นต้องมาดูก่อนว่าปัญหาแบบนี้ร้ายแรงแค่ไหน (มีสักกี่กรณี)

สร้างโปรแกรม digdict เพื่อค้นหา (brute force) ดูว่า ในรายการคำทั้งหมดที่มีอยู่นี้ ก่อให้เกิดความกำกวมในการ ตัดคำได้กี่รูปแบบ คือ

หาคำ a,b,x,y ที่ a+b = x+y
หรือ ยาวกว่านั้น a,b,c,x,y,z ที่ a+b+c = x+y+z
หรือสองข้างไม่เท่ากัน a,b,x,y,z ที่ a+b = x+y+z
หรือ ฯลฯ

เช่น

ตา กลม = ตาก ลม
ตลาด น้ำหอม = ตลาดน้ำ หอม
ไฮโดร เจนใจ คอพับ = ไฮโดรเจน ใจคอ พับ
ไฮโดร เจนใจ คอม้า = ไฮโดรเจน ใจคอ ม้า

จากคำที่ใส่เข้าไป 33018 คำ

vuthi@webls[14:06] wc tdict.txt 
  33018   33017  255084 tdict.txt

ลองรันโปรแกรมแบบแรก

digdict 1 > dig.d1
vuthi@webls[14:03] wc dig.d1
 262348 1293355 6545973 dig.d1

และแบบที่สอง (หลายวันเลย)

digdict 3 > dig.d3
vuthi@webls[14:03] wc dig.d3
55068883 381467791 1822045452 dig.d3

ก็มีอยู่เยอะเหมือนกัน แต่ส่วนมากเป็นการเรียงคำที่ไม่น่าจะพบเห็นในข้อเขียนทั่วไป เช่น "ไฮโดรเจนใจคอพับ" ข้างต้น เดี๋ยวต้องเอาไปค้นเทียบกับ Corpus ฯลฯ อีกที เอาอะไรดี บทความหนังสือพิมพ์ ?

เพิ่มเติม

• วิธีตัดคำเอามาเขียนใหม่แบบย่อ

• วันนี้ (17 สิงหาคม) เอาไฟล์ cttex-1.30 ล่าสุดใส่ไว้ใน Hui Files ให้ดาวน์โหลดได้