Gli alberi di suffisso e gli array di suffissi sono identici? Quali sono le differenze?

3

Ho letto alcune informazioni tramite internet ... ho scoperto che in qualche modo l'albero dei suffissi è abbastanza simile all'array di suffissi ma in qualche modo non sono la stessa cosa ..

Dato una stringa, un algoritmo di costruzione dell'albero del suffisso assomiglia a questo (ho copiato l'algoritmo da un sito web)

FOR i ← 1 to n-1        
FOR j ← 1 to i+1             
   find the end path for S[j…i]
   extend the path, if needed, to S[i+1] 

albero suffisso in grado di elencare tutta la sottrazione ottenuta da una determinata stringa

Tuttavia, l'array di suffissi fornisce anche la stessa funzionalità per ottenere l'elenco delle sottostringhe? Oppure gli array di suffissi sono solo un'implementazione di alberi di suffisso? O l'array di suffissi fornisce solo qualche funzione di memorizzazione?

    
posta teh356 15.09.2011 - 17:53
fonte

2 risposte

2

Un array di suffissi è una infrastruttura che utilizza uno spazio efficiente, che, se conservata insieme alla stringa originale, fornisce le stesse funzioni di un albero dei suffissi.

Quindi sì, puoi pensare a un array di suffissi come meccanismo di archiviazione per gli alberi dei suffissi. A seconda dei dettagli, potrebbero esserci dei costi di performance nell'utilizzo di array su alberi in piena regola, che in genere sono superati dai benefici dell'uso dello spazio. Credo che gli array siano costruiti in modo quasi identico al modo in cui sono costruiti gli alberi e, in pratica, gli array di suffissi sono il metodo preferito per memorizzare / rappresentare un albero di suffisso.

    
risposta data 15.09.2011 - 22:16
fonte
1

La parola "suffix array" sembra essere usata ambiguamente. Da un lato, può significare precisamente quello che dice il termine: una matrice di suffissi (ordinati). D'altra parte, può fare riferimento a questa matrice di suffissi insieme ad altre tabelle, rendendo la struttura dei dati più utile per vari scopi. Per maggiore chiarezza, è possibile utilizzare il termine "tabella dei suffissi" per l'array stesso e utilizzare il termine "suffix array" come termine di copertura per le varie strutture di dati a più tabelle che utilizzano una tabella dei suffissi. Quindi, con questa terminologia, sembra chiaro che hai scaricato un programma per la costruzione della tabella dei suffissi. In altre parole, hai scaricato un'implementazione di un algoritmo di ordinamento del suffisso.

Questa distinzione tra matrice suffisso e tabella dei suffissi è importante da fare quando si confronta l'efficienza degli array di suffissi e degli alberi dei suffissi. La tabella del suffisso stessa è ovviamente succinta ed efficiente. Ma con ogni tabella aggiuntiva, il divario si restringe, così che alla fine è difficile dire quale sia più efficiente. Un numero di articoli negli ultimi dieci anni ha riportato un vantaggio per gli array di suffissi. Ma per raggiungere questa prestazione superiore, devi essere un programmatore molto intelligente.

Se vuoi davvero conoscere gli array di suffissi, allora, a mio avviso, imparare a ordinare i suffissi non è il punto di partenza. Inizia invece con la carta "Extended Suffix Array" di Abouelhoda et al. Questa non è una carta facile. Ma d'altra parte, è molto ampiamente citato, e ogni documento che lo cita deve anche riassumerlo in una certa misura. Quindi alla fine, se ci metti un po 'di lavoro, passerai sicuramente attraverso il giornale. Una volta finito con Abouelhoda, leggi tutti i documenti che citano Aboueloda. Poi leggi il precedente documento di linguistica computazionale di Yamamoto e Church e, naturalmente, i documenti che citano questo. La mia ipotesi è che i linguisti non computazionali otterranno anche qualcosa da questo articolo (non essere troppo limitato dal tuo campo di studi ristretto). Presto diventerai un esperto di array di suffissi senza aver mai imparato a ordinare i suffissi. Quando arrivi a questo punto, torna indietro e leggi un po 'della letteratura per l'ordinamento dei suffissi. Vedrai che è un problema CS fondamentale molto interessante. Infine, per altre questioni fondamentali di CS relative agli array di suffissi (problemi combinatori), raccomando la tesi di Klaus Schürmann (Università di Bielefeld).

    
risposta data 18.09.2011 - 21:14
fonte

Leggi altre domande sui tag