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.

Nas maioria das linguagens de programação, as cadeias de caracteres podem ser expressas tanto na forma literal, como através de algum tipo de variável. Quando expressos através de variáveis, o conteúdo da cadeia geralmente pode ser alterado pela inclusão/exclusão de elementos ou pela substituição de seus elementos por outros elementos, formando uma nova cadeia. Assim, uma cadeia de caracteres é vista como sendo um tipo de dado e normalmente é implementada através de um arranjo de bytes que armazena os elementos da cadeia em sequência, utilizando alguma codificação preestabelecida.

Nas linguagens formais, uma cadeia de caracteres é uma sequência finita de símbolos escolhidos a partir de conjunto denominado alfabeto.

Propósito 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.

Exemplos de strings e seus propósitos:

Uma mensagem como "" é uma string que o software exibe aos usuários finais. No código-fonte do programa, esta mensagem provavelmente apareceria como uma string literal. Texto inserido pelo usuário, como "" como uma atualização de status em uma rede social. Em vez de uma literal, o software provavelmente armazenaria essa string em um banco de dados. Dados alfabéticos, como "", representando sequências de ácidos nucleicos de ADN. Configurações ou parâmetros de computador, como "" como uma string de consulta (query string) de URL. Frequentemente, estas são destinadas a serem um pouco legíveis por humanos, embora seu propósito principal seja a comunicação entre computadores.

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.

História

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.

De acordo com Jean E. Sammet, "a primeira linguagem realista de manipulação de strings e correspondência de padrões" para computadores foi a COMIT na década de 1950, seguida pela linguagem SNOBOL no início da década de 1960.

Tipos de dados de string

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

Dope vectors 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.

Terminação em nulo (Null-terminated) 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:

F R A N K NUL k e f w 4616 5216 4116 4E16 4B16 0016 6B16 6516 6616 7716

Prefixo de comprimento O comprimento também pode ser armazenado explicitamente como um prefixo (comum em dialetos Pascal, daí o nome Pascal string ou P-string). Se o prefixo for de 1 byte, a string é limitada a 255 caracteres. Implementações modernas usam palavras de 32 ou 64 bits para o prefixo, permitindo que as strings sejam limitadas apenas pela memória disponível.

Strings como registros Muitas linguagens orientadas a objetos implementam strings como registros com uma estrutura interna:

public final class String { private unsigned long length; // comprimento da string private UniquePointer<char[]> text; // ponteiro para os caracteres

// métodos públicos... }

Outras representações Para maior eficiência em editores de texto, podem ser usadas estruturas como ropes ou gap buffers, que facilitam inserções e deleções em grandes volumes de texto.

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.

Teoria formal 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 Σ.

Se o alfabeto Σ = {0, 1}, então 0, 1, 01, 000001 e 101 são cadeias sobre o alfabeto Σ. 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 λ. Se o alfabeto Σ = {0, 1}, então |00| = 2, |0101| = 4 e |ε| = 0.''O conjunto de todas as possíveis cadeias de tamanho n sobre um alfabeto Σ qualquer de tamanho é denotado por Σn. Se o alfabeto Σ = {0, 1}, então Σ² = {00, 01, 10, 11}. Notar que Σ0 = {ε} para qualquer alfabeto Σ. O conjunto de todas as possíveis cadeias sobre Σ de qualquer tamanho é denotado por Σ*. Em termos de Σn, Σ* = Σ0 ∪ Σ1 ∪ Σ2…. Se o alfabeto Σ = {0, 1} então Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}. 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 …

Strings literais À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.

Duas representações comuns são: