รื้อฟื้นความหลัง กลับไปทบทวน Trie (Data Structure)

สวัสดีผู้อ่านทุกท่านนะครับ เนื่องจากว่าช่วงนี้ผมกำลังอยู่ในช่วงคิดถึงความหลัง ทบทวนเรื่องเก่า ๆ อย่าง Data structure อยู่ แบบว่าพอทำอะไรไปมาก ๆ ก็คิดถึงเรื่อง Performance ของระบบขึ้นมา ก็เลยต้องกลับไปทบทวน 😂 คราวนี้ก็ไปเอะใจกับตัว Trie ขึ้นมา เพราะตอนที่เป็นนักศึกษาไม่เคยเจอเรื่องนี้ เคยได้ยินอยู่บ้าง แต่ไม่เคยลองทดลองทำอะไร ตอนนี้ก็เลยเป็นโอกาสเหมาะที่จะลองแชร์อะไรเล็ก ๆ น้อย ๆ จากการศึกษาครั้งนี้นะครับ

“ ขอกลับไปทบทวนเนื้อหา Fundamental บทความนึงนะ 😆 ”

โดยก่อนที่จะไปพูดถึงเรื่อง Trie ก็อยากจะอธิบายเกี่ยวกับ Tree แบบสั้น ๆ เพื่อที่จะไปต่อยอดกับเนื้อหา Trie นะครับ

Tree 🌳

โครงสร้างต้นไม้ เป็นโครงสร้างข้อมูลที่มีความสัมพันธ์กันแบบลำดับชั้น (Hierarchical Relationship) โดย Tree เป็น Graph ชนิดหนึ่งที่ต่อเนื่องกันไม่มีวงจรปิด (Node ปลายทางสามารถย้อนกลับไปที่ Node แรกได้โดยตรง)
คอนเซ็ปต์ของ Tree ตัว Node 2 Node ใด ๆ จะเชื่อมต่อกันในทิศทางเดียวเท่านั้น

Components of Tree

• Root : เป็นชื่อเรียกของ Node ที่อยู่ระดับบนสุด (ราก)
• Parent : โหนดที่เป็นต้นกำเนิดของ Node อื่น
• Child : โหนดที่เกิดจาก Node อื่น
• Leaf : เป็นชื่อเรียกของ Node ที่อยู่ลำดับสุดท้าย ที่ไม่มี Child ลงไปอีก (ใบ)
• Siblings : เป็นกลุ่มของ Node ที่มี parent เดียวกัน และอยู่ลำดับเลเวลเดียวกัน
• Level : ความลึกของต้นไม้ โดยจะดูจากเลเวลของ Leaf Node ที่ลึกที่สุดภายในต้นไม้
• จำนวน Node ทั้งหมด หาได้จาก 2^(level+1)-1
• จำนวนของ Branch ก็คือ จำนวนโหนด-1

General Tree

General Tree

ต้นไม้ที่ทุกโหนดจะมีดีกรีตั้งแต่ 0 ขึ้นไป

เปรียบเทียบให้เห็นภาพก็จะเหมือน File System ของคอมพิวเตอร์

Binary Tree

Binary Tree

ต้นไม้ที่ทุกโหนดจะมีดีกรีน้อยกว่าหรือเท่ากับ 2

เป็นเคสพิเศษ เป็น Subset ของ General Tree

Trie 🌲

โครงสร้างต้นไม้รูปแบบ Ordered Tree ที่แต่ละ Node จะจัดเก็บ ตัวอักษร เอาไว้และมีความสัมพันธ์กับ Node ลำดับ level ถัดไป
string หรือ wording จะสามารถเรียกไปใช้ได้ โดยการท่องเข้าไปใน Trie

Example of Trie

Trie จะถูกนำไปใช้ในจำพวกของ Dictionary, คลังคำศัพท์ หรืออยู่ในระบบค้นหา Search Engine

แนวคิดของ Trie

• ทำงานในรูปแบบของ Prefix tree
• เก็บคำนำหน้าแต่ละตัวอักษร ตามลำดับเลเวล
  เช่น “THE” (T = level 0, H = level 1, E = level 2)ca
• ค่า value ใน Root Node จะว่างเสมอ (โดย implement เป็นกลุ่ม children แทน เพื่อบอกความสัมพันธ์ว่า เชื่อมกับ key ไหนไว้)
• ค่า Big O โดยเฉลี่ยจะอยู่ที่ O(log n) เนื่องจาก โครงสร้างเป็นรูปแบบ Tree

หลังจากอัดเนื้อหากันไปบ้างแล้ว ต่อมาจะมาลอง implement แนวคิดลงบนโค้ดของเรากันบ้าง

ตัวอย่าง Code จะถูกเขียนโดยภาษา Javascript (Node.js)

Trie code

จากตัวโค้ดผมได้ทำการลอง Implement ให้ตัว Trie มีหน้าตาประมาณนี้

ตัว Attribute ใน Node ใช้ 2 key คือ

1. isEndOfWord : เป็น Flag ที่บอกว่า จบ Wording แล้ว
2. children : Array ของความสัมพันธ์ในลำดับถัดไป (ถ้าไม่มีจะใส่ค่า null ไว้)

ตัว function ที่ลอง implement มี 2 functions คือ

• insert
  ผมใช้หลักการของ Pointer คือสร้างตัวแปร crawler ขึ้นมาเพื่อไล่ไปทีละลำดับ จุดตั้งต้นจะอยู่ที่ Root Node ทำการเปรียบเทียบแต่ละตัวอักษรเพื่อหา Index ที่จะทำการสร้างลำดับชั้น level ถัดไป และจะ Mark flag จบ wording ด้วย key ที่ชื่อว่า isEndOfWord
• search
  ใช้หลักการเดียวกับ insert ที่จะใช้ Pointer ในการไล่ Traverse เข้าไปใน Tree แต่จะไว้ใช้ดูผลลัพธ์ หลังจากค้นหาครบทุกตัวอักษรแล้ว ถ้า crawler มีค่าและ isEndOfWord เป็นจริง จะรีเทิร์นผลลัพธ์เป็น True (คือค้นเจอคำนี้นั่นเอง)

หลังจากนั้นก็มาลองรันโปรแกรมของเรากันเลย ~

ผลลัพธ์จากการรันโปรแกรม Trie

หลังจากลอง ทดสอบสำเร็จไปแล้ว ก็สงสัยว่า “เอ๊ะ ตรงนี้เราสามารถลองทำอะไรแบบอื่นได้อีกไหมนะ 🤔” ก็เลยงั้นลองเปลี่ยนจากแนวคิด Index of array เป็น key/value แทน โดยรอบนี้จะให้ตัว children เก็บเป็น key of characters แทน โดยหลังจากลองทำ หน้าตาของโค้ดก็ออกมาประมาณนี้

Trie code version 2

ผลลัพธ์จากการรันโปรแกรม Trie เวอร์ชันดัดแปลง

จะเห็นว่าจะใช้ process time น้อยกว่าเล็กน้อยก็จริง แต่ทว่าในชั่วขณะนั้น อาจจะเป็นที่ตัวคอมพิวเตอร์ของเราก็ได้ที่ส่งผลต่อ timing ดังนั้นก็เลยสันนิษฐานว่า การลอง refactor รอบนี้ ทำได้แค่เปลี่ยนแนวคิด แต่การลด process time นั้นไม่ชัวร์ว่ามันลดลงจริงรึเปล่า 😥

และเราสามารถเปลี่ยนแปลง Logic ของการค้นหาได้ด้วย จากตัวโค้ดจะเห็นว่าผลลัพธ์การทำงาน คำนั้นจะต้องถูกเป๊ะ ๆ ทุกตัวอักษรถึงจะค้นเจอผลลัพธ์ ดังนั้นถ้าหากอยากจะเป็นการค้นหาตามตัวอักษรขึ้นต้น ก็อาจจะมีการเปลี่ยนแปลงส่วนนี้หน่อยนึง และอาจจะมี Recursion ซักเล็กน้อย

Example Code

marttp/sample-trie-nodejs

สำหรับบทความนี้คาดว่าคงจะเหมาะกับคนที่กำลังค้นคว้า และกำลังศึกษาเกี่ยวกับรายวิชา Data structure & Algorithms เพราะผมคิดว่าหลายคนอาจจะเรียนรู้เรื่อง Tree, Binary Search Tree และ Heap Tree มา และหลายคน (เช่นเจ้าของบล๊อกนี้) ที่ไม่ได้เรียนเรื่อง Trie มา แต่ต้องมาศึกษาเอง

มุมมองผมการย้อนกลับมาศึกษาแบบนี้ ก็เป็นเรื่องดีเหมือนกันนะ ทำให้รู้ว่าเรายังสามารถทำให้ตัวเองมีคุณภาพที่ดีมากยิ่งขึ้น และโค้ดในอนาคตของเรา หวังว่ามันจะดีขึ้นด้วยนะ 55555555555 🤣🤣🤣

ไว้เจอกันใหม่ Blog หน้าครับ ✌😁