fbpx
วิกิพีเดีย

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

สิงหาคม 08, 2021

ที่มา

มาจากคำว่า 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 ครั้ง

สิงหาคม 08, 2021
ทร, โครงสร, างข, อม, บทความน, อาจต, องเข, ยนใหม, งหมดเพ, อให, เป, นไปตามมาตรฐานค, ณภาพของว, เด, หร, อกำล, งดำเน, นการอย, ณช, วยเราได, หน, าอภ, ปรายอาจม, อเสนอแนะเน, อหา, มา, แนวค, อด, เม, อเท, ยบก, บโครงสร, างข, อม, ลอ, นๆ, อด, เม, อเท, ยบก, อด, เม, อเท, ยบก, . bthkhwamnixactxngekhiynihmthnghmdephuxihepniptammatrthankhunphaphkhxngwikiphiediy hruxkalngdaeninkarxyu khunchwyeraid hnaxphiprayxacmikhxesnxaenaenuxha 1 thima 2 aenwkhid 3 khxdiemuxethiybkbokhrngsrangkhxmulxun 3 1 khxdiemuxethiybkb BST 3 2 khxdiemuxethiybkb Hash Table 4 praoychnaelakarnaipich 4 1 naipepnokhrngsrangkhxmulsahrb Dictionary 4 2 ichaethn Hash table 4 2 1 aetkmikhxesiykhux 4 3 ichesnesxrkhaidthima aekikhmacakkhawa Retrieval sungtamthimacaxankhxng thri tamphuxxkaebb data structure ni aetbangkhnkxanwa thry aenwkhid aekikhTrie hruxeriykxikxyangwa prefix tree khux okhrngsrangkhxmulaebb ordered tree mkichekb associative array thimi key epn String sungcatangcak BST Binary Search Tree trngthiinaetlaohndkhxng BST caekb key ephuxexaiwthakarepriybethiyb ody node khxng Trie caimekb key iw aettaaehnngkhxng node nn tree cabxkwa node echuxmkb key ihnaethn odymiraylaexiyddngni ohndlukcami prefix khxng string thikahndinohmdphx ohndphinxngthangsaycamikhanxykwaohndphinxngthangkhwa echn a b c ohndrakechuxmkb String wang eraimcaepntxngkahnd value ihthukohnderacasnicechphaaohndib hrux ohndphayinbangohndthisnicethann okhrngsrangkhxng Trie karkhnhain Triekhxdiemuxethiybkbokhrngsrangkhxmulxun aekikhkhxdiemuxethiybkb BST aekikh ih m khwamyawkhxng key n canwnkhxmul ichewlakhnhaerwkwa odymi worst case O m sungcaphbwacanwn node phayinimmiphltxkhwamerwinkarkhnha tangkb BST thiichcanwnkhrnginkarepriybethiyb O log n sung worst case catxngethiybethakb O m log n macakcanwnkhrngthiepriybethiyb key canwntwxksrin key prahydphunthi tha key epn string sncanwnmak ephraawa key imidthukekbepn string etm aetcathukekbepn subsequence thimi prefix aebbediywkn samarthkhnha Longest prefix matching id ody key imcaepntxngepnaebb exact matchkhxdiemuxethiybkb Hash Table aekikh key imcaepntxngepntrngkbsingthikhnhathnghmd exact match samarthkhnha key thiiklekhiyngthisudid aenwonmprasiththiphaphinkarephimkhxmulerwkwa ephraasamarthephimkhxmulideruxyimcaepntxngthangan rehash samarth implement ihhlikeliyngkarich memory ephimid echn in place implementation sung hash table thaimidephraacaepntxngich hash index tablepraoychnaelakarnaipich aekikhnaipepnokhrngsrangkhxmulsahrb Dictionary aekikh enuxngcak Tries mikhwamyudhyuninkarich key cungehmaathicanaipichtha dictionary odymicudednkhux key imcaepntxngepnaebb exact match erasamarthopraekrmih Trie samarthaesdngphl key thiiklekhiyngaethnid samarthopraekrmih Trie mirabb auto complete idodykaris prefix erimtncanwnhnung aelwih Trie aesdng key thimiohndepn prefix thikahndid echn input ca output cat catalog aela xun rabb Auto completeichaethn Hash table aekikh ody Trie micudednthiehnuxkwa Hash table khux ichewla Look Up erwkwa immikarchnknkhxng key imtxngmi hash function inkarkhnha hrux txngepliyn hash function ewlakhxmulephim samartheriyngkhxmultamtwxksrtam key idaetkmikhxesiykhux aekikh Trie xacthanganidchakwa Hash Table inkrnithikhxmulthikhnhaxyuinbriewnthimi access time gt access time khxng main memory mak bang key echn elkhthsniym thaihekid sequence yawmak aela prefix thiimsuxkhwamhmayxair xyangirktam erasamarthich Bitwise trie kbkhxmulthi key epnelkhthsniymtammatrthan IEEE single amp double precision idichesnesxrkhaid aekikh inkrnithimisphththitxngkarcaesnesxrcanwnmak Trie camicaprasiththiphaphmakkwakarethiyb String in array mak thaih m khwamyawkhxngpraoykhthixacmikhathitxngesnesxrxyuphayin aela n canwnkhathitxngkaresnesxr krniich array enuxngcakkhathitxngkaresnesxrsamartherimcaktaaehnngihnkidinpraoykh dngnneracungtxngichkarepriybethiyb String thnghmd m n khrng krniich Trie eracakhnha khathitxngkaresnesxrxacxyuintaaehnngihnkidkhxngpraoykh tngaet 0 thung m 1 dngnneracungichkarkhnhain trie ephiyngcanwn m khrngekhathungcak https th wikipedia org w index php title thry okhrngsrangkhxmul amp oldid 7617981, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม