¿Qué estructura de datos de C# permite buscar un par de cadenas de manera más eficiente para las subcadenas?

Question

I tienen una estructura de datos que consiste de pares de valores, el primero de los cuales es un entero y la segunda de las cuales es una cadena alfanumérica (que puede comenzar con dígitos):

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

Una tabla de estos sería comprende hasta 100.000 filas.

Me gustaría proporcionar una función de búsqueda en la que el usuario pueda buscar ya sea el número (como si fuera una cadena), o piezas de la cadena. Idealmente, la búsqueda será "en vivo" a medida que el usuario escriba; después de cada pulsación de tecla (o tal vez después de una breve demora ~ 250-500 ms) se realizará una nueva búsqueda para encontrar los candidatos más probables. Así, por ejemplo, buscar en

• 1 volverá 15 APPLES, 16 APPLE COMPUTER, 17 ORANGE y 291 156TH ELEMENT
• 15 va a limitar la búsqueda a 15 APPLES, 291 156TH ELEMENT
• AP volverá 15 APPLES y 16 APPLE COMPUTER
• (idealmente , pero no es obligatorio) ELEM devolverá 291 156TH ELEMENT.

Estaba pensando acerca del uso de dos Dictionary<string, string> s ya en última instancia, los int s se comparan como string s - un índice voluntad por la parte entera y la otra por la parte de cadena.

Pero realmente buscar por subcadena no debería usar una función de hash, y parece un desperdicio usar el doble de la memoria que siento que debería necesitar.

En definitiva, la pregunta es, ¿existe alguna forma de realizar búsquedas de texto en dos grandes listas simultáneamente para las subcadenas?

En su defecto, ¿qué tal un SortedDictionary? Puede aumentar el rendimiento pero aún así no resolvería el problema del hash.

Pensé en crear una expresión regular sobre la marcha, pero creo que funcionaría terriblemente.

Soy nuevo en C# (viniendo del mundo Java) así que no he investigado LINQ todavía; es esa la respuesta?

EDITAR 18:21 EST: Ninguna de las cadenas en el campo "Nombre" tendrá más de 12-15 caracteres, si eso afecta su posible solución.

Answer 1

Considero usar la estructura de datos Trie.

¿Cómo lograr eso? Las hojas representarían su "fila", pero tendría "dos rutas" para cada instancia de memoria de una "fila" (una para el número y la otra para el nombre).

Luego, puede sacrificar su condición:

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

O proporcionar aún más rutas de acceso a sus instancias de fila.

Answer 2

De ser posible, evitaría cargar todas las 100.000 entradas en la memoria. Yo usaría una base de datos o Lucene.Net para indexar los valores. Luego use la sintaxis de consulta adecuada para buscar de manera eficiente los resultados.

Answer 3

Como está buscando el comienzo de las palabras, las colecciones basadas en claves no funcionarán, a menos que almacene todas las partes posibles de las palabras, como "a", "ap", "app", "appl", "apple ".

Mi sugerencia es utilizar un System.Collections.Generic.List<T> junto con una búsqueda binaria. Tendría que proporcionar su propio IComparer<T>, que también encuentra el comienzo de las palabras. Utilizarías dos estructuras de datos.

Un List<KeyValuePair<string,int>> sosteniendo palabras sueltas o el número como clave y el número como valor.

One Dictionary<int,string> con el nombre completo.

Se podría proceder de esta manera:

1. dividir su frase (el nombre completo) en palabras individuales.

2. Agréguelos a la lista con la palabra clave y el número como valor de KeyValuePair.

3. Agregue el número a la lista como clave y como valor de KeyValuePair.

4. Cuando la lista esté llena, ordene la lista para permitir una búsqueda binaria.

Buscar un principio de una palabra:

1. Buscar en la lista mediante el uso de BinarySearch en conjunto con su IComparer<T>.

2. El índice que obtienes de la búsqueda puede no ser el primero que aplica, así que vuelve a la lista hasta que encuentres la primera entrada que coincida.

3. Usando el número almacenado como valor en la lista, busque el nombre completo en el diccionario usando este número como clave.