Editar distância com operações de movimentação

13

Motivação: Um co-autor edita um manuscrito e eu gostaria de ver um resumo claro das edições. All "diff" -como ferramentas tendem a ser inútil se você está tanto em movimento texto ao redor (por exemplo, re-organização da estrutura) e fazer edições locais. É realmente tão difícil acertar?


Definições: eu gostaria de encontrar a distância mínima de edição, onde as operações permitidas são:

  • operações "baratas": adicione / altere / exclua um único caractere (as operações usuais de Levenshtein),

  • "caras": operações: mova uma substring para um novo local ( para qualquer sequência de caracteres a , b , c , d ).abcdacbdabcd

Dadas duas cordas e y e inteiros k e K , eu gostaria de resolver o seguinte problema:xykK

  • você pode transformar em y usando no máximo k operações baratas e no máximo K operações caras?xykK

Questões:

  1. Esse problema tem um nome? (Parece uma pergunta muito padrão no contexto do alinhamento de sequência.)

  2. É difícil?

  3. Se for difícil, é um parâmetro fixo tratável com como parâmetro?K

  4. Existem algoritmos de aproximação eficientes? (Por exemplo, encontre uma solução com no máximo operações baratas e 2 K caras se existir uma solução com k operações baratas e K caras.)2k2KkK

Tentei dar uma olhada nas métricas de string listadas na Wikipedia , mas nenhuma delas parecia correta.

Jukka Suomela
fonte
3
Para , o problema é Classificar por Transposições. Veja, por exemplo, web.cs.dal.ca/~whidden/HThesis07.pdf Não encontrei seu problema, mas ele parece muito bem motivado. k=0
Serge Gaspers
4
A dureza NP do problema Classificação por transposições foi comprovada em 2010, consulte A classificação por transposições é difícil .
Marzio De Biasi
3
As transposições são difíceis, mas inserções e exclusões não. Se você permitir que uma operação cara seja a exclusão de uma substring arbitrária ou a inserção de qualquer substring da outra string, o problema deve se tornar bastante fácil. A distância resultante não seria simétrica.
Jouni Sirén
Estou mais curioso sobre a rastreabilidade de parâmetros fixos. Existe alguma nova descoberta?
Yixin Cao

Respostas:

4

O problema se torna mais fácil se considerarmos exclusões longas e cópias de substring em vez de transposições. Suponha que estamos usando o algoritmo de programação dinâmica padrão para a computação editar distância, e que uma operação cara de comprimento aumenta a distância por um k + b , para algumas constantes a , b 0 . Essas constantes podem ser diferentes para exclusões longas e cópias de substring.kak+ba,b0

Uma exclusão longa é a exclusão de uma substring arbitrária de . É fácil apoiá-los, se os dividirmos em dois tipos de operações simples: excluir o primeiro caractere (custo a + b ) e estender a exclusão em um caractere (custo a ). Além da matriz padrão A , onde A [ i , j ] é a distância de edição entre os prefixos x [ 1 i ] e y [ 1 j ] , usamos outra matriz A dxa+baAA[i,j]x[1i]y[1j]Adpara armazenar a distância de edição, quando a última operação usada foi uma exclusão longa. Com essa matriz, só temos de olhar para , A [ i - 1 , j - 1 ] , A [ i , j - 1 ] e A d [ i - 1 , j ] ao calcular A [ i , j ] e A d [ iA[i1,j]A[i1,j1]A[i,j1]Ad[i1,j]A[i,j] , nos permitindo fazê-lo em O ( 1 ) tempo.Ad[i,j]O(1)

Cópia de subcadeia significa a inserção de uma subcadeia arbitrária de na cadeia editada. Assim como nas exclusões longas, dividimos a operação em duas operações simples: inserir o primeiro caractere e estender a inserção por um caractere. Também usamos a matriz A s para armazenar a distância de edição entre os prefixos, desde que a última operação usada seja a cópia de substring.xAs

Fazer isso de forma eficiente é mais complicado do que com exclusões longas, e não tenho certeza se podemos chegar ao tempo amortizado por célula. Construímos uma árvore de sufixos para x , que leva tempo O ( | x | ) , assumindo um alfabeto de tamanho constante. Armazenamos um ponteiro para o nó da árvore do sufixo atual em A s [ i , j - 1 ] , permitindo verificar em tempo constante, se podemos estender a inserção pelo caractere y [ j ] . Se isso for verdade, podemos calcular A [ iO(1)xO(|x|)As[i,j1]y[j] e A s [ i , j ] em tempo constante.A[i,j]As[i,j]

Caso contrário, , em que z é a subcadeia inserida usada para calcular A s [ i , j - 1 ] , não é uma subcadeia de x . Usamos a árvore de sufixos para encontrar o sufixo mais longo z de z , para o qual z y [ j ] é uma subcadeia de x , em O ( | z | - | z | ) . Para calcularzy[j]zAs[i,j1]xzzzy[j]xO(|z||z|) , agora precisamos observar as células A [ i , j - | z | - 1 ] a A [ i , j - 1 ] . Encontrar o sufixo z ' requer apenas O ( 1 ) tempoamortizadopor célula, mas calcular A s [ i , j ] com uma abordagem de força bruta leva O ( | zAs[i,j]A[i,j|z|1]A[i,j1]zO(1)As[i,j] hora. Provavelmente existe uma maneira de fazer isso de forma mais eficiente, mas não consigo encontrá-lo agora.O(|z|)

Na pior das hipóteses, o algoritmo leva , mas uma análise melhor deve ser possível. A distância de edição resultante com exclusões longas e cópia de substring não é simétrica, mas isso não deve ser um problema. Afinal, geralmente é mais fácil alcançar a string vazia de uma não vazia do que o contrário.O(min(|x||y|2,|x|2|y|))

Jouni Sirén
fonte