string - significado - ¿Limitaciones y alternativas a los intentos en otros idiomas además del inglés?

trie significado (2)

Como un addendum a la respuesta de @JimMischel, me gustaría mencionar el tema de que en otros idiomas a menudo hay múltiples formas equivalentes de escribir lo mismo. Vietnamese (basado en la escritura latina / inglesa) es un ejemplo particularmente bueno donde las letras con dos acentos son comunes. Por ejemplo, Ặ (U + 1EB6) también puede escribirse técnicamente con las secuencias dot + punto, Ạ + breve, A + breve + punto, A + punto + breve.

La normalización de Unicode puede resolver este problema al convertir una cadena a un orden canónico estandarizado. Hay 4 variaciones diferentes, NFC, NFKC, NFD y NFKD. No voy a entrar en demasiados detalles aquí, pero los dos primeros son "formas compuestas" que tienden a acortar la cadena, agrupando los caracteres base con sus acentos, mientras que los dos últimos son "formas descompuestas", haciendo lo contrario.

Hangul es un caso interesante: es un alfabeto, aunque todas las letras de una sílaba están escritas juntas en un bloque. Tanto las letras individuales como los bloques silábicos existen en Unicode. La normalización puede resolver esto, aunque el número de sílabas distintas es bastante grande. El uso de NFC / NFKC puede no ser útil para un intento, pero en este caso, usar NFD / NFKD para descomponer las sílabas a las letras constituyentes funcionaría.

Algunos otros puntos no relacionados a considerar:

Además del punto garçon / garcon ya mencionado, tiene el problema cote / coté / côte / côté, que son palabras francesas distintas. Del mismo modo, las marcas de vocales en hebreo y árabe no suelen ser obligatorias, lo que en ocasiones puede causar ambigüedades.
Los alfabetos ¹ del sur y sudeste de Asia pueden ser grandes en comparación con el inglés, aproximadamente el doble de tamaño.

Se denominan estrictamente abugidas , donde las vocales se escriben como signos diacríticos / acentos, pero esta distinción generalmente puede ignorarse desde el punto de vista de la programación.

La estructura de datos trie es a menudo una excelente manera de almacenar cadenas en inglés. Funciona al construir un árbol donde cada borde está etiquetado con una letra, y la ruta a un nodo marcado en el árbol explica una de las palabras en la estructura de datos.

Esta estructura de datos funciona bien en inglés porque hay "solo" 26 letras en el alfabeto inglés (un factor de bifurcación "razonable"), esos caracteres tienen valores ASCII consecutivos (por lo que los punteros secundarios pueden almacenarse en una matriz codificada por el índice de las letras utilizadas por cada niño), y hay muchas palabras en inglés con prefijos comunes (por lo que hay mucha redundancia en la estructura).

Soy un hablante nativo de inglés con un conocimiento limitado de otros idiomas y alfabetos, pero parece que muchas de estas propiedades no son válidas en otros idiomas. Sé que el francés, el español, el alemán y el húngaro, por ejemplo, utilizan con frecuencia caracteres acentuados que no se almacenan continuamente con las letras restantes en el espacio Unicode. Hebreo y árabe tienen marcas de vocales que usualmente se indican arriba o debajo de cada letra. El chino utiliza un sistema de logograma, y los caracteres Hangul coreanos consisten en triples de caracteres más pequeños agrupados.

¿Los intentos siguen funcionando bien para los datos almacenados en estos idiomas y alfabetos? ¿Qué cambios, si los hay, son necesarios para usar try para este tipo de datos? ¿Existen estructuras de datos que funcionen bien para cadenas en esos idiomas y alfabetos que sean particularmente adecuados para ellas pero que no sean útiles o eficientes en inglés?

Descubrí que los intentos funcionan bien para los idiomas de Europa occidental, así como para el cirílico y muchos otros idiomas alfabéticos. Ahora que lo pienso, los únicos idiomas con los que tuve problemas fueron el chino, el japonés y otros sistemas de escritura logográfica. Y para aquellos, el trie fue inútil.

Los valores secuenciales de Unicode de los caracteres ingleses no son realmente un gran beneficio. Aunque sugiere la implementación del nodo simple:

CharNode char array[26] of CharNode

Esa estructura no es particularmente útil. Puede hacer las cosas más rápido, pero a un costo de memoria bastante alto. Incluso en el segundo nivel de un trie, esa matriz es muy escasa. Cuando llegas al cuarto o quinto nivel, es casi todo el espacio muerto. Hice un análisis de eso en un momento dado. Miraré alrededor y veré si todavía tengo los números.

Encontré casi tan rápido tener una matriz de longitud variable en el nodo, con elementos ordenados por frecuencia. Más allá del segundo o tercer nivel del trie, el personaje que estaba buscando estaba casi siempre en la primera o segunda posición en esa matriz. Y el ahorro de espacio era bastante grande. En lugar de 26 referencias por nodo (104 bytes en mi implementación), tuve un recuento de un byte y luego cinco bytes por referencia. Entonces, mientras haya menos de 21 niños para un nodo en particular (que fue la mayor parte del tiempo), ahorré espacio. Hubo una pequeña penalización en el tiempo de ejecución, pero no lo suficiente en mi aplicación para importar.

Esa es la única modificación que tuve que hacer en mi estructura trie para que sea compatible con todos los idiomas alfabéticos con los que estaba trabajando. Como dije, estaba trabajando principalmente con idiomas de Europa Occidental, y para ellos funcionó a la perfección. Sé que funcionó con hebreo y árabe, pero no sé qué tan bien funcionó. Cumplió con nuestros propósitos, pero se desconoce si hubiera satisfecho a un hablante nativo.

El trie que construí funcionó lo suficientemente bien para nuestros propósitos con cualquier idioma cuyos caracteres encajen en el Plano Multilingüe Unicode Basic. Había un poco de rareza al trabajar con pares sustitutos, pero los ignoramos bastante. Básicamente, solo tratamos el par suplente como dos personajes y lo dejamos así.

Debe decidir si desea tratar los caracteres acentuados como caracteres separados o si desea mapearlos. Considere, por ejemplo, la palabra francesa "garçon", que algunas personas deletrearán "garcon", ya sea porque no saben nada mejor o porque no saben cómo hacer que el carácter sea ''ç''. Dependiendo de para qué estés usando el trie, puede que te resulte útil convertir los caracteres acentuados a sus equivalentes no acentuados. Pero supongo que es más un problema de limpieza de entrada que un problema de trie.

Esa es mi manera bastante larga de decir que un trie estándar debería funcionar bien para cualquier lenguaje alfabético, sin ninguna modificación específica del idioma. No veo ninguna forma obvia de usar un trie para un lenguaje logográfico. No sé nada acerca del Hangul coreano, así que no puedo decir si un trie sería útil allí.