प्रत्यय पेड़

Question

से सबस्ट्रिंग में सबसे लंबी दोहराने वाली स्ट्रिंग कैसे प्राप्त करें मुझे सबस्ट्रिंग में सबसे लंबी दोहराने वाली स्ट्रिंग को खोजने की आवश्यकता है। मान लीजिए कि मैं स्ट्रिंग "bannana"

विकिपीडिया says है निम्नलिखित हैं:

कंप्यूटर विज्ञान में, सबसे लंबे समय तक बार-बार-स्ट्रिंग समस्या एक स्ट्रिंग है से कम दो बार पर होता है की सबसे लंबी स्ट्रिंग पाने की समस्या है। स्ट्रिंग "ATCGATCGA $", सबसे लंबे समय तक दोहराया सबस्ट्रिंग है "ATCGA" के साथ चित्र में

तो मुझे लगता है कि स्ट्रिंग "bannana" के लिए वहाँ दो समान रूप से लंबे समय से सबस्ट्रिंग (यदि नहीं मुझे सही करें) कर रहे हैं: "an" और "na" ।

विकिपीडिया भी says कि इस उद्देश्य के लिए प्रत्यय पेड़ का उपयोग किया जाता है। अधिक विशिष्ट होना करने के लिए here उद्धरण इसे कैसे करना है (इस wikipedia पर परिभाषा की तुलना में अधिक understable मुझे लगता है):

एक प्रत्यय पेड़ का निर्माण, तो कम से कम 2 वंश के साथ उच्चतम नोड पाते हैं।

मुझे प्रत्यय पेड़ों के कई कार्यान्वयन मिल गए हैं। निम्नलिखित कोड here से लिया जाता है:

use strict; 
use warnings; 
use Data::Dumper; 

sub classify { 
    my ($f, $h) = (shift, {}); 
    for (@_) { push @{$h->{$f->($_)}}, $_ } 
    return $h; 
} 
sub suffixes { 
    my $str = shift; 
    map { substr $str, $_ } 0 .. length($str) - 1; 
} 
sub suffix_tree { 
    return +{} if @_ == 0; 
    return +{ $_[0] => +{} } if @_ == 1; 
    my $h = {}; 
    my $classif = classify sub { substr shift, 0, 1 }, @_; 
    for my $key (sort keys %$classif) { 
     my $subtree = suffix_tree(
      grep "$_", map { substr $_, 1 } @{$classif->{$key}} 
     ); 
     my @subkeys = keys %$subtree; 
     if (@subkeys == 1) { 
      my $subkey = shift @subkeys; 
      $h->{"$key$subkey"} = $subtree->{$subkey}; 
     } else { $h->{$key} = $subtree } 
    } 
    return $h; 
} 

print +Dumper suffix_tree suffixes 'bannana$'; 

स्ट्रिंग "bannana" के लिए

यह निम्नलिखित रिटर्न पेड़:

$VAR1 = { 
      '$' => {}, 
      'n' => { 
        'a' => { 
          'na$' => {}, 
          '$' => {} 
          }, 
        'nana$' => {} 
       }, 
      'a' => { 
        '$' => {}, 
        'n' => { 
          'a$' => {}, 
          'nana$' => {} 
          } 
       }, 
      'bannana$' => {} 
     }; 

एक और कार्यान्वयन है here से ऑनलाइन, स्ट्रिंग "bannana" के लिए यह पेड़ निम्नलिखित रिटर्न:

7: a 
5: ana 
2: annana 
1: bannana 
6: na 
4: nana 
3: nnana 

    |(1:bannana)|leaf 
tree:| 
    |  |(4:nana)|leaf 
    |(2:an)| 
    |  |(7:a)|leaf 
    | 
    |  |(4:nana)|leaf 
    |(3:n)| 
    |  |(5:ana)|leaf 
3 branching nodes 

प्रश्न:

1. मैं उन ग्राफों से कैसे प्राप्त कर सकता हूं "an" और "na" स्ट्रिंग्स?
2. जैसा कि आप देख सकते हैं कि पेड़ अलग हैं, क्या वे बराबर हैं या नहीं, यदि हां क्यों वे अलग हैं, तो कौन सा एल्गोरिदम सही नहीं है?
3. यदि पर्ल कार्यान्वयन गलत है तो क्या पर्ल/पायथन के लिए कोई कामकाजी कार्यान्वयन है?
4. मैंने Ukkonen के एल्गोरिदम के बारे में पढ़ा है जिसका पृष्ठ पर दूसरे उदाहरण के साथ भी उल्लेख किया गया है (यदि ऑनलाइन संस्करण इस एल्गोरिदम का उपयोग कर रहा है या नहीं), तो इस एल्गोरिदम का उपयोग करने वाले किसी भी उल्लेख किए गए उदाहरणों में से कोई भी नहीं है? यदि नहीं, तो एल्गोरिदम धीमा या Ukkonen की तुलना में कोई कमी है?

Answer 1

1. मैं उन ग्राफों "ए" और "ना" तारों से कैसे प्राप्त कर सकता हूं?

एक प्रत्यय पेड़ का निर्माण, फिर कम से कम 2 वंशजों के साथ उच्चतम नोड पाएं।

string-node रूट से प्रत्येक नोड के लिए इस नोड के लिए समेकित तार है।highest node अधिकतम लंबाई string-node के साथ नोड है।

दूसरे प्रश्न के लिए मेरे उत्तर में पेड़ देखें। (3:n) में 2 वंशज हैं और नोड के लिए पथ (2:a)->(3:n) है, concatenate an है। और (5:a) के लिए भी na प्राप्त करें।

2. जैसा कि आप देख सकते हैं कि पेड़ अलग हैं, क्या वे बराबर हैं या नहीं, यदि हां वे अलग क्यों हैं, तो कौन सा एल्गोरिदम सही नहीं है?

ये पेड़ अलग हैं। (पहले पेड़ में के रूप में ) स्ट्रिंग "bannana$" के लिए दूसरे पेड़ के पुनर्निर्माण: पर्ल कार्यान्वयन गलत है

8: $ 
7: a$ 
5: ana$ 
2: annana$ 
1: bannana$ 
6: na$ 
4: nana$ 
3: nnana$ 

    |(1:bannana$)|leaf 
tree:| 
    |  |  |(4:nana$)|leaf 
    |  |(3:n)| 
    |  |  |(7:a$)|leaf 
    |(2:a)| 
    |  |(8:$)|leaf 
    | 
    |  |(4:nana$)|leaf 
    |(3:n)| 
    |  |  |(6:na$)|leaf 
    |  |(5:a)| 
    |  |  |(8:$)|leaf 
    | 
    |(8:$)|leaf 
5 branching nodes 

3. अगर वहाँ पर्ल/अजगर के लिए किसी भी कार्य कार्यान्वयन है?

मुझे पर्ल नहीं पता, लेकिन पेड़ सही ढंग से बनाया गया है।

4. मैंने Ukkonen के एल्गोरिदम के बारे में पढ़ा है जिसका पृष्ठ दूसरे उदाहरण के साथ पृष्ठ पर भी उल्लेख किया गया है (यदि ऑनलाइन संस्करण इस एल्गोरिदम का उपयोग कर रहा है या नहीं), तो क्या इस एल्गोरिदम का उपयोग करने वाले किसी भी उदाहरण में कोई उदाहरण नहीं है? यदि नहीं, तो एल्गोरिदम धीमा या Ukkonen की तुलना में कोई कमी है?

कि मैंने पहले कहा कि मैं पर्ल पता नहीं है, लेकिन यह पहली algorthim में एक पंक्ति का अर्थ यह है कम से कम O(n^2) (n यह है लंबाई स्ट्रिंग) काम करता है कि:

map { substr $str, $_ } 0 .. length($str) - 1; 

Ukkonen एल्गोरिथ्म रैखिक समय काम करता है O(n)।

पहला एल्गोरिदम भी रिकर्सिव है जो प्रयुक्त स्मृति को प्रभावित कर सकता है।