Cadeia de caracteres
Na programação de computadores, uma cadeia de caracteres ou string é uma sequência de caracteres, geralmente utilizada para representar palavras, frases ou textos de um programa.
Imagem: Vitor Oliveira from Torres Vedras, PORTUGAL · BY-SA · Openverse
O propósito principal das cadeias de caracteres (strings) é armazenar texto legível por humanos, como palavras e frases. As strings são usadas para comunicar informações de um programa de computador para o usuário do programa. Um programa também pode aceitar a entrada de strings de seu usuário. Além disso, as strings podem armazenar dados expressos como caracteres, mas que não se destinam à leitura humana. O termo "string" também pode designar uma sequência de dados ou registros de computador que não sejam caracteres — como uma "cadeia de bits" — mas, quando usado sem qualificação, refere-se a cadeias de caracteres.
Imagem: Jefferson Carlos De Bragança · BY-SA · Openverse
O uso da palavra "string" (em português, corda, sequência ou cadeia) para significar quaisquer itens organizados em linha, série ou sucessão remonta a séculos. Na tipografia do século XIX, os compositores utilizavam o termo para designar um comprimento de tipos impressos em papel; a "string" era medida para determinar o pagamento do compositor. O uso da palavra "string" para significar "uma sequência de símbolos ou elementos linguísticos em uma ordem definida" surgiu da matemática, da lógica simbólica e da teoria linguística para descrever o comportamento formal de sistemas simbólicos, abstraindo o significado dos símbolos. Por exemplo, o lógico C. I. Lewis escreveu em 1918: Um sistema matemático é qualquer conjunto de sequências (strings) de marcas reconhecíveis nas quais algumas das sequências são tomadas inicialmente e as demais derivadas destas por operações realizadas de acordo com regras que são independentes de qualquer significado atribuído às marcas. Que um sistema consista de 'marcas' em vez de sons ou odores é imaterial.
Imagem: Portuguese_eyes · BY-SA · Openverse
Um tipo de dado de string é um tipo de dado modelado na ideia de uma string formal. Strings são tipos de dados tão importantes e úteis que são implementados em quase todas as linguagens de programação. Em algumas linguagens, estão disponíveis como tipos primitivos e, em outras, como tipos compostos. A sintaxe da maioria das linguagens de alto nível permite que uma string, geralmente entre aspas, represente uma instância desse tipo; tal meta-string é chamada de literal ou string literal.
Comprimento da string
Embora as strings formais possam ter um comprimento finito arbitrário, o comprimento em linguagens reais é frequentemente restringido a um máximo artificial. Em geral, existem dois tipos: **strings de comprimento fixo**, que possuem um tamanho máximo determinado em tempo de compilação e usam a mesma quantidade de memória independentemente da necessidade; e **strings de comprimento variável**, cujo tamanho não é fixo e podem usar quantidades variadas de memória dependendo dos requisitos em tempo de execução (veja Gerenciamento de memória). A maioria das linguagens modernas utiliza strings de comprimento variável. O comprimento pode ser armazenado como um inteiro separado ou implicitamente através de um caractere de terminação (geralmente um caractere nulo, como em C).
Codificação de caracteres
Historicamente, os tipos de string alocavam um byte por caractere (baseados em ASCII ou EBCDIC). Idiomas logográficos como o chinês, japonês e coreano (CJK) exigem muito mais do que os 256 caracteres permitidos por um byte de 8 bits. As soluções iniciais envolviam representações de dois bytes, mas isso gerava problemas de compatibilidade e corrupção de dados em sistemas que não foram projetados para tal (como o ISO-2022 e Shift-JIS). O Unicode simplificou esse cenário. A maioria das linguagens agora possui suporte nativo para strings Unicode. O formato de fluxo de bytes preferencial do Unicode, o UTF-8, foi projetado para evitar problemas de sincronização das codificações multibyte antigas. UTF-8, UTF-16 e UTF-32 exigem que o programador saiba que as unidades de código de tamanho fixo são diferentes dos "caracteres" visíveis.
Implementações
Algumas linguagens, como C++, Perl e Ruby, permitem que o conteúdo de uma string seja alterado após a criação; estas são chamadas de strings mutáveis. Em outras, como Java, JavaScript, Python e Go, o valor é fixo e uma nova string deve ser criada para qualquer alteração; estas são chamadas de strings imutáveis. A imutabilidade simplifica a segurança entre threads (thread safety). As strings são tipicamente implementadas como arrays de bytes ou caracteres. Algumas linguagens de alto nível as tratam como tipos primitivos (JavaScript, PHP), enquanto outras as tratam como tipos compostos com suporte especial para literais (Java, C#). Linguagens como C e Erlang evitam um tipo de dado dedicado, representando strings como listas de códigos de caracteres.
Representações
O comprimento de uma string pode ser armazenado em um vetor de controle (dope vector), separado do local onde estão os caracteres. O compilador PL/I (F) da IBM utilizava um string dope vector (SDV) que continha o comprimento atual, o comprimento máximo e um ponteiro para o início da string. O comprimento pode ser armazenado implicitamente usando um caractere terminador especial, geralmente o caractere nulo (NUL), convenção perpetuada pela linguagem C. Por isso, essa representação é comumente chamada de C string. Uma string de n caracteres ocupa n + 1 espaços de memória. Exemplo de uma string terminada em nulo "FRANK" em um buffer de 10 bytes:
Problemas de segurança
Diferentes layouts de memória afetam a segurança. Strings terminadas em nulo são suscetíveis a problemas de estouro de buffer (buffer overflow) se o caractere terminador estiver ausente ou for manipulado por um invasor. Representações com campo de comprimento também são vulneráveis se o valor do comprimento puder ser manipulado. É responsabilidade do programa realizar a validação dos dados para evitar ataques de injeção de código.
Seja Σ um conjunto finito e não vazio de símbolos (ou caracteres) chamado de o alfabeto. Uma cadeia sobre Σ é qualquer sequência finita de caracteres contidos em Σ. O comprimento ou cardinalidade da cadeia é a quantidade de caracteres utilizados para sua composição. À cadeia de comprimento zero dá-se o nome de cadeia vazia e é usualmente denotada na literatura pelos símbolos ε ou λ. O conjunto de todas as possíveis cadeias de tamanho n sobre um alfabeto Σ qualquer de tamanho é denotado por Σn. O conjunto de todas as possíveis cadeias sobre Σ de qualquer tamanho é denotado por Σ*. Em termos de Σn, Σ* = Σ0 ∪ Σ1 ∪ Σ2…. Apesar do conjunto Σ* possuir infinitos elementos, todos os elementos de Σ* possuem comprimento finito. Um conjunto de cadeias sobre um alfabeto Σ (isto é, qualquer subconjunto de Σ*) é chamado de linguagem formal sobre Σ.
Concatenação e sub-cadeias
Concatenação é uma importante operação binária em Σ*. Para qualquer duas cadeias s e t em Σ*, sua concatenação é definida pela sequência de caracteres de s seguida pela sequência de caracteres em t, denotada por st. Por exemplo se Σ = {a, b, …, z}, s = bear e t = hug, então st = bearhug e ts = hugbear. A concatenação de cadeias é uma operação associativa, mas não comutativa. A cadeia vazia serve como um elemento identidade: para qualquer cadeia s, εs = sε = s. Portanto, o conjunto Σ* e a operação de concatenação formam um monóide. A cadeia s é dita uma subcadeia (ou fator) de t se existem cadeias (possivelmente vazias) u e v de forma que t = usv.
Ordenação lexicográfica
Geralmente é necessário definir uma ordenação em um conjunto de cadeias. Se um alfabeto Σ possui uma relação de ordem (como a ordem alfabética) pode-se definir uma relação de ordem em Σ* chamada ordem lexicográfica. Note que como Σ é finito, é sempre possível definir uma ordenação em Σ e portanto em Σ*. Por exemplo, se Σ = {0, 1} e 0 < 1, então a ordenação lexicográfica em Σ* é ε < 0 < 00 < 000 < … < 011 < 0110 < … < 01111 < … < 1 < 10 < 100 < … < 101 < … < 111 …
Às vezes, as cadeias de caracteres precisam ser incorporadas em um arquivo de texto que seja legível por humanos e destinado ao processamento por uma máquina. Isso é necessário, por exemplo, no código-fonte de linguagens de programação ou em arquivos de configuração. Nesse caso, o caractere NUL não funciona bem como terminador, pois normalmente é invisível (não imprimível) e difícil de inserir via teclado. Armazenar o comprimento da string também seria inconveniente, pois o cálculo manual e o rastreamento do comprimento são tarefas tediosas e propensas a erros.
Embora as cadeias de caracteres sejam usos muito comuns de strings, em ciência da computação, uma "string" pode se referir genericamente a qualquer sequência de dados de tipos homogêneos. Uma cadeia de bits (bit string) ou cadeia de bytes (byte string), por exemplo, pode ser usada para representar dados binários não textuais recuperados de um meio de comunicação. Esses dados podem ou não ser representados por um tipo de dado específico para strings, dependendo das necessidades da aplicação, da vontade do programador e das capacidades da linguagem de programação utilizada. Se a implementação de string da linguagem não for 8-bit clean, pode ocorrer corrupção de dados. Programadores C fazem uma distinção nítida entre uma "string" (também chamada de "cadeia de caracteres"), que por definição é sempre terminada em nulo, e um "array de caracteres", que pode estar armazenado no mesmo array, mas que frequentemente não possui o terminador nulo. O uso de funções de manipulação de strings em C em tais arrays de caracteres costuma parecer funcionar inicialmente, mas acaba levando a problemas de segurança.
As funções de string são utilizadas para criar cadeias de caracteres ou alterar o conteúdo de uma string mutável. Elas também são usadas para consultar informações sobre uma determinada string. O conjunto de funções e seus nomes variam dependendo da linguagem de programação de computadores. O exemplo mais básico de uma função de string é a função de comprimento de string – a função que retorna o comprimento de uma cadeia (sem contar quaisquer caracteres terminadores ou informações estruturais internas da string) e não modifica a string original. Esta função é frequentemente nomeada como length, len ou size. Por exemplo, length("hello world") retornaria 11. Outra função comum é a concatenação, onde uma nova string é criada ao anexar duas cadeias, sendo frequentemente representada pelo operador de adição +. A arquitetura do conjunto de instruções de alguns microprocessadores contém suporte direto para operações de string, como cópia de bloco (ex: no Intel x86, o comando REPNZ MOVSB).
Um tipo de dado cadeia de caracteres (referido em programação geralmente como string) é uma modelagem de uma cadeia formal de caracteres. São bastante usados em programação, sendo implementados em quase todas as linguagens de programação. Em algumas linguagens esse tipo é definido nativamente, em outras é um tipo composto, derivado.
