Tengo un problema: necesito una búsqueda de los datos del sistema de archivos con un uso eficiente del espacio basado en el prefijo de la ruta del archivo. Prefija la búsqueda del texto ordenado, en otras palabras. Usa un trie, dices, y pensé lo mismo. El problema es que los intentos no son lo suficientemente eficientes desde el punto de vista espacial, no sin otros trucos.Estructura en memoria eficiente en el espacio para texto ordenado que admite búsquedas de prefijo
que tienen una buena cantidad de datos:
- sobre 450M en un texto sin formato Unix formato de listado en el disco
- cerca de 8 millones de líneas
- predeterminado gzip comprime a 31M
- bzip2 predeterminado comprime a 21M
No quiero comer en ningún lugar cerca de 450M en memoria. En este punto, me gustaría utilizar algo de alrededor de 100M, ya que hay mucha redundancia en forma de prefijos.
Estoy usando C# para este trabajo, y una implementación directa de un trie todavía requerirá un nodo hoja para cada línea en el archivo. Dado que cada nodo hoja requerirá algún tipo de referencia al fragmento final de texto (32 bits, digamos un índice en una matriz de datos de cadena para minimizar la duplicación de cadena), y la sobrecarga del objeto CLR es de 8 bytes (verificado usando windbg/SOS) , Gastaré> 96,000,000 bytes en gastos generales estructurales sin almacenamiento de texto.
Veamos algunos de los atributos estadísticos de los datos. Cuando rellena en un trie:
- totales únicas "trozos" de texto alrededor de 1,1 millones de
- trozos únicos total de aproximadamente 16 millones en el disco en un archivo de texto
- longitud media porción es de 5,5 caracteres, máximo 136
- cuando no teniendo en cuenta los duplicados, cerca de 52 millones de caracteres totales en trozos
- nodos trie internos promedio de cerca de 6,5 niños con un máximo de 44
- aproximadamente 1.8M nodos interiores.
tasas excesivas de creación de la hoja es de aproximadamente 15%, el exceso de interior creación nodo es 22% - por el exceso de creación, me refiero a hojas y nodos interiores creados durante la construcción trie pero no en el trie final como una proporción de la final número de nodos de cada tipo.
Así es un análisis montón de SOS, que indica dónde se está acostumbrando más memoria:
[MT ]--[Count]----[ Size]-[Class ]
03563150 11 1584 System.Collections.Hashtable+bucket[]
03561630 24 4636 System.Char[]
03563470 8 6000 System.Byte[]
00193558 425 74788 Free
00984ac8 14457 462624 MiniList`1+<GetEnumerator>d__0[[StringTrie+Node]]
03562b9c 6 11573372 System.Int32[]
*009835a0 1456066 23297056 StringTrie+InteriorNode
035576dc 1 46292000 Dictionary`2+Entry[[String],[Int32]][]
*035341d0 1456085 69730164 System.Object[]
*03560a00 1747257 80435032 System.String
*00983a54 8052746 96632952 StringTrie+LeafNode
El Dictionary<string,int> está siendo utilizado para mapear trozos de cuerda a índices en una List<string>, y pueden ser descartados después de la construcción trie, aunque GC no parece estar eliminándolo (un par de colecciones explícitas se realizaron antes de este vuelco) - !gcroot en SOS no indica ninguna raíz, pero anticipo que un GC posterior podría liberarlo.
MiniList<T> es un reemplazo para List<T> utilizando una (es decir, el crecimiento lineal, O(n^2) rendimiento adición) precisamente de tamaño T[] para evitar el desperdicio de espacio; es un tipo de valor y es usado por InteriorNode para rastrear niños.Este T[] se agrega a la pila System.Object[].
Por lo tanto, si subo los artículos "interesantes" (marcados con *), obtengo unos 270M, que es mejor que el texto sin formato en el disco, pero aún no lo suficientemente cerca de mi objetivo. Me imaginé que objeto .NET cabeza era demasiado, y creó un nuevo trie "delgado", usando sólo las matrices de tipo valor a almacenar datos:
class SlimTrie
{
byte[] _stringData; // UTF8-encoded, 7-bit-encoded-length prefixed string data
// indexed by _interiorChildIndex[n].._interiorChildIndex[n]+_interiorChildCount[n]
// Indexes interior_node_index if negative (bitwise complement),
// leaf_node_group if positive.
int[] _interiorChildren;
// The interior_node_index group - all arrays use same index.
byte[] _interiorChildCount;
int[] _interiorChildIndex; // indexes _interiorChildren
int[] _interiorChunk; // indexes _stringData
// The leaf_node_index group.
int[] _leafNodes; // indexes _stringData
// ...
}
Esta estructura ha reducido la cantidad de datos a 139m, y sigue siendo un trie eficientemente transitable para operaciones de solo lectura. Y como es tan simple, puedo guardarlo trivialmente en el disco y restaurarlo para evitar el costo de volver a crear el trie todo el tiempo.
¿Alguna sugerencia para estructuras más eficientes para la búsqueda de prefijos que trie? Enfoques alternativos que debería considerar?
¿Qué tipo de uso va a hacer con los datos? Mucho procesamiento o solo algunas búsquedas; ¿Puede darnos una idea de qué compensación entre el almacenamiento y el procesamiento eficiente son aceptables? – Jackson
Básicamente se almacenan en caché las operaciones de búsqueda del sistema de archivos para que no sea necesario consultar el disco físico para obtener todos los archivos en un directorio, todos los archivos recursivamente en un directorio, etc. sin consultar el disco, que invariablemente no en la memoria y de hecho es a través de la red => demasiados viajes de ida y vuelta. La expectativa de rendimiento sería que hacer 150 búsquedas de prefijos (es decir, encontrar todas las líneas con este prefijo) devolver promedio de 100 líneas no debería tomar más de, digamos, 100 ms. Tal como están las cosas, mi enfoque de 'SlimTrie' toma 10 segundos cargar desde el disco y lista 8,000,000 líneas => ~ 18ms. –
Y eso con la optimización desactivada, con 8 segundos encendidos, eso incluye el inicio de la aplicación. 140M no es tan malo, pero considerando la redundancia en estos datos, estoy seguro de que se puede mejorar. –