Quale algoritmo puoi utilizzare per trovare frasi duplicate in una stringa?

Question

Data una stringa arbitraria, qual è un metodo efficiente per trovare frasi duplicate?Possiamo dire che le frasi devono essere più lunghe di una certa lunghezza per essere incluse.

Idealmente, ti ritroveresti con il numero di occorrenze di ciascuna frase.

Answer 1

Come le persone precedenti hanno affermato che l'albero dei suffissi è lo strumento migliore per il lavoro.Il mio sito preferito per gli alberi dei suffissi è http://www.allisons.org/ll/AlgDS/Tree/Suffix/.Elenca tutti gli usi intelligenti degli alberi dei suffissi in un'unica pagina e include un test js applicazione incorporata per testare le stringhe e lavorare attraverso esempi.

Answer 2

In teoria

• UN matrice di suffissi è la risposta "migliore" poiché può essere implementata per utilizzare lo spazio e il tempo lineari per rilevare eventuali sottostringhe duplicate.Tuttavia, l'implementazione ingenua in realtà richiede tempo O(n^2 log n) per ordinare i suffissi, e non è del tutto ovvio come ridurlo a O(n log n), per non parlare di O(n), anche se puoi leggere i relativi documenti se vuoi.
• UN albero dei suffissi può richiedere leggermente più memoria (sempre lineare, però) rispetto a un array di suffissi, ma è più facile da implementare per creare rapidamente poiché puoi usare qualcosa come un'idea di ordinamento digitale mentre aggiungi elementi all'albero (vedi il collegamento a Wikipedia dal nome di dettagli).
• IL Algoritmo KMP È bene essere consapevoli anche del fatto che è specializzato nella ricerca molto rapida di una particolare sottostringa all'interno di una stringa più lunga.Se hai bisogno solo di questo caso speciale, usa semplicemente KMP e non devi preoccuparti prima di creare un indice di sufficienza.

In pratica

Immagino che tu stia analizzando un documento di linguaggio naturale reale (ad es.inglese) e vuoi effettivamente fare qualcosa con i dati che raccogli.

In questo caso, potresti semplicemente voler fare un rapido n-grammo analisi per alcuni n piccoli, ad esempio solo n = 2 o 3.Ad esempio, potresti tokenizzare il tuo documento in un elenco di parole eliminando la punteggiatura, le maiuscole e le parole con radice (in esecuzione, esegue entrambi -> 'esegui') per aumentare le corrispondenze semantiche.Quindi crea semplicemente una mappa hash (come hash_map in C++, un dizionario in Python, ecc.) di ciascuna coppia di parole adiacenti rispetto al numero di occorrenze finora.Alla fine ottieni alcuni dati molto utili che sono stati molto veloci da codificare e non molto lenti da eseguire.

Answer 3

Alberi suffisso sono un buon modo per implementarlo.La parte inferiore dell'articolo contiene collegamenti a implementazioni in diverse lingue.

Answer 4

Come ha detto jmah, puoi usare alberi di suffisso/array di suffisso per questo.

C'è una descrizione di un algoritmo che potresti usare Qui (vedere Sezione 3.1).

Potete trovare una descrizione più approfondita nel libro da loro citato (Gusfield, 1997), che è su Google Libri.

Answer 5

supponiamo che ti venga fornito un array ordinato A con n voci (i=1,2,3,...,n)

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

Questo algoritmo viene eseguito al tempo O(n).