Qual è il modo più efficiente per tenere traccia dell'indice di un carattere specifico in una stringa?

Question

Prendiamo come esempio la seguente stringa:

"La veloce volpe marrone"

In questo momento la q in quick è all'indice 4 della stringa (a partire da 0) e la f in fox è all'indice 16.Ora supponiamo che l'utente inserisca altro testo in questa stringa.

"La velocissima volpe marrone scuro"

Ora la q è nell'indice 9 e la f è nell'indice 26.

Qual è il metodo più efficiente per tenere traccia dell'indice dell'originale q in quick e f in fox, indipendentemente dal numero di caratteri aggiunti dall'utente?

La lingua non ha importanza per me, questa è più una questione teorica che altro, quindi usa la lingua che preferisci, cerca solo di mantenerla nelle lingue generalmente popolari e attuali.

La stringa di esempio che ho fornito è breve, ma spero in un modo in grado di gestire in modo efficiente stringhe di qualsiasi dimensione.Quindi l'aggiornamento di un array con l'offset funzionerebbe con una stringa breve ma si impantanerebbe con troppi caratteri.

Anche se nell'esempio stavo cercando l'indice dei caratteri univoci nella stringa, voglio anche poter tracciare l'indice dello stesso carattere in posizioni diverse come la o in marrone e la o in volpe.Quindi la ricerca è fuori questione.

Speravo che la risposta fosse efficiente sia in termini di tempo che di memoria, ma se dovessi sceglierne solo una mi preoccuperei di più della velocità delle prestazioni.

Answer 1

Diciamo che hai una stringa e alcune delle sue lettere lo sono interessante.Per semplificare le cose diciamo che la lettera all'indice 0 è sempre interessante e non aggiungi mai qualcosa prima di essa: una sentinella.Annota le coppie di (lettera interessante, distanza dalla lettera interessante precedente).Se la stringa è "+the very Quick dark brown Fox" e ti interessa q di 'quick' e f di 'fox' allora dovresti scrivere:(+,0), (q,10), (f,17).(Il segno + è la sentinella.)

Ora li inserisci in un albero binario bilanciato il cui attraversamento in ordine fornisce la sequenza di lettere nell'ordine in cui appaiono nella stringa.Ora potresti riconoscere il problema delle somme parziali:Migliora l'albero in modo che i nodi contengano (lettera, distanza, somma).La somma è la somma di tutte le distanze nel sottoalbero di sinistra.(Quindi somma(x)=distanza(sinistra(x))+somma(sinistra(x)).)

Ora puoi eseguire query e aggiornare questa struttura dati in tempo logaritmico.

Per dire che hai aggiunto N caratteri a sinistra del carattere C dici distance(c)+=n e poi vai ad aggiornare la somma per tutti i genitori di C.

Chiedere qual è l'indice di C calcoli sum(c)+sum(parent(c))+sum(parent(parent(c)))+...

Answer 2

La tua domanda è un po' ambigua: vuoi tenere traccia delle prime istanze di ogni lettera?In tal caso, un array di lunghezza 26 potrebbe essere l'opzione migliore.

Ogni volta che inserisci del testo in una stringa in una posizione inferiore all'indice che hai, calcola semplicemente l'offset in base alla lunghezza della stringa inserita.

Answer 3

Sarebbe utile anche avere in mente una lingua di destinazione poiché non tutte le strutture dati e le interazioni sono ugualmente efficienti ed efficaci in tutte le lingue.

Answer 4

Il trucco standard che di solito aiuta in situazioni simili è mantenere i caratteri della stringa come foglie in un albero binario bilanciato.Inoltre, i nodi interni dell'albero dovrebbero mantenere insiemi di lettere (se l'alfabeto è piccolo e fisso, potrebbero essere bitmap) che ricorrono nel sottoalbero con radice in un particolare nodo.

L'inserimento o l'eliminazione di una lettera in questa struttura richiede solo operazioni O(log(N)) (aggiorna le bitmap sul percorso verso root) e trovare la prima occorrenza di una lettera richiede anche operazioni O(log(N)) - da cui discendi la radice, andando verso il figlio più a sinistra la cui bitmap contiene la lettera interessante.

Modificare:I nodi interni dovrebbero anche mantenere il numero di foglie nel sottoalbero rappresentato, per un calcolo efficiente dell'indice delle lettere.