Cadena (informática)

Las cuerdas suelen estar compuestas de personajes. Son útiles para almacenar datos legibles por humanos, como oraciones, o listas de datos alfabéticos, como las secuencias de ácido nucleico del ADN.

En programación informática, una cadena es tradicionalmente una secuencia de caracteres, ya sea como una constante literal o como algún tipo de variable. Este último puede permitir la mutación de sus elementos y el cambio de longitud, o puede ser fijo (después de la creación). Una cadena generalmente se considera un tipo de datos y, a menudo, se implementa como una estructura de datos de matriz de bytes (o palabras) que almacena una secuencia de elementos, generalmente caracteres, utilizando alguna codificación de caracteres. String también puede denotar matrices más generales u otros tipos y estructuras de datos de secuencia (o lista).

Según el lenguaje de programación y el tipo de datos preciso utilizado, una variable declarada como una cadena puede hacer que el almacenamiento en la memoria se asigne estáticamente para una longitud máxima predeterminada o emplear una asignación dinámica para permitir que contenga una cantidad variable de elementos..

Cuando una cadena aparece literalmente en el código fuente, se conoce como cadena literal o cadena anónima.

En los lenguajes formales, que se utilizan en la lógica matemática y la informática teórica, una cadena es una secuencia finita de símbolos que se eligen de un conjunto denominado alfabeto.

Tipos de datos de cadena

Un tipo de datos de cadena es un tipo de datos modelado sobre la idea de una cadena formal. Las cadenas son un tipo de datos tan importante y útil que se implementan en casi todos los lenguajes de programación. En algunos idiomas están disponibles como tipos primitivos y en otros como tipos compuestos. La sintaxis de la mayoría de los lenguajes de programación de alto nivel permite que una cadena, generalmente citada de alguna manera, represente una instancia de un tipo de datos de cadena; una metacadena de este tipo se llama literal o literal de cadena.

Longitud de la cadena

Aunque las cadenas formales pueden tener una longitud finita arbitraria, la longitud de las cadenas en los lenguajes reales suele estar restringida a un máximo artificial. En general, hay dos tipos de tipos de datos de cadena: cadenas de longitud fija, que tienen una longitud máxima fija que se determina en el momento de la compilación y que usan la misma cantidad de memoria, ya sea que se necesite este máximo o no., y cadenas de longitud variable, cuya longitud no se fija arbitrariamente y que pueden usar cantidades variables de memoria según los requisitos reales en tiempo de ejecución (consulte Administración de memoria). La mayoría de las cadenas en los lenguajes de programación modernos son cadenas de longitud variable. Por supuesto, incluso las cadenas de longitud variable tienen una longitud limitada, por el tamaño de la memoria disponible de la computadora. La longitud de la cadena se puede almacenar como un número entero separado (que puede poner otro límite artificial a la longitud) o implícitamente a través de un carácter de terminación, generalmente un valor de carácter con todos los bits en cero, como en el lenguaje de programación C. Véase también "Terminado en nulo" debajo.

Codificación de caracteres

Históricamente, los tipos de datos de cadena han asignado un byte por carácter y, aunque el juego de caracteres exacto variaba según la región, las codificaciones de caracteres eran lo suficientemente similares como para que los programadores a menudo ignoraran esto, ya que los caracteres que un programa trataba de manera especial (como punto y espacio y coma) estaban en el mismo lugar en todas las codificaciones que encontraría un programa. Estos conjuntos de caracteres se basaban normalmente en ASCII o EBCDIC. Si el texto en una codificación se mostraba en un sistema que usaba una codificación diferente, el texto a menudo se alteraba, aunque a menudo era algo legible y algunos usuarios de computadoras aprendían a leer el texto alterado.

Los lenguajes logográficos como el chino, el japonés y el coreano (conocidos colectivamente como CJK) necesitan mucho más de 256 caracteres (el límite de una codificación de un byte de 8 bits por carácter) para una representación razonable. Las soluciones normales implicaban mantener representaciones de un solo byte para ASCII y usar representaciones de dos bytes para ideogramas CJK. El uso de estos con el código existente generaba problemas con la coincidencia y el corte de cadenas, cuya gravedad dependía de cómo se diseñara la codificación de caracteres. Algunas codificaciones, como la familia EUC, garantizan que un valor de byte en el rango ASCII representará solo ese carácter ASCII, lo que hace que la codificación sea segura para los sistemas que usan esos caracteres como separadores de campo. Otras codificaciones, como ISO-2022 y Shift-JIS, no ofrecen tales garantías, lo que hace que la coincidencia de códigos de bytes no sea segura. Estas codificaciones tampoco se "autosincronizaban", por lo que la ubicación de los límites de los caracteres requería retroceder hasta el comienzo de una cadena, y pegar dos cadenas juntas podría dañar la segunda cadena.

Unicode ha simplificado un poco la imagen. La mayoría de los lenguajes de programación ahora tienen un tipo de datos para cadenas Unicode. El formato de flujo de bytes preferido de Unicode, UTF-8, está diseñado para no tener los problemas descritos anteriormente para las codificaciones de varios bytes más antiguas. UTF-8, UTF-16 y UTF-32 requieren que el programador sepa que las unidades de código de tamaño fijo son diferentes a los "caracteres", la principal dificultad actualmente son las API diseñadas incorrectamente que intentan ocultar esta diferencia (UTF-32 hace puntos de código de tamaño fijo, pero estos no son "caracteres" debido a los códigos de composición).

Implementaciones

Algunos lenguajes, como C++, Perl y Ruby, normalmente permiten cambiar el contenido de una cadena después de haberla creado; se denominan cadenas mutables. En otros lenguajes, como Java, JavaScript, Lua, Python y Go, el valor es fijo y se debe crear una nueva cadena si se va a realizar alguna modificación; estos se denominan cadenas inmutables. Algunos de estos lenguajes con cadenas inmutables también proporcionan otro tipo que es mutable, como Java y StringBuilder de.NET, el StringBuffer de Java seguro para subprocesos y el Cacao NSMutableString. La inmutabilidad tiene ventajas y desventajas: aunque las cadenas inmutables pueden requerir la creación ineficiente de muchas copias, son más simples y completamente seguras para subprocesos.

Las cadenas generalmente se implementan como matrices de bytes, caracteres o unidades de código para permitir un acceso rápido a unidades o subcadenas individuales, incluidos los caracteres cuando tienen una longitud fija. Algunos lenguajes como Haskell los implementan como listas enlazadas.

Algunos lenguajes, como Prolog y Erlang, evitan implementar un tipo de datos de cadena dedicado y, en su lugar, adoptan la convención de representar cadenas como listas de códigos de caracteres.

Representaciones

Las representaciones de cadenas dependen en gran medida de la elección del repertorio de caracteres y del método de codificación de caracteres. Las implementaciones de cadenas más antiguas se diseñaron para trabajar con el repertorio y la codificación definidos por ASCII, o extensiones más recientes como la serie ISO 8859. Las implementaciones modernas a menudo usan el extenso repertorio definido por Unicode junto con una variedad de codificaciones complejas como UTF-8 y UTF-16.

El término cadena de bytes generalmente indica una cadena de bytes de uso general, en lugar de cadenas de solo caracteres (legibles), cadenas de bits o similares. Las cadenas de bytes a menudo implican que los bytes pueden tomar cualquier valor y cualquier dato se puede almacenar tal cual, lo que significa que no debe haber ningún valor interpretado como un valor de terminación.

La mayoría de las implementaciones de cadenas son muy similares a las matrices de longitud variable con las entradas que almacenan los códigos de caracteres de los caracteres correspondientes. La principal diferencia es que, con ciertas codificaciones, un solo carácter lógico puede ocupar más de una entrada en la matriz. Esto sucede, por ejemplo, con UTF-8, donde los códigos individuales (puntos de código UCS) pueden ocupar de uno a cuatro bytes, y los caracteres individuales pueden ocupar un número arbitrario de códigos. En estos casos, la longitud lógica de la cadena (número de caracteres) difiere de la longitud física de la matriz (número de bytes en uso). UTF-32 evita la primera parte del problema.

Terminado en nulo

La longitud de una cadena se puede almacenar implícitamente usando un carácter de terminación especial; a menudo, este es el carácter nulo (NUL), que tiene todos los bits cero, una convención utilizada y perpetuada por el popular lenguaje de programación C. Por lo tanto, esta representación se conoce comúnmente como una cadena C. Esta representación de una cadena de caracteres n ocupa n + 1 espacio (1 para el terminador) y, por lo tanto, es una estructura de datos implícita.

En cadenas terminadas, el código de terminación no es un carácter permitido en ninguna cadena. Las cadenas con el campo longitud no tienen esta limitación y también pueden almacenar datos binarios arbitrarios.

Un ejemplo de una cadena terminada en nulo almacenada en un búfer de 10 bytes, junto con su representación ASCII (o UTF-8 más moderna) como números hexadecimales de 8 bits es:

La longitud de la cadena en el ejemplo anterior, "FRANK", es de 5 caracteres, pero ocupa 6 bytes. Los caracteres posteriores al terminador no forman parte de la representación; pueden ser parte de otros datos o simplemente basura. (Las cadenas de esta forma a veces se denominan cadenas ASCIZ, por la directiva del lenguaje ensamblador original que se usó para declararlas).

Terminado en bytes y bits

El uso de un byte especial que no sea nulo para terminar cadenas ha aparecido históricamente tanto en hardware como en software, aunque a veces con un valor que también era un carácter de impresión. $ fue usado por muchos sistemas ensambladores, : usado por sistemas CDC (este carácter tenía un valor de cero), y el ZX80 usó " ya que este era el delimitador de cadena en su lenguaje BASIC.

Algo similar, "procesamiento de datos" máquinas como la IBM 1401 usaban un bit de marca de palabra especial para delimitar cadenas a la izquierda, donde la operación comenzaría a la derecha. Este bit tenía que estar claro en todas las demás partes de la cadena. Esto significó que, mientras que el IBM 1401 tenía una palabra de siete bits, casi nadie pensó en usar esto como una función y anular la asignación del séptimo bit para (por ejemplo) manejar códigos ASCII.

El software de las primeras microcomputadoras se basaba en el hecho de que los códigos ASCII no usan el bit de orden superior y lo configuraban para indicar el final de una cadena. Debe restablecerse a 0 antes de la salida.

Prefijo de longitud

La longitud de una cadena también se puede almacenar de forma explícita, por ejemplo, prefijando la cadena con la longitud como un valor de byte. Esta convención se usa en muchos dialectos de Pascal; como consecuencia, algunas personas llaman a esta cadena cadena Pascal o cadena P. El almacenamiento de la longitud de la cadena como byte limita la longitud máxima de la cadena a 255. Para evitar tales limitaciones, las implementaciones mejoradas de cadenas P utilizan palabras de 16, 32 o 64 bits para almacenar la longitud de la cadena. Cuando el campo longitud cubre el espacio de direcciones, las cadenas están limitadas solo por la memoria disponible.

Si la longitud está limitada, entonces se puede codificar en un espacio constante, generalmente una palabra de máquina, lo que lleva a una estructura de datos implícita, tomando n + k espacio, donde k es el número de caracteres en una palabra (8 para ASCII de 8 bits en una máquina de 64 bits, 1 para UTF-32/UCS-4 de 32 bits en una máquina de 32 bits, etc.). Si la longitud no está limitada, la codificación de una longitud n ocupa espacio log(n) (consulte el código de longitud fija), por lo que las cadenas con prefijo de longitud son una estructura de datos sucinta. codificando una cadena de longitud n en log(n) + espacio n.

En el último caso, el campo de prefijo de longitud en sí mismo no tiene una longitud fija, por lo tanto, los datos de la cadena real deben moverse cuando la cadena crece, de modo que el campo de longitud debe aumentarse.

Aquí hay una cadena Pascal almacenada en un búfer de 10 bytes, junto con su representación ASCII/UTF-8:

Cadenas como registros

Muchos lenguajes, incluidos los orientados a objetos, implementan cadenas como registros con una estructura interna como:

clase cuerda {} size_t longitud; char *texto;};

Sin embargo, dado que la implementación suele estar oculta, se debe acceder a la cadena y modificarla a través de funciones miembro. text es un puntero a un área de memoria asignada dinámicamente, que puede expandirse según sea necesario. Véase también cadena (C++).

Otras representaciones

Tanto la terminación de caracteres como los códigos de longitud limitan las cadenas: por ejemplo, las matrices de caracteres C que contienen caracteres nulos (NUL) no pueden ser manejadas directamente por las funciones de la biblioteca de cadenas C: las cadenas que usan un código de longitud están limitadas al valor máximo del código de longitud.

Estas dos limitaciones se pueden superar mediante una programación inteligente.

Es posible crear estructuras de datos y funciones que los manipulen sin los problemas asociados con la terminación de caracteres y, en principio, pueden superar los límites de longitud del código. También es posible optimizar la cadena representada utilizando técnicas de codificación de longitud de ejecución (reemplazo de caracteres repetidos por el valor del carácter y una longitud) y codificación Hamming.

Si bien estas representaciones son comunes, otras son posibles. El uso de cuerdas hace que ciertas operaciones con cadenas, como inserciones, eliminaciones y concatenaciones, sean más eficientes.

La estructura de datos central en un editor de texto es la que administra la cadena (secuencia de caracteres) que representa el estado actual del archivo que se está editando. Si bien ese estado podría almacenarse en una sola matriz larga y consecutiva de caracteres, un editor de texto típico usa una representación alternativa como su estructura de datos de secuencia: un búfer de espacios, una lista vinculada de líneas, una tabla de piezas o una cuerda, lo que hace que Ciertas operaciones de cadena, como inserciones, eliminaciones y deshacer ediciones anteriores, más eficientes.

Preocupaciones de seguridad

El diseño diferente de la memoria y los requisitos de almacenamiento de las cadenas pueden afectar la seguridad del programa que accede a los datos de la cadena. Las representaciones de cadenas que requieren un carácter de terminación son comúnmente susceptibles a problemas de desbordamiento de búfer si el carácter de terminación no está presente, causado por un error de codificación o por un atacante que alteró deliberadamente los datos. Las representaciones de cadenas que adoptan un campo de longitud separado también son susceptibles si la longitud se puede manipular. En tales casos, el código de programa que accede a los datos de la cadena requiere una verificación de límites para garantizar que no acceda o cambie inadvertidamente los datos fuera de los límites de la memoria de la cadena.

Los datos de cadena se obtienen con frecuencia de la entrada del usuario a un programa. Como tal, es responsabilidad del programa validar la cadena para garantizar que represente el formato esperado. Realizar una validación limitada o nula de la entrada del usuario puede hacer que un programa sea vulnerable a los ataques de inyección de código.

Cadenas literales

A veces, las cadenas deben estar incrustadas dentro de un archivo de texto que sea legible por humanos y destinado a ser consumido por una máquina. Esto es necesario, por ejemplo, en el código fuente de los lenguajes de programación o en los archivos de configuración. En este caso, el carácter NUL no funciona bien como terminador, ya que normalmente es invisible (no imprimible) y es difícil de ingresar a través de un teclado. El almacenamiento de la longitud de la cadena también sería un inconveniente, ya que el cálculo manual y el seguimiento de la longitud son tediosos y propensos a errores.

Dos representaciones comunes son:

• Rodeado de comillas (ASCII 0x22 doble cita "str" o ASCII 0x27 sola cita 'str'), utilizado por la mayoría de idiomas de programación. Para poder incluir caracteres especiales como la marca de citas, caracteres de nueva línea o caracteres no imprimibles, las secuencias de escape están disponibles a menudo, normalmente prefijados con el carácter de la barra de atrás (ASCII 0x5C).
• Terminado por una secuencia de nueva línea, por ejemplo en archivos INI de Windows.

Cadenas sin texto

Si bien las cadenas de caracteres son usos muy comunes de cadenas, una cadena en informática puede referirse genéricamente a cualquier secuencia de datos tipificados homogéneamente. Una cadena de bits o cadena de bytes, por ejemplo, puede usarse para representar datos binarios no textuales recuperados de un medio de comunicación. Estos datos pueden o no estar representados por un tipo de datos específico de cadena, según las necesidades de la aplicación, el deseo del programador y las capacidades del lenguaje de programación que se utiliza. Si la implementación de cadenas del lenguaje de programación no está limpia en 8 bits, es posible que se dañen los datos.

Los programadores de C distinguen claramente entre una "cadena", también conocida como "cadena de caracteres", que por definición siempre termina en un valor nulo, y una "cadena de bytes& #34; o "pseudocadena" que puede almacenarse en la misma matriz, pero a menudo no termina en nulo. El uso de funciones de manejo de cadenas C en una "cadena de bytes" a menudo parece funcionar, pero luego conduce a problemas de seguridad.

Algoritmos de procesamiento de cadenas

Hay muchos algoritmos para procesar cadenas, cada uno con varias compensaciones. Los algoritmos de la competencia se pueden analizar con respecto al tiempo de ejecución, los requisitos de almacenamiento, etc. El nombre stringology fue acuñado en 1984 por el científico informático Zvi Galil para la teoría de los algoritmos y las estructuras de datos utilizadas para el procesamiento de cadenas.

Algunas categorías de algoritmos incluyen:

• Criar algoritmos de búsqueda para encontrar una subestring o patrón dado
• algoritmos de manipulación de cuerdas
• Clasificación de algoritmos
• algoritmos de expresión regular
• Parsing a string
• Minería de secuencias

Los algoritmos de cadena avanzados a menudo emplean estructuras de datos y mecanismos complejos, entre ellos árboles de sufijos y máquinas de estado finito.

Lenguajes y utilidades orientados a cadenas de caracteres

Las cadenas de caracteres son un tipo de datos tan útil que se han diseñado varios lenguajes para que las aplicaciones de procesamiento de cadenas sean fáciles de escribir. Los ejemplos incluyen los siguientes idiomas:

• awk
• Icon
• MUMPS
• Perl
• Rexx
• Ruby
• sed
• SNOBOL
• Tcl
• TTM

Muchas utilidades de Unix realizan manipulaciones de cadenas simples y se pueden usar para programar fácilmente algunos algoritmos de procesamiento de cadenas potentes. Los archivos y los flujos finitos se pueden ver como cadenas.

Algunas API, como la interfaz de control multimedia, SQL incorporado o printf, usan cadenas para contener los comandos que se interpretarán.

Muchos lenguajes de programación de secuencias de comandos, incluidos Perl, Python, Ruby y Tcl, emplean expresiones regulares para facilitar las operaciones de texto. Perl se destaca particularmente por su uso de expresiones regulares, y muchos otros lenguajes y aplicaciones implementan expresiones regulares compatibles con Perl.

Algunos lenguajes, como Perl y Ruby, admiten la interpolación de cadenas, lo que permite evaluar e incluir expresiones arbitrarias en cadenas literales.

Funciones de cadenas de caracteres

Las funciones de cadena se utilizan para crear cadenas o cambiar el contenido de una cadena mutable. También se utilizan para consultar información sobre una cadena. El conjunto de funciones y sus nombres varía según el lenguaje de programación de la computadora.

El ejemplo más básico de una función de cadena es la función de longitud de cadena: la función que devuelve la longitud de una cadena (sin contar los caracteres de terminación ni la información estructural interna de la cadena) y no modifica la cuerda. Esta función a menudo se denomina length o len. Por ejemplo, length("hello world") devolvería 11. Otra función común es la concatenación, donde se crea una nueva cadena agregando dos cadenas, a menudo este es el operador de suma +.

Algunas arquitecturas de conjuntos de instrucciones de microprocesadores contienen soporte directo para operaciones de cadena, como la copia de bloques (por ejemplo, en Intel x86m REPNZ MOVSB).

Teoría formal

Sea Σ un conjunto finito de símbolos (alternativamente llamados caracteres), llamado alfabeto. No se hace ninguna suposición sobre la naturaleza de los símbolos. Una cadena (o palabra) sobre Σ es cualquier secuencia finita de símbolos de Σ. Por ejemplo, si Σ = {0, 1}, entonces 01011 es una cadena sobre Σ.

La longitud de una cadena s es el número de símbolos en s (la longitud de la secuencia) y puede ser cualquiera que no sea entero negativo; a menudo se denota como |s|. La cadena vacía es la cadena única sobre Σ de longitud 0, y se denota ε o λ.

El conjunto de todas las cadenas sobre Σ de longitud n se denota como Σn. Por ejemplo, si Σ = {0, 1}, entonces Σ2 = {00, 01, 10, 11}. Tenga en cuenta que Σ0 = {ε} para cualquier alfabeto Σ.

El conjunto de todas las cadenas sobre Σ de cualquier longitud es el cierre de Kleene de Σ y se denota como Σ*. En términos de Σn,

${displaystyle Sigma ^{*}=bigcup _{nin mathbb {N} cup {0} Sigma$

Por ejemplo, si Σ = {0, 1}, entonces Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011,...}. Aunque el conjunto Σ* en sí mismo es contablemente infinito, cada elemento de Σ* es una cadena de longitud finita.

Un conjunto de cadenas sobre Σ (es decir, cualquier subconjunto de Σ*) se denomina lenguaje formal sobre Σ. Por ejemplo, si Σ = {0, 1}, el conjunto de cadenas con un número par de ceros, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111,...}, es un lenguaje formal sobre Σ.

Concatenación y subcadenas

La concatenación es una operación binaria importante en Σ*. Para dos cadenas cualesquiera s y t en Σ*, su concatenación se define como la secuencia de símbolos en s seguido por la secuencia de caracteres en t, y se denota st. Por ejemplo, si Σ = {a, b,..., z}, s = bear, y t = abrazo, luego st = bearhug y ts = hugbear.

La concatenación de cuerdas es una operación asociativa, pero no recíproca. El ε de cadena vacía sirve como elemento de identidad; para cualquier cadena s, εs = sε = s. Por lo tanto, el conjunto de la* y la operación de concatenación forman un monoide, el monoide libre generado por la bah. Además, la función de longitud define un homomorfismo monoide de la* a los enteros no negativos (es decir, una función ${displaystyle L:Sigma ^{*}mapsto mathbb {N} cup {0}$, tal que ${displaystyle L(st)=L(s)+L(t)quad forall s,tin Sigma ^{*}$).

Se dice que una cadena s es una subcadena o factor de t si existe (posiblemente vacío) cadenas u y v tales que t = usv. La relación "es una subcadena de " define un orden parcial en Σ*, cuyo elemento mínimo es la cadena vacía.

Prefijos y sufijos

Se dice que una cadena s es un prefijo de t si existe una cadena u tal que t = su. Si u no está vacío, se dice que s es un prefijo propio de t. Simétricamente, se dice que una cadena s es un sufijo de t si existe una cadena u tal que t = nosotros. Si u no está vacío, se dice que s es un sufijo propio de t. Los sufijos y prefijos son subcadenas de t. Ambas relaciones "es un prefijo de" y "es un sufijo de" son órdenes de prefijo.

Reversión

El reverso de una cadena es una cadena con los mismos símbolos pero en orden inverso. Por ejemplo, si s = abc (donde a, b y c son símbolos del alfabeto), entonces el reverso de s es cba. Una cadena que es el reverso de sí misma (por ejemplo, s = señora) se llama palíndromo, que también incluye la cadena vacía y todas las cadenas de longitud 1.

Rotaciones

Se dice que una cadena s = uv es una rotación de t si t = vu. Por ejemplo, si Σ = {0, 1} la cadena 0011001 es una rotación de 0100110, donde u = 00110 y v = 01. Como otro ejemplo, la cadena abc tiene tres rotaciones diferentes, a saber. abc mismo (con u=abc, v=ε), bca (con u=bc, v= a) y cab (con u=c, v=ab).

Orden lexicográfico

Suele ser útil definir un orden en un conjunto de cadenas. Si el alfabeto Σ tiene un orden total (cf. orden alfabético) se puede definir un orden total en Σ* llamado orden lexicográfico. Por ejemplo, si Σ = {0, 1} y 0 < 1, entonces el orden lexicográfico en Σ* incluye las relaciones ε < 0 < 00 < 000 <... < 0001 < 001 < 01 < 010 < 011 < 0110 < 01111 < 1 < 10 < 100 < 101 < 111 < 1111 < 11111... El orden lexicográfico es total si lo es el orden alfabético, pero no está bien fundado para ningún alfabeto no trivial, aunque lo sea el orden alfabético.

Consulte Shortlex para conocer un orden de cadenas alternativo que preserva la solidez.

Operaciones de cadenas

Varias operaciones adicionales en cadenas ocurren comúnmente en la teoría formal. Estos se dan en el artículo sobre operaciones de cadena.

Topología

(Hyper)cube de cadenas binarias de longitud 3

Las cadenas admiten la siguiente interpretación como nodos en un gráfico, donde k es el número de símbolos en Σ:

• cuerdas de longitud fijas n se puede ver como los lugares enteros en un n- hipercubo dimensional con lados de longitud k-1.
• Las cuerdas de longitud variable (de longitud finita) se pueden ver como nodos en un árbol perfecto k-ary.
• Las cuerdas infinitas (otros no considerados aquí) pueden ser vistas como caminos infinitos en un k- Nodo gráfico completo.

La topología natural en el conjunto de cadenas de longitud fija o cadenas de longitud variable es la topología discreta, pero la topología natural en el conjunto de cadenas infinitas es la topología límite, considerando el conjunto de cadenas infinitas como el límite inverso de los conjuntos de cuerdas finitas. Esta es la construcción utilizada para los números p-ádicos y algunas construcciones del conjunto de Cantor, y produce la misma topología.

Los isomorfismos entre las representaciones de cadenas de topologías se pueden encontrar mediante la normalización de acuerdo con la rotación de cadenas mínima lexicográficamente.