|
A necessidade de medir a semelhança/diferença entre duas cadeias de caracteres tanto pode surgir na área da biologia computacional, aquando da comparação de duas sequências biológicas, como na área de processamento de texto, aquando da correcção de erros ortográficos.
Normalmente, a medida desta semelhança/diferença é obtida através da determinação da distância entre as duas cadeias de caracteres. Muitas são as formalizações da noção desta distância. Uma das formas mais comuns, e mais simples, é conhecida por distância de edição e corresponde à transformação/edição da primeira cadeia de caracteres na segunda através de uma série de operações de edição, de forma individual, sobre cada um dos caracteres da cadeia.
Duas das mais típicas distâncias de edição utilizadas são: a distância de edição de Levenshtein e a distância de edição de Damerau. A primeira considera três operações de edição: a inserção, o apagamento e a substituição de um caractere. A segunda considera quatro operações de edição. Às três operações já referidas é adicionada uma operação de transposição entre dois caracteres adjacentes. Ao longo do texto sempre que referirmos a distância de edição, estamos a considerar a distância de Levenshtein.
Definição: A distância de edição entre duas cadeias de caracteres é definida como o número mínimo de operações de edição necessárias para transformar a primeira cadeia de caracteres na segunda. Note-se que o emparelhamento de caracteres iguais não é contabilizado como uma operação de edição.
A definição da distância de edição implica que todas as operações são efectuadas apenas a uma cadeia de caracteres. No entanto a distância de edição é muitas vezes vista como o menor número de operações efectuadas a duas cadeias de caracteres por forma a transformá-las numa terceira cadeia de caracteres comuns. Esta visão em nada altera a definição apresentada anteriormente, uma vez que uma operação de inserção numa cadeia de caracteres pode ser vista como uma operação de apagamento numa outra e vice-versa.
Sub-sequência versus sub-cadeia de caracteres
É relativamente comum na literatura na área da biologia computacional encontrarem-se, erradamente, referências a sub-cadeias de caracteres quando era pretendido referir sub-sequências.
Numa sub-cadeia de caracteres os caracteres têm de ser obrigatoriamente contiguos, enquanto que numa sub-sequência tal facto já não tem de se verificar. Por exemplo, a cadeia de caracteres ACT é uma sub-sequência da cadeia de caracteres ACCGT mas não é uma sub-cadeia de caracteres. A cadeia de caracteres ACC já é uma sub-cadeia de caracteres de ACCGT.
Ao longo do texto as referências a sub-sequências e sub-cadeias de caracteres serão utilizadas nos seus contextos exactos.
|
