La intercalación es el conjunto de información escrita en un orden estándar. Muchos sistemas de intercalación se basan en el orden numérico o alfabético , o en extensiones y combinaciones de estos. La intercalación es un elemento fundamental de la mayoría de los sistemas de archivo de oficina , catálogos de bibliotecas y libros de referencia .
La intercalación se diferencia de la clasificación en que las clases en sí no están necesariamente ordenadas. Sin embargo, incluso si el orden de las clases es irrelevante, los identificadores de las clases pueden ser miembros de un conjunto ordenado, lo que permite que un algoritmo de ordenación ordene los elementos por clase.
Formalmente hablando, un método de intercalación normalmente define un orden total en un conjunto de identificadores posibles, llamados claves de clasificación, lo que en consecuencia produce un preorden total en el conjunto de elementos de información (los elementos con el mismo identificador no se colocan en ningún orden definido).
Un algoritmo de intercalación, como el algoritmo de intercalación Unicode, define un orden mediante el proceso de comparar dos cadenas de caracteres dadas y decidir cuál debe ir antes que la otra. Cuando se ha definido un orden de esta manera, se puede utilizar un algoritmo de ordenación para colocar una lista de cualquier número de elementos en ese orden.
La principal ventaja de la intercalación es que permite al usuario encontrar rápidamente un elemento en la lista o confirmar que no está en ella. En los sistemas automáticos, esto se puede hacer mediante un algoritmo de búsqueda binaria o una búsqueda por interpolación ; la búsqueda manual se puede realizar mediante un procedimiento similar, aunque a menudo se hará de forma inconsciente. Otras ventajas son que se pueden encontrar fácilmente los primeros o los últimos elementos de la lista (lo que probablemente sea útil en el caso de datos ordenados numéricamente) o los elementos de un rango determinado (lo que también es útil en el caso de datos numéricos y también con datos ordenados alfabéticamente, cuando se puede estar seguro de solo las primeras letras del elemento o elementos buscados).
Las cadenas que representan números se pueden ordenar en función de los valores de los números que representan. Por ejemplo, "−4", "2,5", "10", "89", "30 000". La aplicación pura de este método puede proporcionar solo un ordenamiento parcial de las cadenas, ya que diferentes cadenas pueden representar el mismo número (como ocurre con "2" y "2,0" o, cuando se utiliza la notación científica , "2e3" y "2000").
Se puede adoptar un enfoque similar con cadenas que representan fechas u otros elementos que pueden ordenarse cronológicamente o de alguna otra manera natural.
El orden alfabético es la base de muchos sistemas de ordenación en los que los elementos de información se identifican mediante cadenas que consisten principalmente en letras de un alfabeto . El orden de las cadenas se basa en la existencia de un orden estándar para las letras del alfabeto en cuestión. (El sistema no se limita a los alfabetos en el sentido técnico estricto; los idiomas que utilizan un silabario o abugida , por ejemplo el cheroqui , pueden utilizar el mismo principio de ordenación siempre que exista un orden establecido para los símbolos utilizados).
Para decidir cuál de dos cadenas aparece primero en orden alfabético, se comparan inicialmente sus primeras letras. La cadena cuya primera letra aparece antes en el alfabeto aparece primero en orden alfabético. Si las primeras letras son iguales, se comparan las segundas letras, y así sucesivamente, hasta que se decide el orden. (Si una cadena se queda sin letras para comparar, se considera que aparece primero; por ejemplo, "cart" aparece antes de "carthorse"). El resultado de ordenar un conjunto de cadenas en orden alfabético es que las palabras con la misma primera letra se agrupan juntas, y dentro de ese grupo las palabras con las mismas dos primeras letras se agrupan juntas, y así sucesivamente.
Las letras mayúsculas suelen tratarse como equivalentes a sus letras minúsculas correspondientes. (Para tratamientos alternativos en sistemas informáticos, consulte la sección Intercalación automática, a continuación).
Pueden aplicarse ciertas limitaciones, complicaciones y convenciones especiales cuando se utiliza el orden alfabético:
En varios idiomas, las reglas han cambiado con el tiempo, por lo que los diccionarios más antiguos pueden utilizar un orden diferente al de los modernos. Además, la ordenación puede depender del uso. Por ejemplo, los diccionarios alemanes y las guías telefónicas utilizan enfoques diferentes.
Algunos diccionarios árabes , como el bilingüe Diccionario de árabe escrito moderno de Hans Wehr , agrupan y clasifican palabras árabes por raíz semítica . [1] Por ejemplo, las palabras kitāba ( كتابة 'escritura'), kitāb ( كتاب 'libro'), kātib ( كاتب 'escritor'), maktaba ( مكتبة 'biblioteca'), maktab ( مكتب 'oficina'), maktūb ( مكتوب 'destino' o 'escrito'), se aglomeran bajo la raíz triliteral k - t - b ( ك ت ب ), que denota 'escritura'. [2]
Otra forma de ordenación es la clasificación por radicales y trazos , utilizada para sistemas de escritura no alfabéticos como el hanzi del chino y el kanji del japonés , cuyos miles de símbolos desafían la ordenación por convención. En este sistema, se identifican los componentes comunes de los caracteres; estos se denominan radicales en chino y en los sistemas logográficos derivados del chino. Luego, los caracteres se agrupan por su radical primario y luego se ordenan por el número de trazos de lápiz dentro de los radicales. Cuando no hay un radical obvio o más de uno, la convención rige cuál se usa para la ordenación. Por ejemplo, el carácter chino 妈 (que significa "madre") se clasifica como un carácter de seis trazos debajo del radical primario de tres trazos 女.
El sistema de radicales y trazos es complicado en comparación con un sistema alfabético en el que hay unos pocos caracteres, todos inequívocos. La elección de qué componentes de un logograma comprenden radicales separados y qué radical es el primario no es clara. Como resultado, los idiomas logográficos a menudo complementan el ordenamiento de radicales y trazos con una clasificación alfabética de una conversión fonética de los logogramas. Por ejemplo, la palabra kanji Tōkyō (東京) se puede ordenar como si estuviera escrita en los caracteres japoneses del silabario hiragana como "to-u-ki- yo -u" (とうきょう), utilizando el orden de clasificación convencional para estos caracteres. [ cita requerida ]
Además, los caracteres chinos también se pueden ordenar por trazos . En la Gran China, el orden de trazos de los apellidos es una convención en algunos documentos oficiales donde los nombres de las personas se enumeran sin jerarquía.
Cuando la información se almacena en sistemas digitales, la clasificación puede convertirse en un proceso automatizado. En ese caso, es necesario implementar un algoritmo de clasificación adecuado que permita ordenar la información de forma satisfactoria para la aplicación en cuestión. A menudo, el objetivo será lograr un orden alfabético o numérico que siga los criterios estándar descritos en las secciones anteriores. Sin embargo, no todos estos criterios son fáciles de automatizar. [3]
El tipo más simple de intercalación automática se basa en los códigos numéricos de los símbolos en un conjunto de caracteres , como la codificación ASCII (o cualquiera de sus superconjuntos como Unicode ), con los símbolos ordenados en orden numérico creciente de sus códigos, y este orden se extiende a las cadenas de acuerdo con los principios básicos del orden alfabético (matemáticamente hablando, orden lexicográfico ). Por lo tanto, un programa de computadora podría tratar los caracteres a , b , C , d y $ como si estuvieran ordenados $ , C , a , b , d (los códigos ASCII correspondientes son $ = 36, a = 97, b = 98, C = 67 y d = 100). Por lo tanto, las cadenas que comiencen con C , M o Z se ordenarían antes que las cadenas con a , b , etc. en minúsculas. Esto a veces se llama orden ASCIIbético . Esto se desvía del orden alfabético estándar, en particular debido a la ordenación de las letras mayúsculas antes de todas las minúsculas (y posiblemente al tratamiento de los espacios y otros caracteres que no son letras). Por lo tanto, a menudo se aplica con ciertas modificaciones, la más obvia es la conversión de mayúsculas y minúsculas (a menudo a mayúsculas, por razones históricas [nota 1] ) antes de la comparación de los valores ASCII.
En muchos algoritmos de cotejo, la comparación no se basa en los códigos numéricos de los caracteres, sino en referencia a la secuencia de cotejo (una secuencia en la que se supone que se encuentran los caracteres para el propósito del cotejo), así como otras reglas de ordenamiento apropiadas para la aplicación dada. Esto puede servir para aplicar las convenciones correctas utilizadas para el ordenamiento alfabético en el idioma en cuestión, tratando adecuadamente letras con mayúsculas y minúsculas diferentes, letras modificadas , dígrafos , abreviaturas particulares, etc., como se mencionó anteriormente en Orden alfabético, y en detalle en el artículo Orden alfabético . Estos algoritmos son potencialmente bastante complejos, posiblemente requieran varias pasadas a través del texto. [3]
No obstante, los problemas siguen siendo habituales cuando el algoritmo tiene que abarcar más de un idioma. Por ejemplo, en los diccionarios alemanes la palabra ökonomisch aparece entre offenbar y olfaktorisch , mientras que en los diccionarios turcos se trata a o y ö como letras diferentes, colocando oyun antes de öbür .
Un algoritmo estándar para cotejar cualquier conjunto de cadenas compuestas por cualquier símbolo Unicode estándar es el Algoritmo de cotejo Unicode . Este se puede adaptar para utilizar la secuencia de cotejo adecuada para un idioma determinado mediante la adaptación de su tabla de cotejo predeterminada. Varias de estas adaptaciones se recopilan en Common Locale Data Repository .
En algunas aplicaciones, las cadenas por las que se ordenan los elementos pueden diferir de los identificadores que se muestran. Por ejemplo, El resplandor podría ordenarse como El resplandor, El (consulte Orden alfabético más arriba), pero aún así puede desearse mostrarlo como El resplandor . En este caso, se pueden almacenar dos conjuntos de cadenas, uno para fines de visualización y otro para fines de ordenación. Las cadenas utilizadas para la ordenación de esta manera se denominan claves de ordenación .
A veces, se desea ordenar texto con números incrustados utilizando el orden numérico adecuado. Por ejemplo, "Figura 7b" va antes de "Figura 11a", aunque '7' viene después de '1' en Unicode . Esto se puede extender a los números romanos . Este comportamiento no es particularmente difícil de producir siempre que solo se ordenen números enteros, aunque puede ralentizar significativamente la ordenación. Por ejemplo, Microsoft Windows hace esto al ordenar nombres de archivos .
Ordenar los decimales correctamente es un poco más difícil, porque las distintas configuraciones regionales utilizan símbolos diferentes para el punto decimal y, a veces, el mismo carácter utilizado como punto decimal también se utiliza como separador, por ejemplo, "Sección 3.2.5". No existe una respuesta universal sobre cómo ordenar dichas cadenas; las reglas dependen de la aplicación.
En algunos contextos, los números y las letras se utilizan no tanto como base para establecer un orden, sino como un medio para etiquetar elementos que ya están ordenados. Por ejemplo, las páginas, secciones, capítulos y similares, así como los elementos de las listas, se "numeran" con frecuencia de esta manera. Las series de etiquetado que se pueden utilizar incluyen números arábigos comunes (1, 2, 3, ...), números romanos (I, II, III, ... o i, ii, iii, ...) o letras (A, B, C, ... o a, b, c, ...). (Un método alternativo para indicar elementos de lista, sin numerarlos, es utilizar una lista con viñetas ).
Cuando se utilizan letras de un alfabeto para este propósito de enumeración , existen ciertas convenciones específicas de cada idioma en cuanto a qué letras se utilizan. Por ejemplo, se omiten las letras rusas Ъ y Ь (que en la escritura solo se utilizan para modificar la consonante precedente ), y normalmente también Ы , Й y Ё. Además, en muchos idiomas que utilizan la escritura latina extendida , las letras modificadas a menudo no se utilizan en la enumeración.
