Corda (estrutura de dados) - Rope (data structure)

Uma corda simples construída na string de "Hello_my_name_is_Simon".

Na programação de computadores , uma corda , ou cordão , é uma estrutura de dados composta de cordas menores que é usada para armazenar e manipular com eficiência uma corda muito longa. Por exemplo, um programa de edição de texto pode usar uma corda para representar o texto que está sendo editado, de modo que operações como inserção, exclusão e acesso aleatório possam ser feitas com eficiência.

Descrição

Uma corda é uma árvore binária onde cada folha (nó final) contém uma corda e um comprimento (também conhecido como "peso"), e cada nó mais acima na árvore contém a soma dos comprimentos de todas as folhas em sua subárvore esquerda . Um nó com dois filhos, portanto, divide toda a string em duas partes: a subárvore esquerda armazena a primeira parte da string, a subárvore direita armazena a segunda parte da string e o peso de um nó é o comprimento da primeira parte.

Para operações de corda, as strings armazenadas em nós são consideradas objetos imutáveis constantes no caso não destrutivo típico, permitindo algum comportamento de cópia na gravação . Os nós folha são geralmente implementados como strings básicas de comprimento fixo com uma contagem de referência anexada para desalocação quando não são mais necessários, embora outros métodos de coleta de lixo também possam ser usados.

Operações

Nas seguintes definições, N é o comprimento da corda.

Inserir

Definição: Insert(i, S’) inserir a string S ' começando na posição i na string s , para formar uma nova string C ₁ , ..., C _i , S' , C _{i + 1} , ..., C _m .

Complexidade de tempo: . ${\ displaystyle O (\ log N)}$

Esta operação pode ser realizada por uma Split() e duas Concat() operações. O custo é a soma dos três.

Índice

Figura 2.1: Exemplo de pesquisa de índice em uma corda.

Definição:: Index(i) retorna o caractere na posição i

Complexidade de tempo: ${\ displaystyle O (\ log N)}$

Para recuperar o i -ésimo caractere, começamos uma pesquisa recursiva no nó raiz:

function index(RopeNode node, integer i)
  if node.weight <= i and exists(node.right) then
    return index(node.right, i - node.weight)
  end
  
  if exists(node.left) then
    return index(node.left, i)
  end
  
  return node.string[i]
end

Por exemplo, para encontrar o caractere i=10 na Figura 2.1 mostrada à direita, comece no nó raiz (A), descubra que 22 é maior que 10 e há um filho à esquerda, então vá para o filho à esquerda (B). 9 é menos que 10, então subtraia 9 de 10 (saindo i=1 ) e vá para a criança certa (D). Aí porque 6 é maior que 1 e tem filho da esquerda, vai para a criança da esquerda (G). 2 é maior que 1 e tem filho da esquerda, então vá para a criança da esquerda novamente (J). Finalmente, 2 é maior que 1, mas não há filho à esquerda, então o caractere no índice 1 da string curta "na" (ou seja, "a") é a resposta.

Concat

Figura 2.2: Concatenando duas cordas infantis em uma única corda.

Definição: Concat(S1, S2) concatene duas cordas, S ₁ e S ₂ , em uma única corda.

Complexidade de tempo: (ou tempo para calcular o peso da raiz) ${\ displaystyle O (1)}$${\ displaystyle O (\ log N)}$

Uma concatenação pode ser realizada simplesmente criando um novo nó raiz com left = S1 e right = S2 , que é tempo constante. O peso do nó pai é definido como o comprimento do filho esquerdo S ₁ , o que levaria tempo, se a árvore fosse equilibrada. ${\ displaystyle O (\ log N)}$

Como a maioria das operações de corda requer árvores balanceadas, a árvore pode precisar ser reequilibrada após a concatenação.

Dividir

Figura 2.3: Dividindo uma corda ao meio.

Definição: Split (i, S) dividir a string S em duas novas strings S ₁ e S ₂ , S ₁ = C ₁ ,…, C _i e S ₂ = C _{i + 1} ,…, C _m .

Complexidade de tempo: ${\ displaystyle O (\ log N)}$

Existem dois casos que devem ser tratados:

1. O ponto de divisão está no final de uma string (ou seja, após o último caractere de um nó folha)
2. O ponto de divisão está no meio de uma corda.

O segundo caso se reduz ao primeiro dividindo a string no ponto de divisão para criar dois novos nós folha e, em seguida, criando um novo nó que é o pai das duas strings componentes.

Por exemplo, para dividir a corda de 22 caracteres ilustrada na Figura 2.3 em duas cordas de componentes iguais de comprimento 11, consulte o 12º caractere para localizar o nó K no nível inferior. Remover a ligação entre K e G . Ir para o pai de L e subtrair o peso de K a partir do peso de D . Suba na árvore e remova todos os links corretos para as subárvores que cobrem os personagens após a posição 11, subtraindo o peso de K de seus nós pais (apenas os nós D e A , neste caso). Finalmente, constrói-se os nodos recém órfãs K e H , concatenando-los em conjunto e criar uma nova matriz P com peso igual ao comprimento do nó esquerda K .

Como a maioria das operações de corda requer árvores equilibradas, a árvore pode precisar ser reequilibrada após a divisão.

Excluir

Definição: Delete(i, j) elimine a substring C _i ,…, C _{i + j - 1} , de s para formar uma nova string C ₁ ,…, C _{i - 1} , C _{i + j} ,…, C _m .

Complexidade de tempo: . ${\ displaystyle O (\ log N)}$

Esta operação pode ser feita por duas Split() e uma Concat() operação. Primeiro, divida a corda em três, dividida por i -ésimo e i + j -ésimo caractere respectivamente, que extrai a string para excluir em um nó separado. Em seguida, concatene os outros dois nós.

Relatório

Definição:: Report(i, j) produza a string C _i ,…, C _{i + j - 1} .

Complexidade de tempo: ${\ displaystyle O (j + \ log N)}$

Para relatar a string C _i ,…, C _{i + j - 1} , encontre o nó u que contém C _i e weight(u) >= j , e então atravesse T começando no nó u . Saída C _i ,…, C _{i + j - 1} fazendo um percurso em ordem de T começando no nó u .

Comparação com matrizes monolíticas

Vantagens:

• As cordas permitem a inserção e exclusão de texto muito mais rápidas do que as matrizes de string monolíticas, nas quais as operações têm complexidade de tempo O (n).
• Os cabos não requerem memória extra O (n) quando operados (os arrays precisam disso para operações de cópia).
• As cordas não requerem grandes espaços de memória contíguos.
• Se apenas versões não destrutivas de operações forem usadas, a corda é uma estrutura de dados persistente . Para o exemplo do programa de edição de texto, isso leva a um suporte fácil para vários níveis de desfazer .

Desvantagens:

• Maior uso geral do espaço quando não está sendo operado, principalmente para armazenar nós pais. Há uma compensação entre quanto da memória total é tal sobrecarga e por quanto tempo as partes dos dados estão sendo processadas como strings. As strings nas figuras de exemplo acima são irrealisticamente curtas para arquiteturas modernas. O overhead é sempre O (n), mas a constante pode ser arbitrariamente pequena.
• Aumento do tempo para gerenciar o armazenamento extra
• Maior complexidade do código-fonte; maior risco de bugs

Esta tabela compara as características algorítmicas de implementações de cordas e cordas, não sua velocidade bruta . Strings baseadas em array têm menor sobrecarga, então (por exemplo) as operações de concatenação e divisão são mais rápidas em pequenos conjuntos de dados. No entanto, quando strings baseadas em array são usadas para strings mais longas, a complexidade do tempo e o uso de memória para inserir e excluir caracteres tornam-se inaceitavelmente grandes. Em contraste, uma estrutura de dados de corda tem desempenho estável, independentemente do tamanho dos dados. Além disso, a complexidade do espaço para cordas e matrizes é O (n). Em resumo, cordas são preferíveis quando os dados são grandes e modificados com frequência.

Veja também

• O ambiente de programação Cedar , que usava cordas "quase desde seu início"
• O modelo T enfilade , uma estrutura de dados semelhante do início dos anos 1970.
• Buffer de lacuna , uma estrutura de dados comumente usada em editores de texto que permite operações eficientes de inserção e exclusão agrupadas perto do mesmo local
• Tabela de peças , outra estrutura de dados comumente usada em editores de texto

Referências

links externos

• Implementação "C cords" de cordas na biblioteca Boehm Garbage Collector
• Especificação SGI C ++ para cabos (compatível com STLPort e libstdc ++ )
• Cordas para C #
• cordas para Common Lisp
• Cordas para Java
• Cordas para JavaScript
• Cordas para Limbo
• cordas para Nim
• Cordas para OCaml
• piropos para Python
• Cordas para Smalltalk
• SwiftRope para Swift
• "Ropey" para Rust