wordcut: ภาคอธิบาย

พอดี Pakkapon Phongthawee ตามมาเอกสารที่เคยเขียนก็เก่าแล้ว

หลัก ๆ แล้วการตัดคำที่เขียน ๆ มามี 2 ขั้นตอน ได้แก่

  1. สร้างกราฟ
  2. หาเส้นทางที่สั้นที่สุดบนกราฟในข้อ 1

สร้างกราฟ

กราฟของ “กินข้าว”

แต่ละเส้นเชื่อมแทนว่าแค่ละคำมีตัวอักษรอะไรบ้าง ส่วนเลข 0 3 6 7 คือดัชนีของตามตัวอักษร เช่น 3 คือนับว่ากินมีอักษร 3 ตัว

ส่วนกราฟสร้างขึ้นหลัก ๆ จากการเอารายการคำมาเทียบดู ยกเว้น ว ที่เชื่อมระหว่าง 6 กับ 7 อันนี้เพิ่มเข้ามากราฟมันต่อกันได้

กราฟแบบเป็นภาพนี้จริง ๆ ก็เก็บเป็น list กับ vector แบบนี้ แต่อาจจะดูงง ๆ หน่อยเพราะผมมักจะชี้ย้อนหลัง เช่น ใช้ 3 ชี้ไป 0

(vector nil nil nil (list 0) nil nil (list 3) (list 3 7))

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

(vector “กา” “กิน” “ข้า” “ข้าว”)

ในตัวอย่างนี้มี 4 คำแต่ทำจริง ๆ อาจจะมีเป็นแสนคำได้ เวลาไล่ไปในรายการคำ ก็ใช้การค้นหาแบบทวิภาค

เวลาไล่หาก็จะมีโครงสร้างอีกอย่างหนึ่งคือ pointer-list ก็ตามชื่อข้างในมี pointer ซึ่งประกอบไปด้วยสมาชิก 5 ตัวคือ :s :l :r :offset :is-final อธิบายได้ตามนี้ :s คือดัชนีของอักษรตัวแรก :offset จำนวนตัวอักษร เช่น pointer :s 3 :offset 3 ก็คือ ชี้ไปที่คำว่า “ข้า” ส่วน pointer :s 3 :offset 4 ก็คือชี้ไปที่คำว่า “ข้าว” ส่วน :is-final คือบอกว่าเป็นคำหรือยัง เช่น ข้ :is-final ก็จะเป็น false คือยังไม่เป็นคำ ส่วน ข้า เป็นคำแล้ว :is-final ก็เป็น true สุดท้าย :l และ :r เอาไว้ชี้ตำแหน่งในรายการคำ อย่างรายการคำนี้ค่าเริ่มต้นก็คือ :l 0 และ :r 3

สิ่งที่ pointer ทำได้ก็คือโดน update ด้วยตัวอักษา เช่น (update pointer ก) โดยค่าเริ่มแรกคือ :s 0 :l 0 :r 3 :offset 0 :is-final false พอ update ด้วย ก ก็จะเข้าไปหาในรายการคำว่า คำที่ตำแหน่งที่ 0 ตัวไหนมี ก บ้าง ก็มีสองคำแรกดังนั้น :l ก็จะเป็น 0 เหมือนเดิม เพราะคำแรกเป็น ก นำ ส่วน :r เป็น 1 แทนเพราะคำสุดท้ายที่มี ก คือคำที่ 2 ส่วน :is-final เป็น false และ :offset เป็น 0

มาลองในส่วน pointer-list บ้าง ก็จะมีฟังก์ชันประมาณ (update-pointer-list pointer-list “ฉันกินข้าว” 0) ขึ้นมา สิ่งที่ update-pointer-list ทำก็คือเพิ่ม pointer ใหม่เข้าไปใน pointer-list เลย เสร็จแล้วก็สั่ง update pointer ทุกตัว ตัวไหนก็หาคำในรายการไม่เจอก็เอาออกไป ส่วนที่พอหาเจอก็เก็บไว้ แล้วก็เอาไปทำตัวต่อไป เช่น (update-pointer-list pointer-list-0 “ฉันกินข้าว” 1) (update-pointer-list pointer-list-1 “ฉันกินข้าว” 1)

จากขั้นตอนข้างบนหลังจากที่ update-pointer-list ทุกครั้งก็มีดูว่า pointer-list มีตัวสมาชิกไหนที่ :is-final เป็น true ไหม ถ้ามีก็เอาไปสร้างเส้นเชื่อม

หาเส้นทางที่สั้นที่สุด

เวลาหาเส้นทางสั้นที่สุดจะใช้ค่าสองอย่าง คือพยายามทำให้คำที่ไม่มีในรายการคำน้อยที่สุด เช่น ไม่ควรไปผ่าน ว เดี่ยว ๆ และอีกอย่างที่สำคัญลงมาคือผ่านเส้นทางที่มีจำนวนคำน้อยที่สุด

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