Editar distância da lista com elementos exclusivos

12

A distância de edição Levenshtein-Distance entre listas é um problema bem estudado. Mas não consigo encontrar muitas melhorias possíveis, se soubermos que nenhum elemento ocorre mais de uma vez em cada lista .

Vamos supor também que os elementos são comparáveis ​​/ classificáveis ​​(mas as listas a serem comparadas não são classificadas para começar).

Em particular, estou interessado em saber se a singularidade dos elementos permite melhorar o algoritmo de Ukkonen para a distância de edição, que possui complexidade de tempo e complexidade de espaço O ( min ( s , m , n ) s ) , onde s é o custo mínimo das etapas de edição .O(min(m,n)s)O(min(s,m,n)s)s

Mais formalmente,

com que eficiência podemos calcular a distância de edição entre duas seqüências de caracteres com a promessa de que elas não têm letras repetidas?s,tΣ

é um alfabeto muito grande.Σ

user362178
fonte
Qual é a sua pergunta agora; como acelerar a distância de edição aos pares ou como calcular todas as distâncias aos pares de uma lista de cadeias?
Raphael
2
Eu suspeito que a pergunta é: como calcular a distância de edição entre , onde s , t Σ são strings sobre um alfabeto muito grande Σ , e garantimos que nenhuma letra apareça duas vezes em s ou em t (o OP representa cada string como uma lista de letras, ou seja, uma lista de elementos). Mas isso precisa de confirmação. s,ts,tΣΣst
DW
Sim, nesse caso, o alfabeto grande é composto de índices de banco de dados e as "strings", s e t, são listas que contêm esses índices.
user362178
Para aqueles que se perguntam sobre as complexidades: e n são os comprimentos das cadeias de entrada es é a distância real de edição, portanto ela é incluída na complexidade. O custo de cada edição é considerado 1, mas provavelmente é irrelevante para calcular esta distância (o número de edições s ). mnss
Albert Hendriks

Respostas:

3

TL; DR: Um tipo um pouco mais restritivo de distância de edição, no qual só podemos inserir e excluir caracteres individuais, pode ser calculado em tempo linearitmico, quando ambas (ou apenas uma) das seqüências possuem caracteres únicos. Isso fornece limites superiores e inferiores úteis na distância de edição de Levenshtein.

Inserir / excluir distância de edição e subsequências comuns mais longas

A distância de edição de Levenshtein permite inserções, exclusões e substituições de um caractere, atribuindo a cada um custo de 1. Se restringirmos apenas inserções e exclusões, obteremos uma medida de distância semelhante que agora faz com que as substituições tenham um custo de 2 (uma vez que qualquer substituição pode ser imitado usando uma inserção e uma exclusão). Como não conheço um nome padrão para esse tipo mais restritivo de distância de edição, chamo-o de "inserir / excluir distância de edição". Corresponde intimamente ao maior problema de subsequência comum (LCS) , no qual recebemos duas cadeias de comprimento e n , respectivamente, e queremos saber o comprimento da subsequência mais longa que aparece em ambas. Se duas cordas tiverem LCS Lmneu, eles têm a inserção / exclusão da distância de edição n+m-2eu : a maneira mais fácil de ver isso é alinhar as strings para que os caracteres no LCS apareçam empilhados um sobre o outro, enquanto os caracteres que não estão no LCS aparecem em frente a -caractere de lacuna. Ficará claro que podemos editar a primeira string na segunda, fazendo uma inserção sempre que houver uma -na linha superior e uma exclusão sempre que houver uma -na linha inferior. Por exemplo:

-C-IRC-LE
T-RI-CKLE

Aqui, o LCS de CIRCLEe TRICKLE, ICLEtem comprimento 4 e a distância de edição é de fato .6+7-24=5

Maiores subsequências crescentes

O motivo desse desvio é que existe uma maneira muito eficiente de calcular o LCS (e, portanto, a distância de edição de inserção / exclusão) quando pelo menos uma das seqüências contém apenas caracteres distintos: Nesse caso, o problema do LCS pode ser transformado em o problema de encontrar uma subsequência crescente mais longa , que pode ser resolvida no tempo . Suponha que recebamos duas cadeias A e B , e a cadeia A tenha caracteres distintos. Podemos renomear o primeiro caractere de A para 1, o segundo para 2 e assim por diante, acompanhando o número que atribuímos a cada caractere em uma tabela. Então em BO(nregistron)UMABUMAUMAB, renomeamos seus caracteres usando essa tabela (ou seja, todas as ocorrências do primeiro caractere foram Aalteradas para 1 etc.). Finalmente, procuramos uma subsequência crescente mais longa em B. Isso corresponde a um LCS entre Ae B, e a partir daí podemos calcular imediatamente a distância de edição de inserção / exclusão. O tempo total necessário é apenas se A e B tiverem comprimentos n e m , respectivamente.O(n+mregistrom)UMABnm

Limites em Levenshtein editar distância

A distância de inserção / exclusão fornece claramente um limite superior à distância de Levenshtein (já que qualquer sequência válida de operações de edição sob a distância de inserção / exclusão também é uma sequência válida de operações de edição de Levenshtein). Dividir a distância de edição de inserção / exclusão por 2 também gera um limite inferior, pois, na pior das hipóteses, qualquer operação de edição da Levenshtein pode ser alterada em 2 operações de edição de inserção / exclusão.

Generalizações

rO((r+n)registron)rndiffdiffO(nd)d

Hunt, J .; Szymanski, T. (1977), "Um algoritmo rápido para computar as subsequências comuns mais longas", Communications of the ACM, 20 (5): 350–353, doi: 10.1145 / 359581.359603

j_random_hacker
fonte