c++ - comparar - ¿Cómo puedo determinar la distancia de Levenshtein para los caracteres chinos mandarines?

edit distance algorithm (1)

En primer lugar, solo para aclarar: un personaje chino no es como tal equivalente a una palabra alemana o inglesa. La mayoría de las cosas que considerarías como palabras (usando una definición semántica o sintáctica de "palabra") constan de 1 a 3 caracteres. Es fácil aplicar la distancia de Levenshtein a tales secuencias de caracteres representándolas como secuencias de puntos de código UCS-2 o UCS-4. Como la mayoría de las palabras son cortas (especialmente palabras de longitud 1 o 2 caracteres), puede ser de uso limitado.

Sin embargo, como su pregunta es específicamente sobre la distancia de edición entre caracteres individuales , creo que se requiere un enfoque diferente, y puede ser muy difícil.

Para empezar, debe representar a cada personaje como una secuencia de los componentes / trazos en los que se compone. Hay dos problemas:

Algunos componentes se componen de componentes incluso más pequeños, por lo que la forma de dividir un personaje en componentes "atómicos" no se define de forma exclusiva. Si lo haces hasta el nivel de golpes individuales, necesitarías una caracterización de cada golpe (posición dentro del personaje, forma, dirección, etc.). No creo que nadie haya hecho esto así (estaría más interesado si alguien me dice lo contrario).
Tendría que poner los trazos o componentes en un orden . El candidato obvio es el orden de trazo canónico del personaje, que se describe en lexica, e incluso hay sitios web de diccionario con diagramas de orden de trazo animados. Sin embargo, las fuentes de datos que conozco (para japonés) generan estas animaciones como secuencias de gráficos de mapa de bits; Nunca he visto códigos humanos o legibles por máquina que representen la secuencia de trazos (o incluso los nombres de trazos individuales) en una forma que sea adecuada para el cálculo de la distancia de edición.

Una última cosa que podría intentar, sin embargo, es renderizar los glifos de los caracteres y calcular la distancia de edición en función de cuántos píxeles (o vectores) se deben cambiar para convertir un carácter en otro. Una vez hice esto para caracteres latinos y combinaciones de caracteres (en píxeles) en el contexto de la postcorrección de OCR, y los resultados fueron bastante alentadores.

Una respuesta rápida a larsmans comente a continuación: Hay dos conceptos relacionados definidos por el estándar Unicode (en el siguiente me refiero a la versión 6.0, capítulo 12 ):

Un índice basado en radicales y recuentos de apoplejía. Cada personaje Han se compone de varios componentes, uno de los cuales es el radical. Un índice de recuento radical / trazo es una lista de caracteres ordenada por radical (es decir, todos los caracteres que comparten el mismo radical agrupados), y cada grupo específico de radical clasificado internamente por el número de trazos utilizados en el resto del personaje. Desafortunadamente, incluso esto no está definido de manera única: hay personajes cuyo radical se define de forma diferente por diferentes lexica tradicionales, y el conteo de trazos también puede ser difícil. Esto es lo que dice el Estándar Unicode:
Para agilizar la localización de caracteres ideográficos específicos de Han en los cuadros de códigos, se proporcionan índices de trazos radicales en el sitio web de Unicode. [...] La autoridad más influyente para la información sobre accidentes cerebrovasculares radicales es el diccionario KangXi del siglo XVIII, que contiene 214 radicales. El principal problema en el uso de radicales KangXi hoy en día es que muchos caracteres simplificados son difíciles de clasificar en cualquiera de los 214 radicales KangXi. Como resultado, se han introducido varios conjuntos radicales modernos. Ninguno, sin embargo, es de uso general, y los 214 radicales KangXi siguen siendo los más conocidos. [...] Los gráficos Unicode de trazos radicales se basan en los radicales KangXi. El estándar Unicode sigue una serie de diferentes fuentes para la clasificación de trazo radical. Cuando dos fuentes están en desacuerdo con el recuento radical o de trazo de un personaje dado, el personaje se muestra en ambas posiciones en los cuadros de trazo radical.
Tenga en cuenta que incluso si suponemos que el índice radical / de trazo no es ambiguo y correcto, no sería suficiente como fuente de información para transformar un carácter en una secuencia de componentes, ya que el único componente del carácter completamente descrito por este es el radical.
Secuencias de descripción ideográfica (sección 12.2): Unicode define puntos de código para los componentes básicos de los caracteres (la mayoría de ellos pueden usarse como caracteres independientes de todos modos), y hay puntos de código utilizados para unirlos para formar una secuencia de componentes que describe el composición de un personaje más complejo. Así que esto funciona de una manera similar a la combinación de personajes , pero hay diferencias importantes:
1. El orden de los componentes no está definido de forma exclusiva
2. No existe una definición de mecanismo de representación para tales secuencias
3. No existe un mapeo entre los caracteres ordinarios y las correspondientes secuencias de descripción ideográfica (aunque el Estándar menciona que tales mapeos, hasta cierto punto, existen en las fuentes que usaron para compilar el conjunto de caracteres Han).
El Estándar sugiere que las secuencias de descripción ideográfica se usen para describir caracteres complejos o raros que no están representados por ningún punto de código existente; pero desalienta explícitamente el uso de secuencias de descripción en lugar de caracteres comunes:
En particular, las Secuencias de descripción ideográfica no se deben usar para proporcionar representaciones gráficas alternativas de ideogramas codificados en el intercambio de datos. La búsqueda, la intercalación y otras operaciones de texto basadas en el contenido fallarían.

Estamos desarrollando un sistema para realizar coincidencias difusas en más de 50 idiomas internacionales utilizando el estándar de caracteres UTF-8, UTF-16 y UTF-32 Unicode. Hasta ahora, hemos podido utilizar la distancia de Levenshtein para detectar errores ortográficos de palabras de caracteres extendidos en alemán Unicode.

Nos gustaría extender este sistema para manejar ideogramas chinos mandarines representados en Unicode. ¿Cómo realizaríamos el cálculo de la distancia de Levenshtein entre caracteres chinos similares?