ทรัย (โครงสร้างข้อมูล)

ที่มา

มาจากคำว่า Retrieval ซึ่งตามที่มาจะอ่านของ “ทรี” ตามผู้ออกแบบ data structure นี้ แต่บางคนก็อ่านว่า “ทรัย”

แนวคิด

Trie หรือเรียกอีกอย่างว่า prefix tree คือ โครงสร้างข้อมูลแบบ ordered tree มักใช้เก็บ associative array ที่มี key เป็น String ซึ่งจะต่างจาก BST(Binary Search Tree) ตรงที่ในแต่ละโหนดของ BST จะเก็บ key เพื่อเอาไว้ทำการเปรียบเทียบ โดย node ของ Trie จะไม่เก็บ key ไว้ แต่ตำแหน่งของ node นั้น tree จะบอกว่า node เชื่อมกับ key ไหนแทน โดยมีรายละเอียดดั้งนี้

• โหนดลูกจะมี prefix ของ string ที่กำหนดในโหมดพ่อ
• โหนดพี่น้องทางซ้ายจะมีค่าน้อยกว่าโหนดพี่น้องทางขวา เช่น a,b,c
• โหนดรากเชื่อมกับ String ว่าง “”
• เราไม่จำเป็นต้องกำหนด value ให้ทุกโหนดเราจะสนใจเฉพาะโหนดใบ หรือ โหนดภายในบางโหนดที่สนใจเท่านั้น

• โครงสร้างของ Trie
• การค้นหาใน Trie

ข้อดีเมื่อเทียบกับโครงสร้างข้อมูลอื่นๆ

ข้อดีเมื่อเทียบกับ BST

ให้ m = ความยาวของ key, n = จำนวนข้อมูล

• ใช้เวลาค้นหาเร็วกว่า โดยมี worst case O(m) ซึ่งจะพบว่าจำนวน node ภายในไม่มีผลต่อความเร็วในการค้นหา ต่างกับ BST ที่ใช้จำนวนครั้งในการเปรียบเทียบ O(log(n)) ซึ่ง worst case จะต้องเทียบเท่ากับ O(m×log(n)) มาจากจำนวนครั้งที่เปรียบเทียบ key × จำนวนตัวอักษรใน key
• ประหยัดพื้นที่ ถ้า key เป็น string สั้นๆจำนวนมาก เพราะว่า key ไม่ได้ถูกเก็บเป็น string เต็มๆ แต่จะถูกเก็บเป็น subsequence ที่มี prefix แบบเดียวกัน
• สามารถค้นหา Longest-prefix matching ได้ โดย key ไม่จำเป็นต้องเป็นแบบ exact match

ข้อดีเมื่อเทียบกับ Hash Table

• key ไม่จำเป็นต้องเป็นตรงกับสิ่งที่ค้นหาทั้งหมด(exact match) สามารถค้นหา key ที่ใกล้เคียงที่สุดได้
• แนวโน้มประสิทธิภาพในการเพิ่มข้อมูลเร็วกว่า เพราะสามารถเพิ่มข้อมูลได้เรื่อยๆไม่จำเป็นต้องทำงาน rehash()
• สามารถ implement ให้หลีกเลี่ยงการใช้ memory เพิ่มได้ เช่น in-place implementation ซึ่ง hash table ทำไม่ได้เพราะจำเป็นต้องใช้ hash index table

ประโยชน์และการนำไปใช้

นำไปเป็นโครงสร้างข้อมูลสำหรับ Dictionary

เนื่องจาก Tries มีความยืดหยุ่นในการใช้ key จึงเหมาะที่จะนำไปใช้ทำ dictionary โดยมีจุดเด่นคือ

• key ไม่จำเป็นต้องเป็นแบบ exact match เราสามารถโปรแกรมให้ Trie สามารถแสดงผล key ที่ใกล้เคียงแทนได้
• สามารถโปรแกรมให้ Trie มีระบบ auto complete ได้โดยการใส่ prefix เริ่มต้นจำนวนหนึ่ง แล้วให้ Trie แสดง key ที่มีโหนดเป็น prefix ที่กำหนดได้ เช่น input:ca output:cat, catalog และ อื่นๆ

• ระบบ Auto complete

ใช้แทน Hash table

โดย Trie มีจุดเด่นที่เหนือกว่า Hash table คือ...

• ใช้เวลา Look Up เร็วกว่า
• ไม่มีการชนกันของ key
• ไม่ต้องมี hash function ในการค้นหา หรือ ต้องเปลี่ยน hash function เวลาข้อมูลเพิ่ม
• สามารถเรียงข้อมูลตามตัวอักษรตาม key ได้

แต่ก็มีข้อเสียคือ

• Trie อาจทำงานได้ช้ากว่า Hash Table ในกรณีที่ข้อมูลที่ค้นหาอยู่ในบริเวณที่มี access time > access time ของ main memory มากๆ
• บาง key เช่น เลขทศนิยม ทำให้เกิด sequence ยาวมาก และ prefix ที่ไม่สื่อความหมายอะไร อย่างไรก็ตาม เราสามารถใช้ Bitwise trie กับข้อมูลที่ key เป็นเลขทศนิยมตามมาตรฐาน IEEE single & double precision ได้

ใช้เซนเซอร์คำได้

ในกรณีที่มีศัพท์ที่ต้องการจะเซนเซอร์จำนวนมาก Trie จะมีจะประสิทธิภาพมากกว่าการเทียบ String ใน array มาก ถ้าให้ m = ความยาวของประโยคที่อาจมีคำที่ต้องเซนเซอร์อยู่ภายใน และ n = จำนวนคำที่ต้องการเซนเซอร์

• กรณีใช้ array เนื่องจากคำที่ต้องการเซนเซอร์สามารถเริ่มจากตำแหน่งไหนก็ได้ในประโยค ดังนั้นเราจึงต้องใช้การเปรียบเทียบ String ทั้งหมด m × n ครั้ง
• กรณีใช้ Trie เราจะค้นหา คำที่ต้องการเซนเซอร์อาจอยู่ในตำแหน่งไหนก็ได้ของประโยค (ตั้งแต่ 0 ถึง m-1) ดังนั้นเราจึงใช้การค้นหาใน trie เพียงจำนวน m ครั้ง