โครงสร้างข้อมูล Trie: อัญมณีที่ถูกทอดทิ้ง

ตั้งแต่วันแรกในชีวิตในฐานะโปรแกรมเมอร์ เราทุกคนต่างต้องรับมือกับโครงสร้างข้อมูล: อาร์เรย์ รายการที่เชื่อมโยง ทรี ชุด สแต็ค และคิวคือคู่หูในชีวิตประจำวันของเรา และโปรแกรมเมอร์ที่มีประสบการณ์รู้ว่าควรใช้เมื่อใดและเพราะเหตุใด ในบทความนี้ เราจะมาดูกันว่าโครงสร้างข้อมูลที่ถูกละเลย trie นั้นโดดเด่นเพียงใดในโดเมนของแอปพลิเคชันพร้อมคุณสมบัติเฉพาะ เช่น เกมคำศัพท์

เกมคำศัพท์เป็นตัวอย่างทดลอง

ขั้นแรก ให้พิจารณาปริศนาคำศัพท์ง่ายๆ: ค้นหาคำที่ถูกต้องทั้งหมดในกระดานตัวอักษรขนาด 4x4 เชื่อมต่อตัวอักษรที่อยู่ติดกันในแนวนอน แนวตั้ง หรือแนวทแยงมุม ตัวอย่างเช่น ในกระดานต่อไปนี้ เราเห็นตัวอักษร 'W', 'A', 'I' และ 'T' เชื่อมต่อกันเพื่อสร้างคำว่า "WAIT"

วิธีแก้ปัญหาที่ไร้เดียงสาในการค้นหาคำที่ถูกต้องทั้งหมดคือการสำรวจกระดานโดยเริ่มจากมุมซ้ายบนแล้วย้ายความลึกก่อนไปยังลำดับที่ยาวขึ้น โดยเริ่มจากตัวอักษรตัวที่สองในแถวแรกอีกครั้ง เป็นต้น ในบอร์ด 4x4 ที่อนุญาตให้เคลื่อนที่ในแนวตั้ง แนวนอน และแนวทแยง มีลำดับ 12029640 เรียงตามความยาวตั้งแต่หนึ่งถึงสิบหกอักขระ

ตอนนี้ เป้าหมายของเราคือการค้นหาโครงสร้างข้อมูลที่ดีที่สุดเพื่อใช้ตัวตรวจสอบคำที่ถูกต้อง กล่าวคือ คำศัพท์ของเรา ข้อควรจำบางประการ:

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

เพื่ออธิบายประเด็นที่สอง ให้พิจารณากระดานต่อไปนี้: ไม่มีประเด็นใดที่จะสำรวจการเคลื่อนไหวครั้งต่อๆ ไป เนื่องจากไม่มีคำในพจนานุกรมที่ขึ้นต้นด้วย “ASF”

เราอยากให้โครงสร้างข้อมูลของเราตอบคำถามเหล่านี้โดยเร็วที่สุด ~O(1) เวลาเข้าถึง (สำหรับตรวจสอบลำดับ) จะเหมาะที่สุด!

เราสามารถกำหนดอินเทอร์เฟซคำศัพท์ได้ (ดูที่นี่สำหรับ GitHub repo):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

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

การใช้เมธอด contain( contains() ต้องใช้โครงสร้างข้อมูลสำรองที่ช่วยให้คุณค้นหาองค์ประกอบได้อย่างมีประสิทธิภาพ ในขณะที่ isPrefix() กำหนดให้เราต้องค้นหา "องค์ประกอบที่ใหญ่กว่าถัดไป" กล่าวคือ เราจำเป็นต้องจัดเรียงคำศัพท์ด้วยวิธีใดวิธีหนึ่ง

เราสามารถแยกชุดที่ใช้ hash-based ออกจากรายชื่อผู้สมัครได้อย่างง่ายดาย: ในขณะที่โครงสร้างดังกล่าวจะทำให้เราตรวจสอบตลอดเวลาสำหรับ contain( contains() มันจะทำงานได้ค่อนข้างแย่ใน isPrefix() ในกรณีที่เลวร้ายที่สุดคือเราต้องสแกนทั้งชุด ชุด.

ด้วยเหตุผลที่ค่อนข้างตรงกันข้าม เรายังสามารถแยกรายการลิงก์ที่เรียงลำดับได้ เนื่องจากต้องสแกนรายการอย่างน้อยจนถึงองค์ประกอบแรกที่มากกว่าหรือเท่ากับคำหรือคำนำหน้าที่ค้นหา

สองตัวเลือกที่ใช้ได้กำลังใช้รายการที่เรียงลำดับจากอาร์เรย์สำรองหรือไบนารีทรี
ในรายการอาร์เรย์สำรองที่เรียงลำดับแล้ว เราสามารถใช้การค้นหาแบบไบนารีเพื่อค้นหาลำดับปัจจุบันหากมีอยู่หรือองค์ประกอบที่มากกว่าถัดไปที่ราคา O(log2(n)) โดยที่ n คือจำนวนคำในพจนานุกรม

เราสามารถใช้คำศัพท์ที่ได้รับการสนับสนุนจากอาร์เรย์ซึ่งจะรักษาการเรียงลำดับเช่นนี้ไว้เสมอ โดยใช้ java.util.ArrayList มาตรฐาน และ java.util.Collections.binarySeach :

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

หากเราตัดสินใจใช้ไบนารีทรี การใช้งานอาจสั้นลงและสวยงามยิ่งขึ้น (อีกครั้ง นี่คือลิงก์ไปยังโค้ด):

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

ในทั้งสองกรณี เราสามารถคาดหวังประสิทธิภาพของ O(log n) สำหรับแต่ละวิธีการเข้าถึง ( contain( contains() และ isPrefix() ) สำหรับข้อกำหนดด้านพื้นที่ ทั้งการใช้งานอาร์เรย์สำรองและการใช้งานแบบทรีแบ็คจำเป็นต้องมี O(n+M) โดยที่ n คือจำนวนคำในพจนานุกรม และ M คือขนาดไบต์ของพจนานุกรม กล่าวคือ ผลรวมของความยาวของ สตริงในพจนานุกรม

แอปพลิเคชัน Trie: เมื่อใดและเหตุใดจึงควรใช้ Tries

ประสิทธิภาพลอการิทึมและหน่วยความจำเชิงเส้นไม่เลว แต่ยังมีคุณลักษณะอื่นๆ อีกสองสามประการของโดเมนแอปพลิเคชันของเราที่สามารถนำเราไปสู่ประสิทธิภาพที่ดีขึ้นได้:

• เราสามารถสรุปได้อย่างปลอดภัยว่าทุกคำเป็นตัวพิมพ์เล็ก
• เรารับเฉพาะตัวอักษร az เท่านั้น ไม่มีเครื่องหมายวรรคตอน ไม่มีขีดกลาง ไม่มีเครื่องหมายเน้นเสียง ฯลฯ
• พจนานุกรมประกอบด้วยรูปแบบผันแปรหลายรูปแบบ: พหูพจน์ กริยาผัน คำประกอบ (เช่น บ้าน –> แม่บ้าน) ดังนั้น หลายคำจึงมีต้นกำเนิดเดียวกัน
• คำมีความยาวจำกัด ตัวอย่างเช่น หากเรากำลังทำงานกับบอร์ด 4x4 คำทั้งหมดที่ยาวเกิน 16 ตัวอักษรสามารถทิ้งได้

นี่คือที่มาของ trie (ออกเสียงว่า "try") แต่จริงๆ แล้ว trie คือ อะไรกันแน่? ความพยายามเป็นโครงสร้างข้อมูลที่ถูกละเลย ซึ่งพบในหนังสือ แต่ไม่ค่อยพบในห้องสมุดมาตรฐาน

สำหรับแรงจูงใจ อันดับแรก ให้พิจารณาลูกโปสเตอร์ของวิทยาการคอมพิวเตอร์: ต้นไม้ไบนารี ตอนนี้ เมื่อเราวิเคราะห์ประสิทธิภาพของไบนารีทรีและบอกว่า operation x คือ O(log(n)) เรากำลังพูดถึง log ฐาน 2 อยู่ตลอดเวลา แต่ถ้าเราใช้ ternary tree แทนไบนารีทรีล่ะ ทุกโหนดมีลูกสามคน (หรือแฟนจากสามคน) จากนั้น เรากำลังพูดถึงบันทึกฐาน 3 (นั่นคือการปรับปรุงประสิทธิภาพ แม้ว่าจะมีเพียงปัจจัยคงที่เท่านั้น) โดยพื้นฐานแล้ว ต้นไม้ของเราจะกว้างขึ้นแต่สั้นลง และเราสามารถทำการค้นหาน้อยลงเนื่องจากเราไม่ต้องลงมาเลย ลึกมาก.

ก้าวไปอีกขั้น ถ้าเรามีต้นไม้ที่มีการกระจายเท่ากับจำนวนค่าที่เป็นไปได้ของประเภทข้อมูลของเรา

นี่คือแรงจูงใจเบื้องหลังการทดลอง และอย่างที่คุณอาจเดาได้แล้วว่า Trie นั้นเป็นต้นไม้จริง ๆ จริงๆ แล้ว Trie ก็คือต้นไม้ Trie นั่นเอง!

แต่ตรงกันข้ามกับไบนารีทรีส่วนใหญ่ที่คุณใช้สำหรับการเรียงลำดับสตริง ที่เก็บคำทั้งหมดไว้ในโหนดของพวกเขา แต่ละโหนดของ trie มีอักขระตัวเดียว (และไม่ใช่เช่นนั้น อย่างที่เราจะเห็นในเร็วๆ นี้) และ มีการกระจายสูงสุดเท่ากับความยาวของตัวอักษร ในกรณีของเรา ความยาวของตัวอักษรคือ 26; ดังนั้นโหนดของ trie จึงมี fan-out สูงสุดที่ 26 และในขณะที่ไบนารีทรีที่สมดุลมี log2(n) ความลึก ความลึกสูงสุดของ trie จะเท่ากับความยาวสูงสุดของคำ! (อีกครั้งกว้างขึ้น แต่สั้นลง)

ภายในการทดลอง คำที่มีต้นกำเนิดเดียวกัน (คำนำหน้า) แบ่งพื้นที่หน่วยความจำที่สอดคล้องกับต้นกำเนิด

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

การใช้งาน Java Trie

ดังที่เราทราบ ในแผนผังนั้น ตัวชี้ไปยังองค์ประกอบลูกมักจะใช้กับตัวแปรซ้ายและขวา เนื่องจากการกระจายสูงสุดคงที่ที่สองตัว

ในการพยายามสร้างดัชนีตัวอักษร 26 ตัว แต่ละโหนดมีลูกที่เป็นไปได้ 26 ตัว ดังนั้นจึงมีตัวชี้ที่เป็นไปได้ 26 ตัว แต่ละโหนดจึงมีอาร์เรย์ของทรีย่อย 26 (ตัวชี้ไปยัง) ซึ่งแต่ละค่าอาจเป็นโมฆะ (หากไม่มีลูกดังกล่าว) หรือโหนดอื่น

แล้วเราจะค้นหาคำในการทดลองได้อย่างไร? นี่คือวิธีการที่ ให้ String s จะระบุโหนดที่สอดคล้องกับอักษรตัวสุดท้ายของคำ หากมีอยู่ในทรี:

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

LOWERCASE.getIndex(s.charAt(i)) วิธีการจะคืนค่าตำแหน่งของอักขระ ith ในตัวอักษร บนโหนดที่ส่งคืน node คุณสมบัติบูลีนระบุว่าโหนดนั้นสอดคล้องกับตัวอักษรสุดท้ายของคำ กล่าวคือ ตัวอักษรที่มีเครื่องหมายสีแดงในตัวอย่างก่อนหน้านี้ เนื่องจากแต่ละโหนดเก็บตัวนับจำนวนลูกไว้ หากตัวนับนี้เป็นค่าบวก พจนานุกรมจะมีคำที่ยาวกว่าที่มีสตริงปัจจุบันเป็นคำนำหน้า หมายเหตุ: โหนดไม่จำเป็นต้องอ้างอิงถึงอักขระที่สัมพันธ์กันจริง ๆ เพราะมันอยู่ในตำแหน่งโดยนัยในการทดสอบ

กำลังวิเคราะห์ประสิทธิภาพ

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

ในโดเมนเฉพาะของเรา เนื่องจากเรามีสตริงที่มีความยาวไม่เกิน 16 อักขระ จึงจำเป็น 16 ขั้นตอนในการค้นหาคำที่อยู่ในคำศัพท์ ในขณะที่คำตอบเชิงลบใดๆ เช่น คำหรือคำนำหน้าไม่ได้อยู่ในไตรภาคก็สามารถหาได้ ไม่เกิน 16 ขั้นตอนเช่นกัน! เมื่อพิจารณาว่าก่อนหน้านี้เราได้ละเว้นความยาวของสตริงเมื่อคำนวณความซับซ้อนของเวลาทำงานสำหรับทั้งรายการที่เรียงลำดับตามอาร์เรย์และแผนผังซึ่งซ่อนอยู่ในการเปรียบเทียบสตริง เราสามารถละเว้นที่นี่และระบุได้อย่างปลอดภัยว่าการค้นหาเสร็จสิ้น ใน O(1) เวลา

เมื่อพิจารณาถึงข้อกำหนดด้านพื้นที่ (และจำได้ว่าเราได้ระบุขนาดไบต์ของพจนานุกรมด้วย M ) กลุ่มทดลองอาจมีโหนด M ในกรณีที่เลวร้ายที่สุด ถ้าไม่มีสองสตริงร่วมกันคำนำหน้า แต่เนื่องจากเราสังเกตว่าพจนานุกรมมีความซ้ำซ้อนในระดับสูง จึงมีการบีบอัดจำนวนมากที่ต้องทำ พจนานุกรมภาษาอังกฤษที่ใช้ในโค้ดตัวอย่างคือ 935,017 ไบต์และต้องใช้โหนด 250,264 โดยมีอัตราการบีบอัดประมาณ 73%

อย่างไรก็ตาม ถึงกระนั้นก็ตาม การบีบอัดข้อมูลมักจะต้องการหน่วยความจำมากกว่าทรีหรืออาร์เรย์ เนื่องจากในแต่ละโหนดจำเป็นต้องมีไบต์ sizeof(pointer) อย่างน้อย 26 x บวกกับโอเวอร์เฮดสำหรับอ็อบเจ็กต์และแอตทริบิวต์เพิ่มเติม บนเครื่อง 64 บิต แต่ละโหนดต้องการมากกว่า 200 ไบต์ ในขณะที่อักขระสตริงต้องการไบต์เดียว หรือสองไบต์ หากเราพิจารณาสตริง UTF

การทดสอบและการทดสอบประสิทธิภาพ

แล้วประสิทธิภาพล่ะ? การใช้งานคำศัพท์ได้รับการทดสอบในสองสถานการณ์ที่แตกต่างกัน: ตรวจสอบสตริงสุ่ม 20,000,000 ชุดและค้นหาคำศัพท์ทั้งหมดในกระดาน 15,000 รายการที่สร้างแบบสุ่มจากรายการคำศัพท์เดียวกัน

มีการวิเคราะห์โครงสร้างข้อมูลสี่โครงสร้าง: รายการที่เรียงตามอาร์เรย์สำรอง, ไบนารีทรี, ทรีที่อธิบายข้างต้น และชุดทดลองที่ใช้อาร์เรย์ไบต์ที่สัมพันธ์กับดัชนีตัวอักษรของอักขระด้วยกันเอง นี่คือผลลัพธ์ในหน่วยมิลลิวินาที:

จำนวนการเคลื่อนไหวเฉลี่ยในการแก้กระดานคือ 2,188 สำหรับการย้ายแต่ละครั้ง การค้นหาคำและการค้นหาคำนำหน้าจะเสร็จสิ้น กล่าวคือ สำหรับการตรวจสอบกระดานทั้งหมด มีการค้นหาคำมากกว่า 32 ล้านคำและการค้นหาคำนำหน้า 32 ล้านคำ หมายเหตุ: สิ่งเหล่านี้สามารถทำได้ในขั้นตอนเดียว ฉันแยกมันออกจากกันเพื่อความชัดเจนในการอธิบาย การอัดให้แน่นในขั้นตอนเดียวจะช่วยลดเวลาในการแก้กระดานได้เกือบครึ่งหนึ่ง และน่าจะชอบการทดลองนี้มากกว่า

ดังที่เห็นด้านบนนี้ การค้นหาคำทำงานได้ดีขึ้นกับ trie แม้ในขณะที่ใช้สตริง และเร็วกว่าเมื่อใช้ดัชนีตัวอักษร โดยตัวหลังจะทำงานเร็วกว่าไบนารีทรีมาตรฐานมากกว่าสองเท่า ความแตกต่างในการแก้ปัญหากระดานนั้นชัดเจนยิ่งขึ้น โดยโซลูชันดัชนีตัวอักษรสามตัวที่รวดเร็วนั้นเร็วกว่ารายการและแผนผังมากกว่าสี่เท่า

ห่อ

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

อ้างอิง

คำอธิบายโดยละเอียดเกี่ยวกับการพยายามและตัวอักษรสามารถพบได้ในบทที่ 5 ของหนังสือ "Algorithms, 4th edition" ของ Robert Sedgewick เว็บไซต์ร่วมที่ Princeton มีรหัสสำหรับการติดตั้งใช้งานของ Alphabet และ TrieST ที่กว้างขวางกว่าตัวอย่างของฉัน

คำอธิบายการทดลองและการนำไปใช้สำหรับภาษาต่างๆ ยังสามารถพบได้ใน Wikipedia และคุณสามารถดูแหล่งข้อมูลการทดลองใช้ของมหาวิทยาลัยบอสตันได้เช่นกัน