Implementación eficiente de Trie para cadenas unicode

12

He estado buscando una implementación eficiente de String trie. Principalmente he encontrado un código como este:

Implementación referencial en Java (según wikipedia)

No me gustan estas implementaciones principalmente por dos razones:

  1. Solo admiten 256 caracteres ASCII. Necesito cubrir cosas como cirílico.
  2. Son extremadamente ineficientes de memoria.

Cada nodo contiene una matriz de 256 referencias, que son 4096 bytes en una máquina de 64 bits en Java. Cada uno de estos nodos puede tener hasta 256 subnodos con 4096 bytes de referencias cada uno. Por lo tanto, un Trie completo para cada cadena de caracteres ASCII 2 requeriría un poco más de 1 MB. Tres cadenas de caracteres? 256 MB solo para matrices en nodos. Y así.

Por supuesto, no tengo la intención de tener 16 millones de cadenas de tres caracteres en mi Trie, por lo que se desperdicia mucho espacio. La mayoría de estas matrices son solo referencias nulas, ya que su capacidad supera con creces el número real de claves insertadas. Y si agrego unicode, las matrices se vuelven aún más grandes (char tiene valores de 64k en lugar de 256 en Java).

¿Hay alguna esperanza de hacer un trie eficiente para cuerdas? He considerado un par de mejoras sobre este tipo de implementaciones:

  • En lugar de usar una matriz de referencias, podría usar una matriz de tipo entero primitivo, que se indexa en una matriz de referencias a nodos cuyo tamaño es cercano al número de nodos reales.
  • Podría dividir cadenas en partes de 4 bits que permitirían matrices de nodos de tamaño 16 a costa de un árbol más profundo.
RokL
fuente

Respuestas:

2

¿Para qué estás usando este trie? ¿Cuál es el número total de palabras que planea mantener y cuál es la escasez de sus caracteres constitutivos? Y lo más importante, ¿es apropiado incluso un trie (versus un simple mapa de prefijo a la lista de palabras)?

Su idea de una tabla intermedia y el reemplazo de punteros con índices funcionará, siempre que tenga un conjunto relativamente pequeño de palabras cortas y un conjunto de caracteres disperso. De lo contrario, corre el riesgo de quedarse sin espacio en su tabla intermedia. Y a menos que esté viendo un conjunto de palabras extremadamente pequeño, realmente no ahorrará tanto espacio: 2 bytes para un corto versus 4 bytes para una referencia en una máquina de 32 bits. Si está ejecutando una JVM de 64 bits, el ahorro será mayor.

Su idea de dividir los caracteres en fragmentos de 4 bits probablemente no le ahorrará mucho, a menos que todos sus caracteres esperados estén en un rango extremadamente limitado (tal vez esté bien para palabras limitadas a US-ASCII mayúsculas, probablemente no con un corpus Unicode general) )

Si tiene un conjunto de caracteres disperso, entonces una HashMap<Character,Map<...>>podría ser su mejor implementación. Sí, cada entrada será mucho más grande, pero si no tiene muchas entradas, obtendrá una victoria general. (como nota al margen: siempre pensé que era divertido que el artículo de Wikipedia sobre Tries mostrara, tal vez todavía lo hace, un ejemplo basado en una estructura de datos hash, ignorando por completo las compensaciones espacio / tiempo de esa elección)

Finalmente, es posible que desee evitar un trie por completo. Si está viendo un corpus de palabras normales en un lenguaje humano (10,000 palabras en uso activo, con palabras de 4 a 8 caracteres de longitud), probablemente estará MUCHO mejor con un HashMap<String,List<String>, donde la clave es el prefijo completo.

parsifal
fuente
- Las referencias son de 8 bytes en máquinas de 32 bits, 16 bytes en máquinas de 64 bits - Es para la funcionalidad de autocompletar - La mayoría de los caracteres en cadenas están en el rango ASCII, pero hay algunos caracteres de Europa Central. Es por eso que quería una ramificación más pequeña que 256, porque eliminará una gran cantidad de caracteres. No veo que HashMap <String, List <String>> sea mejor o más rápido o consuma menos memoria, aunque sea realmente fácil de escribir y usar. Pero aceptaré la idea HashMap <Carácter, Mapa>. Estaría bien para caracteres mayores de 128 (raro en mi caso, sería malo para el texto chino).
RokL
4

si codifica las cadenas en UTF8, puede usar el trie de ramificación 256 estándar y seguir siendo compatible con Unicode

también debe tener en cuenta que solo 70 caracteres de los 128 caracteres ascii posibles (que todos codifican a 1 byte en UTF8) se encontrarán con mayor frecuencia que puede optimizar para eso (como incluir los dígrafos comunes en lugar de los caracteres de control no utilizados )

monstruo de trinquete
fuente
Sé que UTF8 se puede representar así. Sin embargo, esto todavía no resuelve el consumo de memoria, que sigue siendo bastante alto. Intercambiar caracteres en el rango básico 256 requeriría un poco de cambio de oraciones, dudo que valga la pena. En lo que respecta a UTF-8 ... esto es realmente un problema que estoy reflexionando en este momento. Java String utiliza caracteres UTF-16, que puedo obtener fácilmente, puedo codificar estos bytes por bytes. O puedo convertir a UTF-8 y usar eso. En este punto, no me queda claro si el costo de la conversión de UTF-16 a UTF-8 es prohibitivo o no.
RokL
¿Cuál es el idioma que imagina usar esto la mayor parte del tiempo? tratando de optimizar para todo, es imposible (o que se hubiera hecho ya) Así que mejore para el caso común
monstruo de trinquete
1
Este es uno de los pocos casos de uso en los que CESU-8 sería preferible a UTF-8: su gran ventaja aquí es que es trivial pasar de un punto de código UTF-8 al punto de código CESU-8 correspondiente (mientras que necesitaría para decodificar 1-2 puntos de código UTF-16 para llegar a los puntos de código UTF-8 correspondientes).
Joachim Sauer
1
@ratchetfreak Java. Aunque creo que la pregunta se puede generalizar a la mayoría de los idiomas. Supongo que en C simplemente podría lanzar un puntero byte*para codificar cualquier tipo en un trie bit a bit.
RokL
@UMad Quise decir en qué idiomas estarán las cadenas de entrada (inglés, francés, alemán, ...)
ratchet freak