- A preencher
- Lida
- Resposta
Subsequência comum mais longa (LCS)
Que letras têm duas palavras em comum, pela mesma ordem? A subsequência comum mais longa responde a isso, e as ferramentas diff, os corretores ortográficos e as comparações de ADN baseiam-se nela. Escreva duas palavras e veja uma tabela das suas letras a encher-se; depois reconstrua a resposta a partir do canto. Prima Reproduzir para ver a tabela a encher-se, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Escreva duas palavras: a primeira fica ao longo do lado da tabela e a segunda ao longo do topo. Cada célula guarda o comprimento da subsequência comum mais longa das letras até à sua linha e à sua coluna. No fim, as letras são lidas de volta a partir da célula do canto inferior direito. Novo exemplo escolhe outro par de palavras. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.
Como funciona
- Escreva duas palavras: a primeira fica ao longo do lado da tabela e a segunda ao longo do topo.
- Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto.
- Veja cada célula comparar as suas duas letras e depois siga o caminho laranja a partir do canto para ler a resposta.
Como funciona a tabela
Uma célula guarda o comprimento da subsequência comum mais longa entre as letras da primeira palavra até à sua linha e as letras da segunda palavra até à sua coluna. A linha e a coluna marcadas com – representam uma palavra vazia, por isso valem 0. Se as duas letras de uma célula forem iguais, a célula vale mais um do que a célula acima à esquerda. Se forem diferentes, uma das duas letras não faz parte da resposta, por isso a célula fica com o maior valor entre a célula de cima e a da esquerda.
Ler as letras de volta
A célula do canto inferior direito é o comprimento da resposta. Para encontrar as letras, comece aí: onde as duas letras coincidem, essa letra faz parte da subsequência e avança para cima e para a esquerda; caso contrário, vai para a maior entre a célula de cima e a da esquerda. As letras recolhidas pelo caminho, lidas ao contrário, formam uma subsequência comum mais longa. Pode haver outras com o mesmo comprimento; a leitura de volta encontra uma delas.
Perguntas frequentes
Qual é a diferença entre uma subsequência e uma subcadeia?
Uma subcadeia é uma série de letras seguidas, como ACE em RACER. Uma subsequência mantém a ordem mas pode saltar letras, por isso ACE também é uma subsequência de ABCDE. A subcadeia comum mais longa é um problema diferente, com uma tabela semelhante.
Quão rápido é o algoritmo LCS?
Para palavras de comprimentos m e n, a tabela tem m·n células, cada uma preenchida num passo, por isso o trabalho é O(m·n). Para dois textos de 10 000 linhas são 100 milhões de células, e é por isso que as ferramentas diff usam métodos mais engenhosos baseados na mesma ideia.
A subsequência comum mais longa é única?
Não. ABCBDAB e BDCABA têm três subsequências comuns diferentes de comprimento 4: BCBA, BCAB e BDAB. A tabela dá o comprimento; a leitura de volta escolhe uma delas.
A LCS diz quão parecidas são duas palavras?
Em parte. Duas palavras de comprimentos m e n com uma subsequência comum mais longa de comprimento k podem ser transformadas uma na outra apagando m − k letras e inserindo n − k. A distância de edição, que também permite substituir uma letra, é muitas vezes uma medida melhor.
É enviado algum dado para algum lado?
Não. Tudo é calculado no seu navegador, e as suas últimas definições ficam guardadas no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor