che cosa è la struttura/algoritmo di raccolta stringhe più veloce per startwith e/o contiene ricerche

Question

Ho la seguente situazione: Ho una grande collezione di stringhe (diciamo 250.000+) di lunghezza media di forse 30. Quello che devo fare è fare molte ricerche all'interno di questi .. per lo più quelli saranno di StartsWith e Contains tipo.

La raccolta è statica in fase di esecuzione. Il che significa che la lettura iniziale e il riempimento della raccolta di scelta avvengono solo una volta. Pertanto, le prestazioni di costruzione della struttura dati non sono assolutamente importanti. Anche la memoria non è un problema: il che significa anche che non mi dispiace avere due raccolte con gli stessi dati in ciascuna se necessario (come una per startswith e un'altra per contiene). L'unica cosa che conta è l'esecuzione delle ricerche che dovrebbero restituire tutti gli elementi che corrispondono alla condizione di ricerca.

Per startwith mi sono imbattuto in un albero Trie o Radix .. ma forse ci sono anche scelte migliori?

Per contiene .. Non ho ancora una buona idea (oltre all'esecuzione di una query linq su una lista che non sarà molto veloce con quella quantità di dati).

Grazie in anticipo a tutti!

aggiornamento: ho dimenticato una parte importante: con Contiene voglio dire corrispondenze esatte della collezione .. ma voglio trovare tutte le stringhe della collezione che contengono la data searchstring

Answer 1

Costruire un suffix tree vi permetterà di eseguire una ricerca di sottostringa su tutte le stringhe in parallelo in O(1). Il pedante in me non può fare a meno di notare che è davvero O(n + m) dove n è il numero di stringhe che corrispondono alla sottostringa e m è la dimensione della sottostringa interrogata.

Quindi qual è l'albero di suffisso che chiedi? Nella sua implementazione più semplice, è un trie con un metodo di inserimento più elaborato: oltre ad aggiungere una stringa, aggiunge anche il suffisso di quella stringa al trie. Su questa struttura dati, una ricerca di sottostringa diventa una ricerca prefisso di tutti i suffissi possibili. Dato che vuoi anche fare ricerche di prefissi, ti consigliamo di aggiungere un carattere speciale davanti a ciascuna stringa inserita e le sottostringhe della query. Il carattere speciale ti permetterà di distinguere tra un suffisso e una stringa completa.

Mentre questa implementazione di un albero di suffisso è straordinariamente semplice, è anche molto inefficiente (O(n^2) spazio e tempo di compilazione). Fortunatamente, esistono altre implementazioni più efficienti che possono ridurre notevolmente i limiti di spazio e di tempo. Uno di questi, l'algoritmo di Ukkonen, è spiegato molto bene in this SO answer e porta lo spazio limitato a O(n). Si consiglia inoltre di esaminare suffix arrays che sono una rappresentazione equivalente ma più efficiente di alberi di suffisso.

Mentre so che ci sono molte molte altre implementazioni di alberi di suffisso (uno dei quali probabilmente colpirà il punto debole per il tuo caso d'uso) Io proprio non li conosco. Ti consiglio di fare qualche ricerca sull'argomento prima di stabilirti su un'implementazione.