การบีบอัดรูปแบบการผันชื่อภาษาไอซ์แลนด์ด้วย trie ขนาด 3.27kB

 (alexharri.com)
2 คะแนน โดย GN⁺ 2025-08-04 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • การจัดการการผันชื่อบุคคลภาษาไอซ์แลนด์ เปลี่ยนรูปได้ 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 ตามรูปแบบ
  • เป็นบทเรียนสำคัญทางการประมวลผลข้อมูลในทางปฏิบัติที่พิจารณาสมดุลระหว่างขนาดข้อมูลและความแม่นยำอย่างเหมาะสม

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-08-04
ความคิดเห็นจาก Hacker News

  • ตอนเรียนภาษาสเปนครั้งแรกในสมัยมัธยม เคยใช้ซอฟต์แวร์บน Windows ที่ยิงคำกริยารูปต้นและกาลต่าง ๆ ออกมาเป็นชุด ๆ แล้วให้กรอกรูปผันให้ตรง ทำให้ซึมซับกฎไวยากรณ์จนใช้งานคล่องขึ้นมาก แต่พอมาเรียนภาษารัสเซีย การผันตามการกกลับกลายเป็นเรื่องยากทันที และไม่ว่าจะหาแอปที่อธิบายหรือให้ฝึกแพตเทิร์นคล้าย ๆ กันอย่างไรก็หาไม่เจอ เลยสงสัยว่ามีใครรู้จักแอปสำหรับจุดประสงค์นี้ไหม (เว็บหรือ macOS/iOS ก็ได้)

    • ใน Anki มีเด็คแฟลชการ์ดที่ใช้วิธีชื่อว่า "KOFI (Konjugation First)" ซึ่งหมายถึงการเรียนรู้แพตเทิร์นการผันทั้งหมดก่อนจะเริ่มเรียนภาษา หลังจากเรียนภาษาฝรั่งเศสแล้วพบว่าทักษะการผันยังอ่อน เลยลองวิธีนี้ทีหลัง แม้จะพูดผิดไวยากรณ์แล้วสื่อสารในชีวิตประจำวันได้ไม่มีปัญหา แต่ก็ยังไม่ถึงระดับที่ต้องการ วิธีนี้มีเป้าหมายให้จำแพตเทิร์นการผันทั้งหมดให้ได้ในช่วงสั้น ๆ ก่อนเริ่มเรียนภาษา สักวันหนึ่งก็อยากลองใช้กับภาษาใหม่แบบจริงจัง ความสนใจในภาษาฝรั่งเศสลดลงไปแล้วเลยเลิกกลางคัน ลิงก์เด็ค Anki ที่เกี่ยวข้อง

    • ตอนเรียนภาษารัสเซีย เคยเขียนสคริปต์ที่ใช้โมดูล Python ของ spaCy ร่วมกับโมดูลขนาดใหญ่สำหรับภาษารัสเซีย เพื่อทำ lemmatization ตามบริบทและดึงแท็กไวยากรณ์ออกมา แต่พอทักษะภาษารัสเซียเริ่มพัฒนาจริง ๆ กลับพบว่าการเลิกพยายามแยกวิเคราะห์การผันอย่างเป็นตรรกะ แล้วสะสมคลังแพตเทิร์นไว้ในหัวจากประสบการณ์ใช้งานและการทบทวนซ้ำ ๆ (รวมทั้งข้อยกเว้น) ได้ผลกว่ามาก โดยบริบทในที่นี้หมายถึงความหมายภายในประโยค

    • เมื่อ 25 ปีก่อนตอนเรียนภาษาสเปนด้วยตัวเอง เคยใช้พจนานุกรมสเปน/อังกฤษ โดยคำกริยารูปต้นจะมีดัชนีตัวเลขกำกับไว้ เพื่อจัดเข้ากลุ่มที่ใช้แพตเทิร์นการผันแบบเดียวกัน ส่วนต้นพจนานุกรมจะมีตารางผันครบทุกกาลของคำกริยาตัวแทนในแต่ละกลุ่ม คำกริยาไม่ปกติก็มีดัชนีแยกต่างหาก และยังจัดคำกริยาไม่ปกติที่คล้ายกันให้อยู่กลุ่มเดียวกันด้วย (เช่น tener, detener) คำกริยาทั้งหมดถูกจัดระเบียบอย่างสวยงามเป็นแพตเทิร์นเฉพาะไม่กี่สิบแบบ เคยคิดจะทำซอฟต์แวร์ตอบคำถามโดยใช้ระบบนี้ แต่สุดท้ายก็ไม่ได้ทำ เลยสงสัยว่าแพตเทิร์น reverse-string trie ที่บทความพูดถึง จะเอามาใช้กับการจัดหมวดแบบนี้ได้ไหม

    • เคยมีไอเดียว่าจะจำการผันตามการกของภาษารัสเซียให้เร็วขึ้นด้วยการทำแฟลชการ์ดเป็นชุด preposition + adjective + noun ก่อนหน้านี้เคยเรียนภาษาละตินมาก่อน ซึ่งการผันตามการกของภาษาละตินไม่ได้คาดหวังว่าจะท่องเร็วได้ง่าย ๆ (ยกเว้นจะเป็นนักบวช) แต่กับภาษารัสเซียอยากให้คล่องเร็วกว่าเดิม สุดท้ายก็ไม่ได้พัฒนาเป็นโปรเจกต์

    • ใช้ ConjuGato บน iOS เพื่อฝึกการผันภาษาสเปนอยู่ ในโหมดเกมจะให้คำกริยารูปต้น/กาล/บุรุษ แล้วให้เรานึกคำผันออกมา สามารถฝึกเฉพาะคำกริยาไม่ปกติได้ด้วย จึงมีประโยชน์มากสำหรับการจำข้อยกเว้น

  • สำหรับชื่อ 800 ชื่อที่ข้อมูลการผันตามการกหายไปจากฐานข้อมูล วิธีที่ตรงไปตรงมาที่สุดน่าจะเป็นการกำหนดรูปผันด้วยมือเอง ถ้าเป็นเจ้าของภาษาก็น่าจะทำเสร็จได้ในไม่กี่ชั่วโมง และถึงจะเป็นชื่อที่ไม่คุ้นเลย อย่างน้อยก็น่าจะเดารูปที่ไม่ดูแปลกชัดเจนได้ หรือจะให้ LLM ทำก็มีต้นทุนต่ำมากอยู่แล้ว จากนั้นเอาผลลัพธ์มาเข้ารหัสแจกจ่ายด้วยโครงสร้าง trie แบบนี้ก็ยังเป็นไอเดียที่ดี เพียงแต่ไม่จำเป็นต้องใช้ trie เป็นตัวเดารูปผันด้วย

    • ควรรองรับชื่อให้ได้มากกว่านี้—ใน DIM นี่เป็นส่วนที่ต้องเติมต่อเนื่องอยู่แล้ว ในไอซ์แลนด์มีการเพิ่มชื่อใหม่เข้าไปในรายชื่อชื่อที่ได้รับอนุญาตบ่อย ๆ จึงเลี่ยงช่องโหว่ไม่พ้น สำหรับตัวเองยังไม่มั่นใจพอจะเพิ่มข้อมูลด้วยมือ และทุกครั้งที่ตรวจผลลัพธ์ของชื่อที่ยังไม่ยืนยัน 100 ชื่อ ก็มักจะมีหลายชื่อที่ทำให้คิดว่า “แบบนี้ถูกไหมนะ?” หลายครั้งลองไปค้นชื่อคล้ายกันใน DIM แล้วก็คิดว่า “ถ้าเป็นฉันคงไม่ผันแบบนั้น” เพราะแบบนี้จึงถือข้อมูลของ DIM เป็น ‘แหล่งความจริง’ ที่ผู้เชี่ยวชาญทางภาษาดูแลอยู่

    • ทำมือก็ดี แต่กับชื่อที่ไม่อยู่ในรายชื่อทางการ (เช่น ชื่อต่างประเทศ) ก็ยังมีข้อจำกัดอยู่ดี ฉันเองก็อยู่ในประเทศที่มีรายชื่อชื่อแบบรวมศูนย์เหมือนกัน แต่ก็ขอข้อยกเว้นได้ และก็มีทั้งคนที่เกิดก่อนมีรายชื่อนี้หรือผู้อพยพที่อาจไม่มีชื่ออยู่ในรายการ ในสถานการณ์ผสมหลายแบบอย่างนี้ ฟังก์ชัน “ทำนายรูปผันที่น่าจะพอใช้ได้” ก็ยังมีประโยชน์อยู่มาก

    • ยังไม่เห็นหลักฐานว่าการให้ LLM ทำนายรูปผันจะทำได้ดีกว่า trie (ถ้าตัวอย่างจริงไม่ได้อยู่ในข้อมูลฝึกของ LLM การค้นเว็บน่าจะดีกว่า)

    • เลยเริ่มสงสัยว่า LLM ที่มีอยู่ตอนนี้ได้เรียนรู้แพตเทิร์นแบบนี้ไว้แล้วหรือยัง

  • ไม่แน่ใจว่า Rails จัดการปัญหานี้ให้อัตโนมัติไหม แต่สมัยก่อนมันชอบมีเวทมนตร์แบบนี้อยู่ เคยเปิดดูซอร์สโค้ดของ pluralise แล้วพบว่ามีการเข้ารหัสแม้กระทั่งกฎพหูพจน์ไม่ปกติของภาษาเวลส์เอาไว้ด้วย

    • Rails ดีจริง ๆ เพราะแทบทุกฟังก์ชันที่นึกออกก็มักจะมีเมธอดเตรียมไว้ให้แล้ว

  • ไอเดียการปรับแต่งอย่างหนึ่งคือ แทนที่ trie จะจับคู่ไปยังสตริง suffix โดยตรง ก็สร้างอาร์เรย์ของ suffix ที่ไม่ซ้ำกัน แล้วให้ trie อ้างถึงดัชนีในอาร์เรย์นั้นแทน เช่น:

    const suffixes = [",,,", "a,u,u,u", ",,i,s", ",,,s", "i,a,a,a", ...];

    แล้วอ้างถึงดัชนีแบบนี้:

    var serializedInput = "{e:{n:{ein:0_r: ..."

    • ลองทำเองด้วย Claude Code แล้ว ผลคือหลัง gzip กลับเพิ่มขึ้น 100 ไบต์ (3456 -> 3556) และลดได้แค่ขนาดก่อนบีบอัดราว 20% ดูเหมือนว่า gzip จะปรับแต่งกับแพตเทิร์นซ้ำ ๆ แบบนี้ได้ดีอยู่แล้ว

    • ถ้าจะไปต่ออีกขั้น ก็อาจใส่ suffix เองลงไปใน trie แล้วระบุซับทรีที่เหมือนกันเพื่อตัดความซ้ำซ้อนออก ถ้าใช้ gzip ได้ ก็น่าจะยังมีวิธีปรับแต่งฉลาด ๆ โดยใช้อาร์เรย์ suffix ได้อีกแน่ ๆ และถ้าใช้ฟอร์แมตที่ปรับแต่งสำหรับไบนารีก็อาจดีกว่านี้

  • โดยส่วนตัวยังรู้สึกอยู่เรื่อย ๆ ว่าน่าจะมีวิธีมหัศจรรย์ที่ทำให้ขนาดแบบไม่บีบอัดต่ำกว่า <1kb ได้ เช่น สร้างลิสต์ regular expression แบบย่อที่สุดที่จัดหมวดชื่อได้ถูกต้อง 100%? หรือ bloom filter ขนาดใหญ่มาก? หรือใช้ฟีเจอร์เฉพาะทางแทนแฮชทั่วไป?

  • ฟังดูเหมือนโจทย์สัมภาษณ์สายฝันร้ายเลย การใช้ trie แบบกลับด้าน (ย้อนลำดับ) เป็นอะไรที่น่าจะได้ใช้ทั้งชีวิตแค่ครั้งเดียว แต่ถ้าได้ใช้ครั้งนั้นก็คงดูเหมือนพ่อมดไปเลย

    • จะพูดให้แม่นกว่าคือ ไม่ได้กลับ trie แต่เอาชื่อไปใส่แบบกลับด้านมากกว่า

  • แทนที่จะทำเรื่องนี้ใน JS น่าจะให้ฐานข้อมูลส่งคืนทุกชุดผสมของ name-case มาเลย แล้วค่อยเลือกเฉพาะที่ต้องใช้ตอนแสดงผลก็ได้ คือไปจัดการในชั้น localization แทน แต่อยากรู้ว่าถ้าเป็นข้ามภาษาจะเป็นอย่างไร เช่น ถ้า UI ภาษาไอซ์แลนด์ต้องจัดการชื่อฝรั่งเศส ก็คงใช้แค่ nominative เสมอ และถ้า UI ภาษาอังกฤษต้องจัดการชื่อไอซ์แลนด์ก็น่าจะเหมือนกัน สุดท้ายแล้วคงจำเป็นมากจริง ๆ แค่ในบริบทที่ต้องระบุหรือเรียกผู้ใช้โดยตรง หรือในแอดมินพาเนลประเภท “user x ตอบกลับ user y”

  • มีชื่อถึง 88 ชื่อที่ใช้แพตเทิร์นการผันตามการกแบบเฉพาะซึ่งลงท้ายด้วย “idur”, “tur”, “ður” แต่ suffix เดียวกันก็ไม่ได้แปลว่าจะใช้แพตเทิร์นการผันเดียวกันเสมอไป เรื่องนี้ดูเหมือนกฎง่าย ๆ แต่จริง ๆ น่าสนใจมาก แพตเทิร์น suffix อาจเกี่ยวกับการออกเสียงของพยางค์ก่อนหน้าหรือเปล่า? ถ้าจะรองรับชื่อที่ไม่รู้จักให้ดีขึ้น บางทีอาจต้องดึงตัวแทนเสียงอ่านของชื่อด้วย NLP แล้วค่อยค้นผ่าน trie หรือโครงสร้างคล้ายกัน แทนที่จะอิงแค่ตัวอักษรอย่างเดียว?

    • คิดแบบนี้ต่อไปเรื่อย ๆ มีโอกาสไหลไปสู่การถกเรื่อง Dependent Types ได้ ต้องระวังไว้

    • เป็นไอเดียที่คมมาก จริง ๆ แล้วแม้แต่ชื่อที่ออกเสียงเหมือนกันก็ยังมีแพตเทิร์นการผันต่างกันได้ เช่น:

      • Ástvaldur -> ur,,i,ar
      • Baldur -> ur,ur,ri,urs ชื่อสองชื่อนี้ลงท้ายด้วย “aldur” เหมือนกันและออกเสียงเหมือนกัน แต่แพตเทิร์นการผันต่างกัน ถ้าเอาแพตเทิร์นของ “Ástvaldur” ไปใช้กับ “Baldur” รูปสามแบบท้ายจะฟังแปลกมาก (ถามคู่ชีวิตชาวไอซ์แลนด์มาแล้วด้วย) ภาษาไอซ์แลนด์โดยทั่วไปสะกดค่อนข้างตรงกับเสียงอยู่แล้ว ดังนั้นแม้จะใช้ trie ที่อิงเสียงอ่าน ความต่างก็คงไม่มากนัก

  • ในกรณีของ beygla/strict อาจลองพิจารณา perfect hashing เป็นทางเลือกได้

    • ถ้าค่าทั้งหมดไม่ได้เป็นเอกลักษณ์เฉพาะตัวทุกค่า ก็อาจบีบอัดได้มากกว่า perfect hashing ปกติ โดยใส่คู่ name->suffix หลายคู่ไว้ในแฮชบักเก็ตเดียวกันได้ แต่แบบนี้จะเสียความสามารถในการตัดสินว่า “ชื่อนี้จัดการไม่ได้”

  • น่าแปลกใจที่การแปลงการกของชื่อภาษาไอซ์แลนด์ดูจะเรียบง่ายและเป็นไปตามแพตเทิร์นชัดเจนพอให้วิธีแบบนี้ใช้ได้ดี ทั้งที่ภาษาโดยทั่วไปมักซับซ้อนมาก

    • น่าจะเป็นผลจากการที่ไอซ์แลนด์มีประชากรน้อย และภาษาก็ได้รับการกำกับดูแลอย่างแข็งขันจากภาครัฐ