Número mais curto de edição movido entre duas palavras

11

Estou procurando uma estrutura de dados e um algoritmo para calcular o número mínimo de alterações necessárias para transformar uma palavra em outra, considerando as duas palavras como entradas, onde as únicas alterações permitidas são

  • adicione uma letra em uma das extremidades (por exemplo, AB -> ABC),
  • duplicar e concatenar a palavra inteira (por exemplo, ABC -> ABCABC),
  • corte uma palavra em duas (a dupla do movimento de duplicação, ABCABC -> ABC + ABC),
  • exclua uma das letras (por exemplo, ABC -> AC) e
  • repita uma das letras (por exemplo, ABC -> ABBC).

Por exemplo, uma sequência mínima de movimentos de ABC para BCBC é ABC -> BC (excluir A) -> BCBC (duplicação).

Eu não tenho formação em ciência da computação. Talvez esse seja um problema conhecido, mas minha pesquisa no Google não me deu nada.

Você conhece algum problema relacionado e bem definido?

Edit : Como sugerido na resposta de Anthony Labarre, li alguns artigos sobre o problema de permutação / arranjo de poset que é semelhante ao problema descrito acima. Alguém sabe mais sobre esse problema? Isso é relevante?

cz3rk
fonte
1
Presumivelmente, nenhum da lista em en.wikipedia.org/wiki/String_metric se aplica, nem está em sourceforge.net/projects/simmetrics ?
András Salamon
Eu não conheço todos eles, mas a maior parte do objetivo desses métodos é alinhar strings com apenas uma alteração de letra permitida e não permitir movimentos mais complexos.
Cz3rk
1
Uma duplicação se aplica a toda a cadeia ABC -> ABCABC, para que a direção não importe. Mas a direção da repetição só pode estar na ordem da esquerda para a direita, como um gaguejador.
Cz3rk
2
Por que importa se as palavras digitadas não compartilham letras? (Deve haver uma cadeia vazia entre Ae Bna @ sequência de reinerpost.)
Jeffε
2
Você adicionou a operação "recorte uma palavra em duas"; você quer dizer a operação que mapeia para ? wwww
Argentpepper # 28/13

Respostas:

3

Não sei se esse problema exato foi estudado, mas Chaudhuri et al. estudou o problema de duplicação tandem-perda aleatória relacionada: você recebe uma permutação e deseja transformá-la na permutação de identidade (1) duplicando um segmento de qualquer comprimento e anexando a cópia logo após o original e (2) excluindo elementos para que você obtenha uma nova permutação em vez de uma sequência. Observe que a aplicação (1) e (2) representa uma operação.

Diferentes variantes podem ser definidas de acordo com o peso atribuído a cada operação, o que em seu papel depende da largura dos segmentos duplicados. Eles também estudam um problema semelhante com toda a duplicação do genoma , que é exatamente o tipo de duplicação que você permite. Não me lembro de ler sobre o trabalho sobre esse problema no contexto de strings, mas espero que isso possa ao menos dar um ponto de partida para suas pesquisas.

Anthony Labarre
fonte
Obrigado, vou dar uma olhada no trabalho deles. Eu posso ver a relação entre os dois problemas.
Cz3rk
2

Como foi apontado, esse problema é semelhante ao problema de distância de edição mais conhecido (subjacente à distância de Levenshtein ). Ele também possui pontos em comum com, por exemplo, a distância dinâmica de distorção do tempo (a duplicação ou "gagueira") em seu último requisito.

Passos para a programação dinâmica

Minha primeira tentativa de decomposição recursiva ao longo das linhas de distância de Levenshtein e distância dinâmica de distorção do tempo foi algo como o seguinte (para e ), com sendo definido como x=x1xny=y1ymd(x,y)

min{d(x,y1ym1)+1▻ Add letter at endd(x,y2ym)+1▻ Add letter at beginningd(x,y1ym/2)+1if y=y1ym/2y1ym/2▻ Doublingd(x1xn/2,y)+1if x=x1xn/2x1xn/2▻ Halvingd(x1xn,y)+1▻ Deletiond(x1xn1,y1ym1)if yn=ym▻ Ignoring last elt.

Aqui, a última opção basicamente diz que converter FOOX em BARX é equivalente a converter FOOX em BAR. Isso significa que você pode usar a opção "adicionar letra no final" para obter o efeito de gagueira (duplicação) e a exclusão em algum momento. O problema é que ele automaticamente permite que você adicione uma arbitrária personagem no meio da corda bem , algo que você provavelmente não quer. (Esse "ignorar os últimos elementos idênticos" é a maneira padrão de obter exclusão e gagueira em posições arbitrárias. Torna proibir inserções arbitrárias e, ao mesmo tempo, permitir adições em ambas as extremidades, um pouco complicado ...)

Eu incluí esse detalhamento, mesmo que ele não funcione completamente, caso alguém possa "resgatá-lo" de alguma forma - e porque eu o uso na minha solução heurística abaixo.

(Obviamente, se você pudesse obter uma análise como essa que realmente definisse sua distância, seria necessário apenas adicionar memorização e ter uma solução. No entanto, como você não está apenas trabalhando com prefixos, eu não acho que você poderia usar apenas índices para sua memorização; talvez seja necessário armazenar as strings modificadas reais para cada chamada, o que seria enorme se as strings fossem de tamanho substancial.)

Passos em direção a uma solução heurística

Outra abordagem, que pode ser mais fácil de entender e que pode usar um pouco menos de espaço, é procurar o menor “caminho de edição” da sua primeira string para a sua segunda, usando o algoritmo (basicamente, o melhor primeiro ramo e limite). O espaço de pesquisa seria definido diretamente pelas suas operações de edição. Agora, para uma grande cadeia, você fariaAA obtenha uma vizinhança grande, pois você pode excluir qualquer caractere (fornecendo um vizinho para cada exclusão em potencial) ou duplicar qualquer caractere (novamente, fornecendo um número linear de vizinhos), além de adicionar qualquer caractere em cada extremidade, o que dê a você um número de vizinhos igual ao dobro do tamanho do alfabeto. (Só espero que você não esteja usando Unicode completo ;-) Com um fanout tão grande, é possível obter uma aceleração substancial usando um bidirecional ou algum parenteA .

Para fazer o funcionar, você precisará de um limite inferior para a distância restante até o seu alvo. Não tenho certeza se existe uma escolha óbvia aqui, mas o que você poderia fazer é implementar uma solução de programação dinâmica com base na decomposição recursiva que forneci acima (novamente com possíveis problemas de espaço, se suas seqüências de caracteres forem muito longas). Embora essa decomposição não calcule exatamente a sua distância, ela é garantida como um limite inferior (porque é mais permissivo), o que significa que funcionará como uma heurística em . (Não sei quão apertado será, mas estaria correto.) É claro que a memorização de sua função vinculada poderia ser compartilhada em todos os cálculos do limite durante seuA A AAAcorre. (Uma troca de tempo / espaço lá.)

Então…

A eficiência da minha solução proposta parece representar bastante (1) o comprimento das suas strings e (2) o tamanho do seu alfabeto. Se nenhum dos dois for enorme, pode funcionar. Isso é:

  • Implemente o limite inferior à sua distância usando minha decomposição recursiva e programação dinâmica (por exemplo, usando uma função recursiva memorizada).
  • Implemente (ou bidirecional ) com suas operações de edição como "movimentos" no espaço de estados e o limite inferior baseado em programação dinâmica.A AA

Eu realmente não posso dar nenhuma garantia de quão eficiente seria, mas deve estar correto, e provavelmente seria muito melhor do que uma solução de força bruta.

Se nada mais, espero que isso lhe dê algumas idéias para futuras investigações.

Magnus Lie Hetland
fonte
0

Algum problema relacionado e bem definido seria o problema do alinhamento da sequência . É diferente porque não usa operação de duplicação. Operações definidas são: inserção de caractere, exclusão de caractere, transformação de caractere. O algoritmo popular para resolver esse problema é Needleman-Wunsch .

Martinsos
fonte
Eu conheço esse, mas realmente quero trabalhar com um conjunto de movimentos definidos. A única maneira que encontrei para fazê-lo é com um algoritmo recursivo de força bruta. Não é muito legal e ele pode se tornar um computador intensivo se o tamanho das palavras aumentar.
Cz3rk