Colación

Recopilación es el ensamblaje de información escrita en un orden estándar. Muchos sistemas de cotejo se basan en el orden numérico o alfabético, o en extensiones y combinaciones de los mismos. 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í mismas 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 clasificación organice los elementos por clase.

Hablando formalmente, un método de colación normalmente define un orden total en un conjunto de posibles identificadores, llamados claves de ordenación, que en consecuencia produce un pedido anticipado total en el conjunto de elementos de información (los elementos con el mismo identificador no se colocan en ningún ordenar).

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 usar un algoritmo de clasificación para poner una lista de cualquier número de artículos en ese orden.

La principal ventaja de la intercalación es que hace que sea rápido y fácil para un usuario encontrar un elemento en la lista o confirmar que está ausente de la lista. En sistemas automáticos esto se puede hacer utilizando un algoritmo de búsqueda binaria o búsqueda por interpolación; la búsqueda manual se puede realizar usando un procedimiento más o menos similar, aunque esto a menudo se hará inconscientemente. Otras ventajas son que uno puede encontrar fácilmente el primer o el último elemento de la lista (lo más probable es que sea útil en el caso de datos ordenados numéricamente), o elementos en un rango determinado (útil nuevamente en el caso de datos numéricos, y también con datos ordenados alfabéticamente cuando uno puede estar seguro solo de las primeras letras del artículo o artículos buscados).

Pedidos

Numérico y cronológico

Las cadenas que representan números se pueden ordenar según los valores de los números que representan. Por ejemplo, "−4", "2.5", "10", "89", "30,000". Tenga en cuenta que la aplicación pura de este método puede proporcionar solo una ordenación parcial en las cadenas, ya que diferentes cadenas pueden representar el mismo número (como con "2" y "2.0" o, cuando sea científico se utiliza la notación "2e3" y "2000").

Se puede adoptar un enfoque similar con cadenas que representan fechas u otros elementos que se pueden ordenar cronológicamente o de alguna otra forma natural.

Alfabético

El orden alfabético es la base de muchos sistemas de recopilació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 sentido técnico estricto; los idiomas que usan un silabario o abugida, por ejemplo, el cherokee, pueden usar el mismo principio de ordenación siempre que haya un orden establecido para los símbolos usados).

Para decidir cuál de las dos cadenas viene primero en orden alfabético, inicialmente se comparan 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, entonces 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 va primero; por ejemplo, "cart" viene antes de "carhorse"). El resultado de organizar un conjunto de cadenas en orden alfabético es que las palabras con la misma primera letra se agrupan, y dentro de ese grupo se agrupan las palabras con las mismas dos primeras letras, y así sucesivamente.

Las letras mayúsculas normalmente se tratan como equivalentes a sus letras minúsculas correspondientes. (Para tratamientos alternativos en sistemas computarizados, consulte Cotejo automatizado, a continuación).

Pueden aplicarse ciertas limitaciones, complicaciones y convenciones especiales cuando se utiliza el orden alfabético:

• Cuando las cuerdas contienen espacios u otros divisores de palabras, se debe tomar la decisión de ignorar estos divisores o tratarlos como símbolos anteriores a todas las demás letras del alfabeto. Por ejemplo, si se toma el primer enfoque entonces "parque de coches" vendrá después de "carbono" y "carpa" (como lo haría si fuera escrito "carpark"), mientras que en el segundo enfoque "parque de coches" vendrá antes de esas dos palabras. La primera regla se utiliza en muchos diccionarios (pero no todos), el segundo en directorios telefónicos (así que Wilson, Jim K aparece con otras personas llamadas Wilson, Jim y no después de Wilson, Jimbo).
• Las Abreviaturas pueden ser tratadas como si fueran espeltadas en su totalidad. Por ejemplo, nombres que contienen "St." (corto para la palabra Inglés Saint) se ordenan a menudo como si fueran escritos como "Saint". También hay una convención tradicional en inglés que se apellidos que comienzan Mc y M ' se enumeran como si esos prefijos fueran escritos Mac.
• Las cuerdas que representan nombres personales a menudo se enumeran por orden alfabético de apellido, incluso si el nombre dado viene primero. Por ejemplo, Juan Hernandes y Brian O'Leary deben clasificarse como "Hernandes, Juan" y "O'Leary, Brian" aunque no estén escritos de esta manera.
• Palabras iniciales muy comunes, como El en inglés, se ignoran a menudo para fines de clasificación. Así que... El resplandor se clasificaría como "Shining" o "Shining, The".
• Cuando algunas de las cuerdas contienen numerales (o otros caracteres no letras), varios enfoques son posibles. A veces tales caracteres se tratan como si vinieran antes o después de todas las letras del alfabeto. Otro método es que los números se ordenen alfabéticamente como se deletrean: por ejemplo 1776 se clasificaría como si se deletreara "siete setenta y seis", y 24 heures du Mans como si deletreara "vingt-quatre..." (French for "twenty-four"). Cuando los números u otros símbolos se utilizan como formas gráficas especiales de letras, como en 1337 para la hoja o Se7en para el título de película Siete, pueden ser ordenados como si fueran esas cartas.
• Los idiomas tienen diferentes convenios para tratar letras modificadas y ciertas combinaciones de letras. Por ejemplo, en español la carta ñ se trata como carta básica siguiente n, y los digraphs ch y ll antes (hasta 1994) tratados como cartas básicas siguientes c y l, aunque ahora están alfabetizados como combinaciones de dos letras. Una lista de tales convenciones para varios idiomas se puede encontrar en el orden alfabético § Convenciones específicas del idioma.

En varios idiomas, las reglas han cambiado con el tiempo, por lo que los diccionarios más antiguos pueden usar un orden diferente al de los modernos. Además, la intercalación puede depender del uso. Por ejemplo, los directorios telefónicos y los diccionarios de alemán utilizan diferentes enfoques.

Ordenación por radicales y trazos

Vea también Indización de caracteres chinos

Otra forma de intercalación es la clasificación de 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 el orden por convención. En este sistema se identifican los componentes comunes de los personajes; estos se llaman radicales en chino y sistemas logográficos derivados del chino. Luego, los caracteres se agrupan por su radical principal y luego se ordenan por número de trazos de lápiz dentro de los radicales. Cuando no hay un radical obvio o más de un radical, la convención rige cuál se usa para la colación. Por ejemplo, el carácter chino 妈 (que significa "madre") se clasifica como un carácter de seis trazos bajo el radical primario de tres trazos 女.

El sistema de radicales y trazos es engorroso en comparación con un sistema alfabético en el que hay algunos caracteres, todos inequívocos. La elección de qué componentes de un logograma comprenden radicales separados y qué radical es primario no está bien definida. Como resultado, los lenguajes logográficos a menudo complementan la ordenación de radicales y trazos con la 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.

Además, en la Gran China, el orden de los trazos de los apellidos es una convención en algunos documentos oficiales en los que los nombres de las personas se enumeran sin jerarquía.

Automatización

Cuando la información se almacena en sistemas digitales, la recopilación puede convertirse en un proceso automatizado. Entonces es necesario implementar un algoritmo de colación apropiado que permita ordenar la información de manera 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.

El tipo más simple de intercalación automatizada 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 esta ordenación se extiende a las cadenas de acuerdo con los principios básicos de la ordenación alfabética (matemáticamente hablando, ordenación lexicográfica). Entonces, un programa de computadora podría tratar los caracteres a, b, C, d y $ como ordenado $, 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 comienzan con C, M o Z se ordenarán antes que las cadenas con minúsculas a, b, etc. Esto a veces se denomina orden ASCIIbetical. Esto se desvía del orden alfabético estándar, particularmente debido al orden de las letras mayúsculas antes que las minúsculas (y posiblemente el tratamiento de los espacios y otros caracteres que no son letras). Por lo tanto, a menudo se aplica con ciertas modificaciones, siendo la más obvia la conversión de mayúsculas y minúsculas (a menudo a mayúsculas, por razones históricas) antes de la comparación de los valores ASCII.

En muchos algoritmos de intercalación, la comparación no se basa en los códigos numéricos de los caracteres, sino en referencia a la secuencia de intercalación, una secuencia en la que se supone que los caracteres vienen con el propósito de colación, así como otras reglas de ordenamiento apropiadas para la aplicación dada. Esto puede servir para aplicar las convenciones correctas utilizadas para la ordenación alfabética en el idioma en cuestión, tratando adecuadamente con letras en mayúsculas y minúsculas, letras modificadas, dígrafos, abreviaturas particulares, etc., como se mencionó anteriormente en Orden alfabético, y en detalle en la artículo de pedido. Dichos algoritmos son potencialmente bastante complejos y posiblemente requieran varias pasadas por el texto.

Sin embargo, los problemas siguen siendo comunes cuando el algoritmo tiene que abarcar más de un idioma. Por ejemplo, en los diccionarios alemanes, la palabra ökonomisch se encuentra entre offenbar y olfaktorisch, mientras que los diccionarios turcos tratan o y ö como letras diferentes, colocando oyun antes de öbür.

Un algoritmo estándar para cotejar cualquier colección de cadenas compuesta por cualquier símbolo Unicode estándar es el algoritmo de cotejo Unicode. Esto se puede adaptar para usar la secuencia de clasificación adecuada para un idioma determinado al adaptar su tabla de clasificación predeterminada. Varias adaptaciones de este tipo se recopilan en el repositorio de datos de configuración regional común.

Claves de clasificación

En algunas aplicaciones, las cadenas por las que se ordenan los elementos pueden diferir de los identificadores que se muestran. Por ejemplo, The Shining podría clasificarse como Shining, The (consulte el orden alfabético anterior), pero es posible que desee mostrarlo como The Shining. yo>. En este caso, se pueden almacenar dos conjuntos de cadenas, uno con fines de visualización y otro con fines de clasificación. Las cadenas utilizadas para la intercalación de esta manera se denominan claves de ordenación.

Problemas con los números

A veces, se desea ordenar el 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 clasificación. Por ejemplo, Microsoft Windows hace esto cuando ordena los nombres de los archivos.

Ordenar correctamente los decimales es un poco más difícil, porque las diferentes regiones usan diferentes símbolos para un punto decimal y, a veces, el mismo carácter que se usa como punto decimal también se usa como separador, por ejemplo, "Sección 3.2.5& #34;. No existe una respuesta universal sobre cómo ordenar tales cadenas; cualquier regla depende de la aplicación.

Etiquetado de artículos pedidos

En algunos contextos, los números y las letras no se usan tanto como base para establecer un pedido, sino como un medio para etiquetar artículos que ya están pedidos. Por ejemplo, las páginas, secciones, capítulos y similares, así como los elementos de las listas, se "numeran" De este modo. Las series de etiquetado que se pueden utilizar incluyen números arábigos ordinarios (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 los elementos de la lista, sin numerarlos, es usar una lista con viñetas).

Cuando se utilizan letras de un alfabeto para este propósito de enumeración, existen ciertas convenciones específicas del idioma en cuanto a qué letras se utilizan. Por ejemplo, se omiten las letras rusas Ъ y Ь (que en la escritura solo se usan para modificar la consonante anterior), y generalmente también Ы, É y Ё. Además, en muchos idiomas que usan escritura latina extendida, las letras modificadas a menudo no se usan en la enumeración.