อธิบาย Wordcut.js 0.0.3 โปรแกรมตัดคำที่ปรับแต่งได้ง่าย

ตั้งแต่ปี 2003 ผมตั้งใจทำโปรแกรมตัดคำที่มี customize ง่าย ๆ หน่อย ตอนโน้นเขียนด้วยภาษา C ไม่น่าเชื่อว่าตอนนี้ 11 ปีแล้วก็ยังทำอยู่ T_T แต่เปลี่ยนมาเขียน JavaScript แทน แน่นอนเสียเรื่องความเร็วไปแต่ว่าความง่ายก็ตามมาด้วย 11 ปีที่ผ่านมาได้ได้ version นี้ มันมีความคืบหน้าบางอย่างก็อยากจะเขียนเล่าบ้าง

  • มาจากป๋าเทพถามผมหลายปีมาแล้วว่าสร้าง word graph ไว้ใน memory หรือเปล่า คำตอบของผมตอนโน้นก็คือสร้าง แล้วก็หา shortest path บน directed acyclic graph ที่สร้างมา แต่ว่ามาปีนี้ผมไม่ได้ทำอย่างนั้นแล้ว เพราะว่ามันเปลือง memory ตอนนี้ใช้วิธีเก็บ path ที่ดีที่สุดของทุก ๆ ตัวอักษรไว้แทน แต่ว่าไม่มี word graph แบบเต็ม ๆ แล้ว

    Word graph มันก็จะประมาณรูปนี้ล่ะครับ: wordgraph

  • หลักการคร่าว ๆ ของ Wordcut ก็คือสร้าง word graph (แต่อาจจะไม่ได้เก็บทั้งหมด) จาก finite state acceptor แล้วก็หา shortest path ออกมาเป็นคำตอบของการตัดคำเลย
  • acceptor จะเปลี่ยน state โดยมี input เป็นตัวอักษรที่ใส่เข้าไปทีละตัว
  • พอ acceptor ถึง final state ก็จะเพิ่ม edge เข้าไปใน word graph
  • เรื่อง word list ก็เหมือนกับ version เก่า ๆ คือเป็น plain text ธรรมดา 1 คำ 1 บรรทัด ก่อนใช้เพียงแต่เอาไป sort แบบนี้
    LANG=C sort -u  sorted_wordlist.txt
    

คร่าว ๆ ก็มีเท่านี้ล่ะครับ acceptor นี่อาจจะใช้ word list ก็ได้ หรือเป็นโปรแกรมล้วน ๆ ก็ได้

var WordRule = {
  tag: "WORD_RULE",
  createAcceptor: function(tag) {

    if (tag[this.tag])
      return null;

    return {strOffset: 0,
            isFinal: false,
            transit: function(ch) {
              var lch = ch.toLowerCase();
              if (lch >= "a" && lch <= "z") {
                this.isFinal = true;
                this.strOffset++;
              } else {
                this.isError = true;
              }
              return this;
            },
            isError: false,
            tag: WordRule.tag,
            w: 1};
  }
};

อันนี้เป็นแบบใช้โปรแกรมล้วน ๆ ไม่มี word list ตรง if (tag[this.tag]) return null; นี้แค่ใช้ตรวจสอบว่าไม่ต้องสร้าง acceptor หลาย ๆ ตัวมาซ้ำ ๆ กัน เพราะว่าอย่างสมมุติมีคำ aaab กับ ab อย่างไรก็เลือก aaab อยู่แล้ว ก็ไม่ต้องสร้างมาซ้ำอีก แต่ถ้าเป็นภาษาไทยก็ไม่ใช่แบบนี้แล้ว ส่วน w ก็คือ weight ที่จะใส่เข้าไปใน word graph, isError คือมันหลุดไป error state ปกติพอให้ isError เป็น true แล้ว acceptor ก็จะโดนทิ้งไป transit ก็คือการเปลี่ยน state

ที่ทำแบบนี้ทำให้สามารถเพิ่มกฎได้โดยแค่เขียนตัวสร้าง acceptor แบบตัวอย่างข้างบนแล้วยัดใส่ wordcut ได้เลย โดยคำสั่ง wordcut.acceptors.creators.push(…); เพื่อใครอยากจะลองเขียนกฎเองหรือใส่อะไรเป็นพิเศษก็ทำได้จากตรงนี้

ส่วนตัวหา shortest path อยู่ใน path_selector อันนี้ก็สามารถแก้เป็นวิธีการคำนวณแบบที่แต่ละคนต้องการได้ไม่ยากเหมือนกัน แค่ใส่ function ชื่อ selectPath เข้าไปใหม่ น่าจะสั่ง wordcut.pathSelector.selectPath = function(paths) { … } ได้เลย ดูตัวอย่างได้จาก github

โดยสรุปแล้ว wordcut ออกแบบมาให้ customize ง่าย ติดตามผลงานได้ที่ https://github.com/veer66/wordcut

Posted in ไม่มีหมวดหมู่

One thought on “อธิบาย Wordcut.js 0.0.3 โปรแกรมตัดคำที่ปรับแต่งได้ง่าย

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s