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

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 ).$abcd \mapsto acbd$$a$$b$$c$$d$

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

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

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.)$2k$$2K$$k$$K$

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

Como comentado por Serge Gaspers, para o problema é Classificação por transposições e foi introduzido por Bafna e Pevzner em 1995. Sua dureza NP foi comprovada apenas em 2010; veja Laurent Bulteau, Guillaume Fertin e Irena Rusu, "Classificar por transposições é difícil" .$k=0$

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.$k$$ak+b$$a,b \ge 0$

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 $x$$a+b$$a$$A$$A[i,j]$$x[1 \dots i]$$y[1 \dots j]$$A_{d}$para 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 [ $A[i-1,j]$$A[i-1,j-1]$$A[i,j-1]$$A_{d}[i-1,j]$$A[i,j]$ , nos permitindo fazê-lo em O ( 1 ) tempo.$A_{d}[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.$x$$A_{s}$

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 [ $O(1)$$x$$O(|x|)$$A_{s}[i,j-1]$$y[j]$ e A s [ i , j ] em tempo constante.$A[i,j]$$A_{s}[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 calcular$zy[j]$$z$$A_{s}[i,j-1]$$x$$z'$$z$$z'y[j]$$x$$O(|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 ( | $A_{s}[i,j]$$A[i, j-|z'|-1]$$A[i,j-1]$$z'$$O(1)$$A_{s}[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| \cdot |y|^{2}, |x|^{2} \cdot |y|))$