{"id":8291,"date":"2023-10-04T06:00:57","date_gmt":"2023-10-04T04:00:57","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8291"},"modified":"2024-05-16T19:41:04","modified_gmt":"2024-05-16T17:41:04","slug":"04-oct-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/04-oct-23\/","title":{"rendered":"La distancia Levenshtein (con programaci\u00f3n din\u00e1mica)"},"content":{"rendered":"<p>La distancia de Levenshtein (o distancia de edici\u00f3n) es el  m\u00ednimo de operaciones requeridas para transformar una cadena de caracteres en otra. Las operaciones de edici\u00f3n que se pueden hacer son:<\/p>\n<ul>\n<li>insertar un car\u00e1cter (por ejemplo, de \u00ababc\u00bb a \u00ababca\u00bb)<\/li>\n<li>eliminar un car\u00e1cter (por ejemplo, de \u00ababc\u00bb a \u00abac\u00bb)<\/li>\n<li>sustituir un car\u00e1cter (por ejemplo, de \u00ababc\u00bb a \u00abadc\u00bb)<\/li>\n<\/ul>\n<p>Por ejemplo, la distancia de Levenshtein entre \u00abcasa\u00bb y \u00abcalle\u00bb es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro:<\/p>\n<pre lang=\"text\">\n   \"casa\"  --> \"cala\"  (sustituci\u00f3n de 's' por 'l')\n   \"cala\"  --> \"calla\" (inserci\u00f3n de 'l' entre 'l' y 'a')\n   \"calla\" --> \"calle\" (sustituci\u00f3n de 'a' por 'e')\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   levenshtein :: String -> String -> Int\n<\/pre>\n<p>tal que <code>levenshtein xs ys<\/code> es la distancia de Levenshtein entre <code>xs<\/code> e <code>ys<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   levenshtein \"casa\"  \"calle\"    ==  3\n   levenshtein \"calle\" \"casa\"     ==  3\n   levenshtein \"casa\"  \"casa\"     ==  0\n   levenshtein \"ana\" \"maria\"      ==  3\n   levenshtein \"agua\" \"manantial\" ==  7\n<\/pre>\n<p><!--more--><\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Levenshtein where\n\nimport Data.Array(Array, (!), array)\nimport Test.Hspec (Spec, hspec, it, shouldBe)\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\n-- =============================\n\nlevenshtein1 :: String -> String -> Int\nlevenshtein1 \"\" ys = length ys\nlevenshtein1 xs \"\" = length xs\nlevenshtein1 c1@(x:xs) c2@(y:ys)\n  | x == y    = levenshtein1 xs ys\n  | otherwise = 1 + minimum [ levenshtein1 xs c2\n                            , levenshtein1 c1 ys\n                            , levenshtein1 xs ys]\n\n-- 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =========================================\n\nlevenshtein2 :: String -> String -> Int\nlevenshtein2 xs ys = matrizLevenshtein xs ys ! (m,n)\n  where  m = length xs\n         n = length ys\n\n-- (matrizLevenshtein xs ys) es la matriz cuyo n\u00famero de filas es la\n-- longitud de xs, cuyo n\u00famero de columnas es la longitud de ys y en\n-- valor en la posici\u00f3n (i,j) es la distancia de Levenshtein entre los\n-- primeros i caracteres de xs y los j primeros caracteres de ys. Por\n-- ejemplo,\n--    \u03bb> elems (matrizLevenshtein \"casa\" \"calle\")\n--    [0,1,2,3,4,5,1,0,1,2,3,4,2,1,0,1,2,3,3,2,1,1,2,3,4,3,2,2,2,3]\n-- Gr\u00e1ficamente,\n--       c a l l e\n--     0,1,2,3,4,5,\n--  c  1,0,1,2,3,4,\n--  a  2,1,0,1,2,3,\n--  s  3,2,1,1,2,3,\n--  a  4,3,2,2,2,3\nmatrizLevenshtein :: String -> String -> Array (Int,Int) Int\nmatrizLevenshtein xs ys = q where\n  q = array ((0,0),(m,n)) [((i,j), f i j) | i <- [0..m], j <- [0..n]]\n  m = length xs\n  n = length ys\n  f 0 j = j\n  f i 0 = i\n  f i j | xs !! (i-1) == ys !! (j-1) = q ! (i-1,j-1)\n        | otherwise                  = 1 + minimum [ q ! (i-1,j)\n                                                   , q ! (i,j-1)\n                                                   , q ! (i-1,j-1)]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> levenshtein1 (show (2^33)) (show (3^33))\n--    12\n--    (16.19 secs, 11,766,254,536 bytes)\n--    \u03bb> levenshtein2 (show (2^33)) (show (3^33))\n--    12\n--    (0.02 secs, 0 bytes)\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspec :: Spec\nspec = do\n  it \"ej1\" $\n    levenshtein1 \"casa\"  \"calle\"    `shouldBe`  3\n  it \"ej2\" $\n    levenshtein1 \"calle\" \"casa\"     `shouldBe`  3\n  it \"ej3\" $\n    levenshtein1 \"casa\"  \"casa\"     `shouldBe`  0\n  it \"ej4\" $\n    levenshtein1 \"ana\" \"maria\"      `shouldBe`  3\n  it \"ej5\" $\n    levenshtein1 \"agua\" \"manantial\" `shouldBe`  7\n  it \"ej6\" $\n    levenshtein2 \"casa\"  \"calle\"    `shouldBe`  3\n  it \"ej7\" $\n    levenshtein2 \"calle\" \"casa\"     `shouldBe`  3\n  it \"ej8\" $\n    levenshtein2 \"casa\"  \"casa\"     `shouldBe`  0\n  it \"ej9\" $\n    levenshtein2 \"ana\" \"maria\"      `shouldBe`  3\n  it \"ej10\" $\n    levenshtein2 \"agua\" \"manantial\" `shouldBe`  7\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--\n--    ej1\n--    ej2\n--    ej3\n--    ej4\n--    ej5\n--    ej6\n--    ej7\n--    ej8\n--    ej9\n--    ej10\n--\n--    Finished in 0.0024 seconds\n--    10 examples, 0 failures\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa definici\u00f3n (por recursi\u00f3n)\n# =============================\n\ndef levenshtein1(xs: str, ys: str) -> int:\n    if not xs:\n        return len(ys)\n    if not ys:\n        return len(xs)\n    if xs[0] == ys[0]:\n        return levenshtein1(xs[1:], ys[1:])\n    return 1 + min([levenshtein1(xs[1:], ys),\n                    levenshtein1(xs, ys[1:]),\n                    levenshtein1(xs[1:], ys[1:])])\n\n\n# 2\u00aa definici\u00f3n (con programaci\u00f3n din\u00e1mica)\n# =========================================\n\n# matrizLevenshtein(xs, ys) es la matriz cuyo n\u00famero de filas es la\n# longitud de xs, cuyo n\u00famero de columnas es la longitud de ys y en\n# valor en la posici\u00f3n (i,j) es la distancia de Levenshtein entre los\n# primeros i caracteres de xs y los j primeros caracteres de ys. Por\n# ejemplo,\n#    >>> matrizLevenshtein(\"casa\", \"calle\")\n#    [[0, 1, 2, 3, 4, 5],\n#     [1, 0, 1, 2, 3, 4],\n#     [2, 1, 0, 1, 2, 3],\n#     [3, 2, 1, 1, 2, 3],\n#     [4, 3, 2, 2, 2, 3]]\n# Gr\u00e1ficamente,\n#       c a l l e\n#     0,1,2,3,4,5,\n#  c  1,0,1,2,3,4,\n#  a  2,1,0,1,2,3,\n#  s  3,2,1,1,2,3,\n#  a  4,3,2,2,2,3\ndef matrizLevenshtein(xs: str, ys: str) -> list[list[int]]:\n    n = len(xs)\n    m = len(ys)\n    q = [[0 for _ in range(m + 1)] for _ in range(n + 1)]\n    for i in range(n + 1):\n        q[i][0] = i\n    for j in range(m + 1):\n        q[0][j] = j\n    for i in range(1,n + 1):\n        for j in range(1, m + 1):\n            if xs[i - 1] == ys[j - 1]:\n                q[i][j] = q[i - 1][j - 1]\n            else:\n                q[i][j] = 1 + min([q[i-1][j],  q[i][j-1], q[i-1][j-1]])\n    return q\n\ndef levenshtein2(xs: str, ys: str) -> int:\n    m = len(xs)\n    n = len(ys)\n    return matrizLevenshtein(xs, ys)[m][n]\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('levenshtein1(str(2**33), str(3**33))')\n#    13.78 segundos\n#    >>> tiempo('levenshtein2(str(2**33), str(3**33))')\n#    0.00 segundos\n\n# Verificaci\u00f3n\n# ============\n\ndef test_levenshtein() -> None:\n    assert levenshtein1(\"casa\",  \"calle\")     ==  3\n    assert levenshtein1(\"calle\", \"casa\")      ==  3\n    assert levenshtein1(\"casa\",  \"casa\")      ==  0\n    assert levenshtein1(\"ana\",   \"maria\")     ==  3\n    assert levenshtein1(\"agua\",  \"manantial\") ==  7\n    assert levenshtein2(\"casa\",  \"calle\")     ==  3\n    assert levenshtein2(\"calle\", \"casa\")      ==  3\n    assert levenshtein2(\"casa\",  \"casa\")      ==  0\n    assert levenshtein2(\"ana\",   \"maria\")     ==  3\n    assert levenshtein2(\"agua\",  \"manantial\") ==  7\n    print(\"Verificado\")\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>La distancia de Levenshtein (o distancia de edici\u00f3n) es el m\u00ednimo de operaciones requeridas para transformar una cadena de caracteres en otra. Las operaciones de edici\u00f3n que se pueden hacer son: insertar un car\u00e1cter (por ejemplo, de \u00ababc\u00bb a \u00ababca\u00bb) eliminar un car\u00e1cter (por ejemplo, de \u00ababc\u00bb a \u00abac\u00bb) sustituir un car\u00e1cter (por ejemplo, de&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[591],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8291"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8291"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8291\/revisions"}],"predecessor-version":[{"id":8559,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8291\/revisions\/8559"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8291"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8291"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8291"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}