Il modo più efficace per cercare stringhe di testo molto grandi in java

Efficiente in termini di spazio o dimensioni? La stringa cambierà e, in caso affermativo, verrà aggiunta o modificata arbitrariamente? Come viene creata la stringa in primo luogo da dove proviene?

Non conoscendo le risposte a queste domande cruciali, sarò tentato di pensare (e testare in modo completo) una serie di approcci:

1. Pensa all'indicizzazione delle sottostringhe al momento della creazione della stringa. È necessario creare questa stringa originariamente, sia leggendola da un file, crescendolo come parte di un output dell'algoritmo, o generandolo nella sua interezza algoritmicamente. Al momento della creazione, poiché i caratteri stanno "entrando" nella stringa, pensate alla ricerca nel flusso di input e alle posizioni di indicizzazione nella stringa in cui si verificano le sottostringhe, quindi alla fine avete una tabella che mappa le sottostringhe all'elenco delle posizioni che le sottostringhe iniziano da. Ciò significa che stai costruendo un indice al momento della creazione / lettura delle stringhe (molto simile a un inserimento in un DB). È necessario considerare se la stringa cambia e sebbene l'aggiunta funzioni correttamente con questo approccio, l'inserimento non è così semplice (anche se dopo una modifica della media stringa, la regolazione dell'indice delle sottostringhe non richiederebbe un nuovo calcolo, solo aggiunte offset calcolate o sottrazione). Se è necessario cercare parole arbitrarie, al momento della creazione, creare un indice che associa tutte le parole alle posizioni nella stringa. Sarà un indice molto grande, ma non hai indicato se sei interessato alla velocità o allo spazio.

2. Considera l'utilizzo di costrutti del linguaggio Java già esistenti. Potrebbe essere necessario suddividere la stringa in array di sottostringhe per garantire le operazioni in memoria, quindi utilizzare la corrispondenza dei modelli o split () sulle sottostringhe e controllare l'inizio e la fine di tali stringhe per assicurarsi di non essere suddivisa in una parola stai cercando.

3. Considera l'utilizzo di strumenti nel sistema operativo sottostante, ad esempio, se sei su una piattaforma * nix, esegui una "grep" sulla stringa (salvata come file?) o strumento simile. Il lavoro di ricerca in modo efficiente è già stato fatto dallo sviluppatore del comando OS e ha intrapreso decenni di miglioramento continuo e il tempo aggiuntivo di attivazione di shell e grepping potrebbe essere superato dall'efficienza dello strumento.

4. Questo suona come la corrispondenza della sequenza del DNA e ci sarà un corpus di conoscenze esistente che copre la ricerca di queste sequenze che potrebbero essere utili a questo problema per te. Lo controllerò sicuramente.

Dovresti testarli e dipenderà dal fatto che la tua stringa sia in continua evoluzione o meno. La mia sensazione è che la costruzione di indici al momento della creazione / aggiornamento della stringa sia probabilmente la strada giusta da percorrere.