Algoritmo per trovare le sottostringhe più comuni in una stringa

Question

Esiste un algoritmo che può essere utilizzato per trovare le frasi più comuni (o sottostringhe) in una stringa? Ad esempio, la seguente stringa avrebbe "ciao mondo", come la sua più comune di due lettere frase:

"hello world this is hello world. hello world repeats three times in this string!"

Nella stringa sopra, la stringa più comune (dopo il carattere stringa vuota, che ripete un infinito numero di volte) sarebbe il carattere dello spazio .

C'è un modo per generare un elenco di sottostringhe comuni in questa stringa, da più comune al meno comune?

Answer 1

Questo è come compito analogo a algoritmo Nussinov e in realtà ancora più semplice come noi non permettiamo alcun lacune, inserzioni o disallineamenti nell'allineamento.

Per la stringa A avente la lunghezza N, definire una tabella F[-1 .. N, -1 .. N] e compilare utilizzando le seguenti regole:

for i = 0 to N 
    for j = 0 to N 
     if i != j 
     { 
      if A[i] == A[j] 
      F[i,j] = F [i-1,j-1] + 1; 
      else 
      F[i,j] = 0; 
     } 

Ad esempio, per BA O BA B:

Questo funziona nel tempo O(n^2). I valori più grandi nella tabella ora puntano alle posizioni finali delle subquenze di auto-matching più lunghe (i - la fine di una occorrenza, j - un'altra). All'inizio, si suppone che l'array sia inizializzato a zero. Ho aggiunto la condizione per escludere la diagonale che è la più lunga ma probabilmente non interessante auto-partita.

pensare di più, questo tavolo è simmetrica su diagonale quindi è abbastanza per calcolare solo la metà di esso. Inoltre, la matrice è inizializzata a zero, quindi l'assegnazione di zero è ridondante. Ciò rimane

for i = 0 to N 
    for j = i + 1 to N 
     if A[i] == A[j] 
     F[i,j] = F [i-1,j-1] + 1; 

Più breve ma potenzialmente più difficile da capire. La tabella calcolata contiene tutte le corrispondenze, corte e lunghe. Puoi aggiungere ulteriori filtri di cui hai bisogno.

Al passo successivo, è necessario recuperare le stringhe, seguito dalle celle non nulle in alto a sinistra dalla diagonale. Durante questo passaggio è anche banale utilizzare alcune hashmap per contare il numero di corrispondenze di auto-similarità per la stessa stringa. Con la stringa normale e la lunghezza minima normale solo il numero ridotto di celle della tabella verrà elaborato tramite questa mappa.

Penso che l'utilizzo di hashmap direttamente in realtà richiede O (n^3) come le corde chiave alla fine dell'accesso devono essere confrontati in qualche modo per l'uguaglianza. Questo confronto è probabilmente O (n).

Answer 2

Python. Questo è un po 'veloce e sporco, con le strutture dati che fanno la maggior parte del sollevamento.

from collections import Counter 
accumulator = Counter() 
text = 'hello world this is hello world.' 
for length in range(1,len(text)+1): 
    for start in range(len(text) - length): 
     accumulator[text[start:start+length]] += 1 

La struttura del contatore è un dizionario con hash, progettato per contare quante volte hai visto qualcosa. L'aggiunta a una chiave inesistente la creerà, mentre il recupero di una chiave inesistente ti darà zero invece di un errore. Quindi tutto ciò che devi fare è scorrere tutte le sottostringhe.

Answer 3

Perl, O(n²) soluzione

my $str = "hello world this is hello world. hello world repeats three times in this string!"; 

my @words = split(/[^a-z]+/i, $str); 
my ($display,$ix,$i,%ocur) = 10; 

# calculate 

for ($ix=0 ; $ix<=$#words ; $ix++) { 
    for ($i=$ix ; $i<=$#words ; $i++) { 
    $ocur{ join(':', @words[$ix .. $i]) }++; 
    } 
} 

# display 

foreach (sort { my $c = $ocur{$b} <=> $ocur{$a} ; return $c ? $c : split(/:/,$b)-split(/:/,$a); } keys %ocur) { 
    print "$_: $ocur{$_}\n"; 
    last if !--$display; 
} 

display 10 migliori punteggi delle stringhe sub più comuni (in caso di parità, mostra la catena più lunga di parole prima). Modificare $display a 1 per avere solo il risultato.
Ci sono n(n+1)/2 iterazioni.

Answer 4

codice appena pseudo, e forse questo non è la più bella soluzione, ma mi avrebbe risolto in questo modo:

function separateWords(String incomingString) returns StringArray{ 
    //Code 
} 

function findMax(Map map) returns String{ 
    //Code 
} 

function mainAlgorithm(String incomingString) returns String{ 
    StringArray sArr = separateWords(incomingString); 
    Map<String, Integer> map; //init with no content 
    for(word: sArr){ 
     Integer count = map.get(word); 
     if(count == null){ 
      map.put(word,1); 
     } else { 
      //remove if neccessary 
      map.put(word,count++); 
     } 
    } 
    return findMax(map); 
} 

Dove mappa può contenere una chiave, coppie di valori come in Java HashMap.

Answer 5

Dal momento che per ogni sottostringa di una stringa di lunghezza> = 2 il testo contiene almeno una stringa di lunghezza 2, almeno tutte le volte, abbiamo solo bisogno di indagare su stringhe di lunghezza 2.

val s = "hello world this is hello world. hello world repeats three times in this string!" 

val li = s.sliding (2, 1).toList 
// li: List[String] = List(he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " t", th, hi, is, "s ", " i", is, "s ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, d., ". ", " h", he, el, ll, lo, "o ", " w", wo, or, rl, ld, "d ", " r", re, ep, pe, ea, at, ts, "s ", " t", th, hr, re, ee, "e ", " t", ti, im, me, es, "s ", " i", in, "n ", " t", th, hi, is, "s ", " s", st, tr, ri, in, ng, g!) 

val uniques = li.toSet 
uniques.toList.map (u => li.count (_ == u)) 
// res18: List[Int] = List(1, 2, 1, 1, 3, 1, 5, 1, 1, 3, 1, 1, 3, 2, 1, 3, 1, 3, 2, 3, 1, 1, 1, 1, 1, 3, 1, 3, 3, 1, 3, 1, 1, 1, 3, 3, 2, 4, 1, 2, 2, 1) 

uniques.toList(6) 
res19: String = "s "