-- I1M 2021-22: Relación 22
-- Cálculo de la distancia de Levenshtein
-- Departamento de Ciencias de la Computación e Inteligencia Artificial
-- Universidad de Sevilla
-- ============================================================================
-- ============================================================================
-- Librerías auxiliares
-- ============================================================================
import qualified Data.Array as A
import qualified Data.Matrix as M
type Matriz a = A.Array (Int,Int) a
-- ============================================================================
--
-- ENUNCIADO:
--
-- Dadas dos cadenas de caracteres X e Y se define la distancia de edición o
-- distancia de Levenshtein como el mínimo número de operaciones básicas de
-- edición para transformar X en Y.
--
-- Las operaciones básicas de edición son:
-- 1. Añadir un caracter a X.
-- 2. Eliminar un caracter a X.
-- 3. Sustituir un caracter de X por otro.
--
-- Por ejemplo, si queremos convertir CENA en CAMA podemos eliminar los tres
-- últimos caracteres de CENA para llegar a C y después añadir los tres
-- caracteres AMA para llegar a CAMA. Eso serían un total de 6 operaciones
-- básicas de edición.
-- Pero es mejor sustituir la E por una A y la N por una M para obtener la
-- cadena destino CAMA con solo dos operaciones básicas de edición.
-- Se pretende calcular este número mínimo de operaciones.
--
-- Para ello se va a hacer uso de la técnica de Programación Dinámica usando
-- como estructura auxiliar una matriz M con índices por filas que van desde 0
-- hasta la longitud de la cadena X (lx), y con índices por columnas que van
-- desde 0 hasta la longitud de la cadena Y (ly). En nuestro ejemplo
-- lx = ly = 4.
--
-- En el ejemplo anterior la matriz quedaría dimensionada así:
--
-- 0 1 2 3 4
-- * ------- * ------- * ------- * ------- * ------- *
-- | | | | | |
-- 0 | | | | | |
-- | | | | | |
-- * ------- * ------- * ------- * ------- * ------- *
-- | | | | | |
-- 1 | | | | | |
-- | | | | | |
-- * ------- * ------- * ------- * ------- * ------- *
-- | | | | | |
-- 2 | | | | | |
-- | | | | | |
-- * ------- * ------- * ------- * ------- * ------- *
-- | | | | | |
-- 3 | | | | | |
-- | | | | | |
-- * ------- * ------- * ------- * ------- * ------- *
-- | | | | | |
-- 4 | | | | | |
-- | | | | | |
-- * ------- * ------- * ------- * ------- * ------- *
--
-- La definición de cada posición de la matriz sería la siguiente:
-- M(i,j) es el mínimo número de operaciones básicas de edición para transformar
-- la subcadena X hasta el caracter i-ésimo, en la subcadena Y hasta el caracter
-- j-ésimo.
--
-- Así:
-- * M(0,0) sería 0 ya que ambas subcadenas están vacías.
-- * M(0,1) sería 1 ya que para transformar la cadena vacía en "C" hay que
-- añadir 1 caracter.
-- * M(2,2) sería 1 ya que para transformar la cadena "CE" en "CA" hace falta
-- sustituir un caracter.
-- * M(lx,ly) tendríamos la solución final al problema.
--
-- El ejemplo anterior terminaría con la siguiente matriz:
--
-- C A M A
-- 0 1 2 3 4
-- * ------- * ------- * ------- * ------- * ------- *
-- | | | | | |
-- 0 | 0 | 1 | 2 | 3 | 4 |
-- | | | | | |
-- * ------- * ------- * ------- * ------- * ------- *
-- | | | | | |
-- C 1 | 1 | 0 | 1 | 2 | 3 |
-- | | | | | |
-- * ------- * ------- * ------- * ------- * ------- *
-- | | | | | |
-- E 2 | 2 | 1 | 1 | 2 | 3 |
-- | | | | | |
-- * ------- * ------- * ------- * ------- * ------- *
-- | | | | | |
-- N 3 | 3 | 2 | 2 | 2 | 3 |
-- | | | | | |
-- * ------- * ------- * ------- * ------- * ------- *
-- | | | | | |
-- A 4 | 4 | 3 | 2 | 3 | 2 |
-- | | | | | |
-- * ------- * ------- * ------- * ------- * ------- *
-- Pasos para resolver el Problema
-- 1. Plantee una ecuación en recurrencia que permita resolver este problema.
-- 1.1. Preste atención a los casos base.
-- 1.2. Resuelva el caso recursivo atendiendo a la definición y a los casos
-- particulares que hay en el ejemplo
-- 2. Implemente la función Haskell que construya la matriz anterior y devuelva
-- el elemento en la posición inferior derecha. Para ello use la signatura:
-- distanciaLevenshtein :: String -> String -> Int
-- Como ejemplo de la llamada anterior podríamos hacer:
-- distanciaLevenshtein "CENA" "CAMA" == 2
--
-- ============================================================================
-- Álvaro Galisteo:
distanciaLevenshtein :: String -> String -> Int
distanciaLevenshtein x y = m A.! (lx,ly)
where m = A.listArray ((0,0),(lx,ly)) [f i j| i <- [0..lx], j <- [0..ly]]
lx = length x
ly = length y
f i j | i == 0 && j == 0 = 0
| i == 0 = 1 + m A.! (i,j-1)
| j == 0 = 1 + m A.! (i-1,j)
| x !! (i-1) == y !! (j-1) = m A.! (i-1,j-1)
| otherwise = 1 + minimum [m A.! (i-1,j-1),
m A.! (i-1,j),
m A.! (i,j-1)]
-- ============================================================================
data Mat = Mat [[String]] Int
instance Show Mat where
show (Mat x m) = "/ " ++ (showRow (x !! 0) m) ++ "\\\n" ++
(showIntermediateRows x 1 m) ++
"\\ " ++ (showRow (x !! (length x - 1)) m) ++ "/"
showRow :: [String] -> Int -> String
showRow [] m = []
showRow (x:xs) m = (replicate (m - (length x)) ' ') ++ x ++ " " ++ (showRow xs m)
showIntermediateRows :: [[String]] -> Int -> Int -> String
showIntermediateRows xxs i m | i >= length xxs - 1 = []
| otherwise = "| " ++ showRow (xxs !! i) m ++ "|\n" ++
showIntermediateRows xxs (i+1) m
printMatrix :: Show a => M.Matrix a -> Mat
printMatrix m = Mat (M.toLists nm) mx
where nm = (M.mapPos (\ (i,j) e -> show e) m)
mx = maximum (map (length) (M.toList nm))
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]](/WIKIS/I1M2021G3/resources/assets/logoUS.png)