- การจัดการการผันชื่อบุคคลภาษาไอซ์แลนด์ เปลี่ยนรูปได้ 4 แบบตามบริบท
- พัฒนาฟังก์ชันที่คืนค่ากรณีไวยากรณ์ที่เหมาะสมสำหรับชื่อที่ป้อนผ่าน ไลบรารี JavaScript เชิงข้อมูล
- การเก็บชื่อทั้งหมดแบบตรงทำให้เกิด การขยายขนาด และปัญหาข้อมูลขาดหาย จึงแก้ปัญหาโดยใช้โครงสร้าง trie และเทคนิคการบีบอัด
- ด้วย การบีบอัด trie ทำให้สามารถอนุมานอัตโนมัติตามรูปแบบร่วม และได้ฐานข้อมูลขนาดเล็กมากที่ครอบคลุมข้อมูลเกิน 80%
- ในสถานการณ์ทั่วไปมี ความแม่นยำมากกว่า 74% และมีเวอร์ชัน strict แยกต่างหากสำหรับภาครัฐหรือสถานการณ์ที่ต้องการความแม่นยำสูง
ที่มา
- การแสดงชื่อส่วนบุคคลในอินเทอร์เฟซภาษาไอซ์แลนด์มีปัญหาเนื่องจาก การผัน (declension)
- ชื่อภาษาไอซ์แลนด์มีรูปต่างกันตาม กรณีไวยากรณ์ ทั้ง 4 แบบ ได้แก่ กรณีประธาน, กรรมตรง, กรรมทางอ้อม, และกรรมความเป็นเจ้าของ
- ฐานข้อมูลมักเก็บชื่อในรูป กรณีประธาน ทำให้มีปัญหาตอนต้องใช้กรณีอื่นตามบริบท
- ถ้าใช้รูปไม่ถูกต้อง จะรู้สึกไม่เป็นธรรมชาติ
การเก็บข้อมูลและทำความสะอาดข้อมูล
- ประเทศไอซ์แลนด์เปิดให้เข้าถึงข้อมูล DIM (Database of Icelandic Morphology) ที่ดำเนินการโดย Árnastofnun
- ข้อมูลการผันของชื่อสามารถจัดรูปแบบเป็นไฟล์ CSV โดยใช้ Kristín’s Format(K-format)
- แม้ข้อมูล DIM ทั้งหมดจะมีขนาดถึง 7 ล้านแถวและค่อนข้างกว้างใหญ่ แต่เมื่อคัดเฉพาะ ชื่อบุคคลที่ได้รับการอนุมัติอย่างเป็นทางการ (4,500 รายการ) ก็สามารถได้ข้อมูลการผันสำหรับชื่อมากกว่า 3,600 รายชื่อ
- สำหรับแต่ละชื่อสามารถสร้าง อาร์เรย์รูปแบบกรณีตั้งแต่กรณีประธานถึงกรรมสัมพันธ์ ได้
โครงสร้างพื้นฐานของไลบรารี
- การออกแบบเริ่มแรกเริ่มจากฟังก์ชัน applyCase ซึ่งคืนค่ารูปที่เหมาะสมจากอาร์เรย์รูปแบบการผันของชื่อ
- อย่างไรก็ตามวิธีโหลดอาร์เรย์ธรรมดามี ขนาดใหญ่ (30kB gzipped)
- มีข้อจำกัดว่าไม่สามารถรองรับชื่อที่ไม่อยู่ในข้อมูลได้
การลดความซ้ำซ้อนและการสกัดรูปแบบ
- สกัด คำนำหน้า (prefix) ร่วม ระหว่างรูป 4 รูปแบบของชื่อ แล้วเก็บเพียง ชุดส่วนต่อท้าย (suffix encoding) ของแต่ละแบบเพื่อให้น้อยการซ้ำซ้อนที่สุด
- พบว่าชื่อจำนวนมากใช้รูปแบบการผันแบบเดียวกัน
การนำ trie มาใช้สำหรับการจับคู่รูปแบบ
- ใช้ โครงสร้าง trie (แทรกตามส่วนต่อท้ายจากท้ายไปต้น) เพื่อปรับปรุงการแมปค่าของกลุ่มชื่อที่ใช้รูปแบบใกล้เคียงกันให้มีประสิทธิภาพขึ้น
- เก็บข้อมูลการผันเพียงครั้งเดียวภายใต้ รูปแบบร่วมกัน (ส่วนท้ายชื่อ) ทำให้สามารถทำนายชื่อใหม่ได้ค่อนข้างแม่นยำ
ขั้นตอนการบีบอัดและปรับแต่ง trie
- หาก ค่าของ leaf แต่ละตัวใน subtree เหมือนกัน จะกำหนดค่าให้โหนดระดับบนและลบโหนดลูก เพื่อลดการบีบอัดต้นไม้
- ผลลัพธ์คือ จำนวนโหนดลดลงสูงสุด 15.4% และขนาดลดเหลือ 4.01kB
- ด้วยการบีบอัดรอบที่สองที่รวม leaf พี่น้องที่มีค่าเท่ากัน เข้าเป็นโหนดเดียวกัน ทำให้ได้ขนาดลงไปถึง 3.27kB
ประสิทธิภาพและการทั่วไปของ trie
- เมื่อมีชื่อใหม่เข้ามา ระบบสามารถทำการ ผันอัตโนมัติโดยอิงรูปแบบที่คล้ายกัน ได้
- ทดสอบกับชื่อที่ไม่รู้จักมาก่อนจริงแล้วให้ผลถูกต้อง 74% และผิดพลาด 26%; ในสภาพการใช้งานจริงของผู้ใช้ อัตราความผิดพลาดอยู่ที่เพียง 0.34%
- เมื่อข้อมูลมี ความสม่ำเสมอ (regularity) และ ความครอบคลุม (comprehensiveness) สูง การบีบอัดและความแม่นยำของการอนุมานอัตโนฎียิ่งดีขึ้น
ไลบรารีจริงและการประยุกต์ใช้
- สุดท้ายจึงเผยแพร่เป็นไลบรารี beygla ที่ใช้ trie แบบบีบอัด
- ให้ใช้งานได้ทั้งขนาดขั้นต่ำ (4.46kB) และ โมดูล strict ที่เข้มงวดและสมบูรณ์ยิ่งขึ้น (15kB)
- เวอร์ชัน strict สำหรับกรณีที่ต้องการความแม่นยำ 100% เช่น เอกสารภาครัฐ และในเว็บแอปทั่วไปสามารถเลือกใช้เวอร์ชันตัวนำที่เบากว่าได้
สรุปและความเป็นไปได้ในการขยายผล
- การอัตโนมัติการผันชื่อบุคคลภาษาไอซ์แลนด์ นี้เป็นตัวอย่างการใช้โครงสร้างข้อมูล trie ตามรูปแบบเพื่อทำให้ระบบมีขนาดเล็กและอัตโนมัติขึ้น
- เป็นตัวอย่างเชิงกลยุทธ์ในการจัดการข้อมูลเชิงปฏิบัติการที่คำนึงถึงการสมดุลระหว่างขนาดกับความแม่นยำได้อย่างเหมาะสม
บันทึกขอบคุณ
- ในกระบวนการพัฒนา beygla มีการรับข้อเสนอแนะจากผู้เชี่ยวชาญหลายรายและมีการปรับปรุงการปรับให้เหมาะสมอย่างต่อเนื่อง
- การบีบอัดเพิ่มเติมของ trie ทำให้ขนาดลดลงจาก 3.43kB ถึง 3.27kB
สรุป
- การอัตโนมัติการผันชื่อบุคคลภาษาไอซ์แลนด์ ในกรณีนี้เป็นตัวอย่างการทำให้ข้อมูลเล็กและอัตโนมัติด้วยโครงสร้างข้อมูล trie ตามรูปแบบ
- เป็นบทเรียนสำคัญทางการประมวลผลข้อมูลในทางปฏิบัติที่พิจารณาสมดุลระหว่างขนาดข้อมูลและความแม่นยำอย่างเหมาะสม
ยังไม่มีความคิดเห็น