come ottenere la stringa ripetuta più lunga nella sottostringa dall'albero dei suffissi

Question

Ho bisogno di trovare la stringa ripetuta più lunga nella sottostringa. Diciamo che ho stringa "bannana"

Wikipedia says seguente:

In informatica, il problema più lunga sottostringa ripetuto è il problema di trovare la sottostringa più lunga di una stringa che si verifica in almeno due volte. Nella figura con la stringa "ATCGATCGA $", la più lunga ripetuto stringa è "ATCGA"

quindi immagino che per la stringa "bannana" ci sono due sottostringhe altrettanto lunghi (se non mi corregga per favore): "an" e "na" .

Wikipedia anche says che per questo scopo vengono utilizzati gli alberi di suffisso. Per essere più precisi here è citazione come farlo (questo mi sembra più understable di definizione su wikipedia):

costruire un albero suffisso, quindi trovare il nodo più alto con almeno 2 discendenti.

Ho trovato diverse implementazioni di alberi di suffisso. Codice seguente è tratto da 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$'; 

per la stringa "bannana" restituisce seguente albero:

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

Un'altra implementazione è online da here, per la stringa "bannana" restituisce seguente albero:

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 

Domande:

1. Come posso ottenere da quei grafici "an" e "na" stringhe?
2. Come puoi vedere gli alberi sono diversi, sono equivalenti o meno, se sì perché sono diversi, se non quale algoritmo è corretto?
3. Se l'implementazione di perl è errata esiste un'implementazione funzionante per perl/python?
4. Ho letto sull'algoritmo di Ukkonen che è anche menzionato a pagina con il 2o esempio (non ho capito se la versione online sta usando questo algoritmo o no), qualcuno degli esempi citati usa questo algoritmo? In caso contrario, l'algoritmo utilizzato è più lento o presenta qualche svantaggio rispetto a Ukkonen?

Answer 1

1. Come posso ottenere da quei grafici "an" e "na" stringhe?

costruire un albero di suffisso, quindi trovare il nodo più alto con almeno 2 discendenti.

string-node è concatenare stringhe per ogni nodo da root a questo nodo.highest node è il nodo con lunghezza massima string-node.

Vedere l'albero nella mia risposta per la seconda domanda. (3:n) hanno 2 discendenti e il percorso per il nodo è (2:a)->(3:n), il numero di concatenazione è an. E anche per (5:a) ottenere na.

2. Come puoi vedere gli alberi sono diversi, sono equivalenti o meno, se sì perché sono diversi, se non quale algoritmo è corretto?

Questi alberi sono diversi. Ricostruire secondo albero per la stringa "bannana$" ( come nel primo albero):

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. Se perl implementazione è sbagliato v'è alcuna implementazione di lavoro per il Perl/Python?

Non conosco il Perl, ma l'albero è stato costruito correttamente.

4. Ho letto sull'algoritmo di Ukkonen che è anche menzionato a pagina con il 2o esempio (non ho capito se la versione online sta usando questo algoritmo o no), qualcuno degli esempi citati usa questo algoritmo? In caso contrario, l'algoritmo utilizzato è più lento o presenta qualche svantaggio rispetto a Ukkonen?

ho detto prima che non so di Perl, ma è una linea in prima algorthim significa che funziona almeno O(n^2) (n Si tratta di lunghezza della stringa):

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

algoritmo di Ukkonen funziona tempo lineare O(n).

Primo algoritmo anche ricorsivo che può influire sulla memoria utilizzata.