อธิบาย 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

Advertisements
This เรื่อง was posted in ไม่มีหมวดหมู่. Bookmark the permalink.

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