प्रत्यय पेड़ कैसे काम करते हैं?

Question

मैं डेटा संरचनाओं अध्याय के माध्यम से The Algorithm Design Manual में जा रहा हूं और सफ़िक्स पेड़ में आया हूं।

उदाहरण कहता है:

इनपुट:

XYZXYZ$ 
YZXYZ$ 
    ZXYZ$ 
    XYZ$ 
    YZ$ 
    Z$ 
     $ 

आउटपुट:

मैं समझने के लिए कि पेड़ दिए गए इनपुट स्ट्रिंग से उत्पन्न हो जाता है नहीं पा रहा हूँ। किसी दिए गए स्ट्रिंग में दिए गए सबस्ट्रिंग को खोजने के लिए प्रत्यय के पेड़ का उपयोग किया जाता है, लेकिन दिया गया पेड़ उस दिशा में कैसे मदद करता है? मैं नीचे दिखाए गए एक ट्राई का एक और उदाहरण समझता हूं, लेकिन यदि नीचे की त्रिभुज एक प्रत्यय पेड़ से संकलित हो जाती है, तो यह कैसा दिखता है?

Answer 1

एक प्रत्यय पेड़ के निर्माण के लिए मानक कुशल एल्गोरिदम निश्चित रूप से nontrivial हैं। ऐसा करने के लिए मुख्य एल्गोरिदम को Ukkonen के एल्गोरिदम कहा जाता है और दो अतिरिक्त ऑप्टमाइज़ेशन के साथ बेवकूफ एल्गोरिदम का एक संशोधन है। इसे बनाने के तरीके के विवरण के लिए आप this earlier question पढ़ने से शायद सबसे अच्छे हैं।

आप radix tries पर मानक प्रविष्टि एल्गोरिदम का उपयोग करते पेड़ में प्रत्येक प्रत्यय सम्मिलित करने के लिए, लेकिन ऐसा करने ले wlil समय O (n) है, जो बड़ी स्ट्रिंग्स के लिए महंगा हो सकता है द्वारा प्रत्यय के पेड़ का निर्माण कर सकते हैं।

तेजी से सबस्ट्रिंग खोज करने के लिए, याद रखें कि एक प्रत्यय पेड़ मूल स्ट्रिंग के सभी प्रत्यय (साथ ही कुछ विशेष अंत-स्ट्रिंग मार्कर) का संकुचित त्रिज्या है। यदि एक स्ट्रिंग एस प्रारंभिक स्ट्रिंग टी का एक सबस्ट्रिंग है और आपके पास टी के सभी प्रत्ययों का एक परीक्षण था, तो आप यह देखने के लिए केवल एक खोज कर सकते हैं कि टी उस ट्राई में किसी भी स्ट्रिंग का उपसर्ग है या नहीं। यदि ऐसा है, तो टी को एस का एक सबस्ट्रिंग होना चाहिए, क्योंकि इसके सभी वर्ण टी में अनुक्रम में मौजूद हैं। प्रत्यय पेड़ सबस्ट्रिंग खोज एल्गोरिदम ठीक है यह खोज संकुचित त्रिज्या पर लागू होती है, जहां आप प्रत्येक चरण में उपयुक्त किनारों का पालन करते हैं।

आशा है कि इससे मदद मिलती है!

Answer 2

एक प्रत्यय पेड़ मूल रूप से केवल एक साथ अक्षरों के रनों को चलाता है जब कोई विकल्प नहीं बनता है। उदाहरण के लिए, यदि आप w को देखने के बाद अपने प्रश्न में त्रिभुज के दाईं ओर देखते हैं, तो वास्तव में केवल दो विकल्प हैं: was और when। ट्राई में, aswas और henwhen में प्रत्येक के पास प्रत्येक पत्र के लिए अभी भी एक नोड है। एक प्रत्यय ट्री में, आप as और hen पकड़े दो नोड्स में एक साथ उन डाल चाहते हैं, तो अपने trie के दाईं ओर में बदल जाएगा:

Answer 3

मैं समझने के लिए कि नहीं पा रहा हूँ पेड़ दिए गए इनपुट स्ट्रिंग से उत्पन्न होता है।

आप अनिवार्य रूप से सूचीबद्ध सभी प्रत्ययों के साथ पेट्रीसिया ट्राई बनाते हैं। पेट्रीसिया ट्राई में डालने पर, आप इनपुट स्ट्रिंग से पहले चार से शुरू होने वाले बच्चे के लिए रूट खोजते हैं, यदि यह मौजूद है तो आप पेड़ को जारी रखते हैं लेकिन यदि ऐसा नहीं होता है तो आप रूट से नया नोड बनाते हैं।रूट में इनपुट स्ट्रिंग ($, ए, ई, एच, आई, एन, आर, एस, टी, डब्ल्यू) में अद्वितीय वर्णों के रूप में कई बच्चे होंगे। आप इनपुट स्ट्रिंग में प्रत्येक वर्ण के लिए उस प्रक्रिया को जारी रख सकते हैं।

सफ़िक्स पेड़ किसी दिए गए स्ट्रिंग में दिए गए सबस्ट्रिंग को खोजने के लिए उपयोग किए जाते हैं, लेकिन दिया गया पेड़ उस दिशा में कैसे मदद करता है?

यदि आप "मुर्गी" को प्रतिस्थापित करने की तलाश में हैं तो "एच" से शुरू होने वाले बच्चे के लिए रूट से खोजना शुरू करें। यदि बच्चे "एच" में स्ट्रिंग की लंबाई तब तक "एच" को संसाधित करना जारी रखती है जब तक कि आप स्ट्रिंग के अंत तक नहीं आते हैं या आपको इनपुट स्ट्रिंग और बच्चे "एच" स्ट्रिंग में वर्णों का मेल नहीं मिलता है। यदि आप सभी बच्चे "एच" से मेल खाते हैं, यानी इनपुट "हेन" बच्चे "एच" में "हे" से मेल खाता है तो "एच" के बच्चों तक आगे बढ़ें जब तक कि आप "एन" नहीं पहुंच जाते, अगर यह बच्चा शुरू करने में विफल रहता है "एन" के साथ तो सबस्ट्रिंग मौजूद नहीं है।

Compact Suffix Trie code:

└── (black) 
    ├── (white) as 
    ├── (white) e 
    │ ├── (white) eir 
    │ ├── (white) en 
    │ └── (white) ere 
    ├── (white) he 
    │ ├── (white) heir 
    │ ├── (white) hen 
    │ └── (white) here 
    ├── (white) ir 
    ├── (white) n 
    ├── (white) r 
    │ └── (white) re 
    ├── (white) s 
    ├── (white) the 
    │ ├── (white) their 
    │ └── (white) there 
    └── (black) w 
     ├── (white) was 
     └── (white) when 

Suffix Tree code:

String = the$their$there$was$when$ 
End of word character = $ 
└── (0) 
    ├── (22) $ 
    ├── (25) as$ 
    ├── (9) e 
    │ ├── (10) ir$ 
    │ ├── (32) n$ 
    │ └── (17) re$ 
    ├── (7) he 
    │ ├── (2) $ 
    │ ├── (8) ir$ 
    │ ├── (31) n$ 
    │ └── (16) re$ 
    ├── (11) ir$ 
    ├── (33) n$ 
    ├── (18) r 
    │ ├── (12) $ 
    │ └── (19) e$ 
    ├── (26) s$ 
    ├── (5) the 
    │ ├── (1) $ 
    │ ├── (6) ir$ 
    │ └── (15) re$ 
    └── (29) w 
     ├── (24) as$ 
     └── (30) hen$