Quale struttura dati C# consente di cercare le stringhe in modo più efficiente per le sottostringhe?

Question

devo una struttura di dati che consiste di coppie di valori, il primo dei quali è un numero intero e la seconda delle quali è una stringa alfanumerica (che può iniziare con cifre):

+--------+-----------------+ 
| Number | Name   | 
+--------+-----------------+ 
| 15  | APPLES   | 
| 16  | APPLE COMPUTER | 
| 17  | ORANGE   | 
| 21  | TWENTY-1  | 
| 291 | 156TH ELEMENT | 
+--------+-----------------+ 

Una tabella di questi sarebbe comprendono fino a 100.000 righe.

Vorrei fornire una funzione di ricerca in cui l'utente può cercare il numero (come se fosse una stringa) o pezzi della stringa. Idealmente la ricerca sarà "live" come l'utente digita; dopo ogni sequenza di tasti (o forse dopo un breve ritardo di ~ 250-500 ms) verrà eseguita una nuova ricerca per trovare i candidati più probabili. Così, ad esempio, la ricerca su

• 1 tornerà 15 APPLES, 16 APPLE COMPUTER, 17 ORANGE, e 291 156TH ELEMENT
• 15 sarà restringere la ricerca a 15 APPLES, 291 156TH ELEMENT
• AP torneranno 15 APPLES e 16 APPLE COMPUTER
• (idealmente , ma non richiesto) ELEM restituirà 291 156TH ELEMENT.

Stavo pensando di utilizzare due Dictionary<string, string> s poiché in definitiva le int s vengono confrontati come string s - un indice piacimento la parte intera e l'altra dalla parte stringa.

Ma la ricerca per sottostringa non dovrebbe utilizzare una funzione di hash e sembra inutile utilizzare il doppio della memoria di cui ho bisogno.

In definitiva, la domanda è: esiste un modo efficace per cercare nel testo due elenchi di grandi dimensioni contemporaneamente per sottostringhe?

In caso contrario, che ne dici di uno SortedDictionary? Potrebbe aumentare le prestazioni ma non risolverebbe il problema dell'hash.

Pensavo di creare una regex al volo, ma pensavo che avrebbe funzionato terribilmente.

Sono nuovo di C# (essendo venuto dal mondo Java), quindi non ho ancora esaminato LINQ; è questa la risposta?

MODIFICA 18:21 EST: nessuna delle stringhe nel campo "Nome" sarà più lunga di 12-15 caratteri, se ciò influisce sulla potenziale soluzione.

Answer 1

Prendere in considerazione l'utilizzo della struttura dati Trie.

Come raggiungerlo? Le foglie rappresenterebbero la tua "riga", ma avresti "due percorsi" per ogni istanza di memoria di una "riga" (una per il numero e l'altra per il nome).

È quindi possibile sacrificare la sua condizione:

(ideally, but not required) ELEM will return 291 156TH ELEMENT. 

O fornire ancora più percorsi alle istanze di fila.

Answer 2

Se possibile, evitare di caricare tutte le 100.000 voci in memoria. Vorrei utilizzare un database o Lucene.Net per indicizzare i valori. Quindi utilizzare la sintassi di query appropriata per cercare in modo efficiente i risultati.

Answer 3

Poiché si sta cercando l'inizio di parole, le raccolte basate su chiavi non funzioneranno, a meno che non si memorizzino tutti i pezzi possibili delle parole, come "a", "ap", "app", "appl", "mela ".

Il mio suggerimento è quello di utilizzare un System.Collections.Generic.List<T> in congiunzione con una ricerca binaria. Dovresti fornire il tuo IComparer<T>, che trova anche l'inizio delle parole. Dovresti usare due strutture dati.

Uno List<KeyValuePair<string,int>> contenente singole parole o il numero come chiave e il numero come valore.

Uno Dictionary<int,string> con il nome intero.

Si potrebbe procedere in questo modo:

1. dividere la frase (il nome completo) in singole parole.

2. Aggiungili all'elenco con la parola chiave e il numero come valore di KeyValuePair.

3. Aggiungere il numero all'elenco come chiave e valore dello KeyValuePair.

4. Quando l'elenco è pieno, ordinare l'elenco per consentire una ricerca binaria.

Ricerca di un inizio di una parola:

1. Cerca nella lista utilizzando BinarySearch in congiunzione con il IComparer<T>.

2. L'indice che si ottiene dalla ricerca potrebbe non essere il primo che si applica, quindi tornare all'elenco finché non si trova la prima voce corrispondente.

3. Utilizzando il numero memorizzato come valore nell'elenco, cercare l'intero nome nel dizionario utilizzando questo numero come chiave.