Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Problema da edição de distância (Edit Distance Problem)

0 votos
8 visitas
perguntada Nov 11 em Ciência da Computação por Renan Abrantes (16 pontos)  
editado Nov 11 por Renan Abrantes

A partir de 2 strings X e Y, o problema é transformar a string X em string Y usando 3 tipos elementares de operação de edição: Remover, Inserir e Trocar. O objetivo é encontrar uma sequência de edição, uma sequência de operações de edição que executa a transformação de x para y a um custo mínimo. O custo de uma sequência de edição é definido como a soma do custo de suas operações de edição.

Problema 2.10 do livro Dynamic Programming: A Computational Tool, Prof. Lew Art, Dr. Holger Mauch, Capítulo 2

Compartilhe

1 Resposta

0 votos
respondida Nov 11 por Renan Abrantes (16 pontos)  

Para a solução do problema, utilizando o livro do problema como referência, vamos descrever melhor as operações elementares:

  • Uma operação de remoção D exclui um único caractere de uma string a um custo de c(D)
  • Uma operação de inserção I insere um único caractere em uma string a um custo de c(I) na posição anterior a analisada.
  • Uma operação de troca R substitui um único caractere de uma string por um caractere a um custo de c(R).

Um exemplo de solução manual para transformar a string "carro" na string "cara", seria necessário seguir os seguintes passos:

  1. Partindo da string "carro" é possível perceber que nas 3 primeiras posições não são necessárias alterações
  2. O último elemento não será utilizado na string buscada, então o caractere seria eliminado usando a função D, D('r').
  3. Por fim, temos a string "caro" buscando a string "cara", para isso é vamos trocar o último caractere com a função R, R('o','a').

Seguindo os passos acima tivemos como resultado, para transformar a string "carro" em "cara", o uso único das funçãoe R e D. Porém, como estamos buscando o menor custo, a ordem ou uso de funções poderia ser diferentes. Por exemplo, caso a função R tivesse custo maior que o custo da função D mais o da função I, a função R não seria utilizada.

Para auxiliar no entendimento da solução, vamos entender a comparação de strings posição a posição.

Supondo que a posição em que está analisando um caracter da string de origem ('carro') seja i, e da string resultado ('cara') seja j, é possível perceber que se os caracteres são iguais, não há nada a fazer, então ambas as posições mudam. Caso os caracteres não sejam iguais, e opte-se pela opção da função de remoção, só causa efeitos na string de origem, então ocorre apenas a passagem de posição i. Já na função R, como após a substituições os valores passam a se tornar iguais, ambas as posições mudam. Caso fosse usado a função I ocorreia apenas mudança na posição j, isso porque como é inserido em uma posição já analisada a posição i já está adiantada.

Entendido isso, podemos entender a função de custo para solução do problema:

A imagem será apresentada aqui.

Para criar um ponto comum entre as duas strings é inserido um caractere temporário para que possamos delimitar os valores dos custos. Isso ocorre por que ao comparar uma posição vazia com uma que possua valor, o custo necessário para transformar o vazio na string desejada seria a inserção de todos os caracteres, este valor é chamado de distância. Da mesma forma transformar um valor em vazio seria a remoção de todos os caracteres.
Este valor comum pode ser inserido no início ou final, mas como visto na função custo, utilizaremos no início.

Aplicada a função custo na comparação das strings será encontrada uma matriz em cada variação de posição na matriz refere ao uso de uma função e tem como o valor seu custo. Como o ponto comum das strings são iguais e foram colocados nas primerias posições, a posição [0,0] da matriz tem valor de custo igual a zero, e o elemento da última linha e coluna eu encontro o menor valor de custo. Também é possivel descobrir as funções utilizadas a partir do menor caminho da posição inicial até a final da matriz.

Para iniciar o desenvolvimento em python do código foi inicializada as variáveis de custo de cada função:

I_C = 1
D_C = 1 
R_C = 1

A função que retorna a matriz de custos, conforme a função de custo, é descrita da seguinte forma:

def EDP(string_A, string_B):

    custo = [[0 for x in range(len(string_B) + 1)] for x in range(len(string_A) + 1)] # Matriz de zeros

    for lin in range(len(string_A)+1):      # Caso pela inserção de um espaço no começo
        for col in range(len(string_B)+1):
            if(lin == 0):
                custo[lin][col] = col*D_C 
            elif(col == 0):
                custo[lin][col] = lin*I_C     

    for lin in range(1,len(string_A)+1):   
        for col in range(1,len(string_B)+1):
            if string_A[lin-1] == string_B[col-1]: # Caracteres iguais 
                custo[lin][col] = custo[lin-1][col-1]
            else:
                insere = custo[lin][col-1] + I_C # Inserção
                excui = custo[lin-1][col] + D_C # Exclui
                substitui = custo[lin-1][col-1] + R_C # Substitui

                # Custo mínimo
                custo[lin][col] = min(insere, excui, substitui)

    return custo

Retornando ao exemplo anterior, foi rodado o seguinte código para visualização da matriz para a transformação da string "CARRO" em "CARA":

import numpy as np
print(np.matrix(EDP('CARRO', 'CARA')))

Este algoritimo obteve a seguinte matriz como resultado:

[[0 1 2 3 4]
[1 0 1 2 3]
[2 1 0 1 2]
[3 2 1 0 1]
[4 3 2 1 1]
[5 4 3 2 2]]

Observamos que conforme o esperado o menor custo é 2 (Última linha e coluna)

Alterando os valores de peso para:

I_C = 3
D_C = 2
R_C = 5

Obteve o seguinte resultado:

[[ 0 2 4 6 8]
[ 3 0 3 6 9]
[ 6 2 0 3 6]
[ 9 4 2 0 3]
[12 6 4 2 5]
[15 8 6 4 7]]

O menor custo nesse caso é 7.

...