{"id":839,"date":"2018-03-19T14:55:36","date_gmt":"2018-03-19T05:55:36","guid":{"rendered":"https:\/\/dong1lkim.oboki.net\/?p=839"},"modified":"2019-09-01T22:21:42","modified_gmt":"2019-09-01T13:21:42","slug":"algorithm-edit-distance","status":"publish","type":"post","link":"https:\/\/oboki.net\/workspace\/python\/algorithm-edit-distance\/","title":{"rendered":"[Algorithm] Edit Distance"},"content":{"rendered":"

Edit Distance<\/h1>\n

\n \ud3b8\uc9d1 \uac70\ub9ac(Edit Distance) \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uace0 Python\uc73c\ub85c Edit Distance \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud574\ubcf8\ub2e4.\n<\/p><\/blockquote>\n

‘KITTEN’\uacfc ‘SITTING’ \ubb38\uc790\uc5f4 \ube44\uad50<\/h2>\n

\ud3b8\uc9d1 \uac70\ub9ac(Edit Distance)\ub294 \uc5b4\ub5a4 \ubb38\uc790\uc5f4\uc744 \ub2e4\ub978 \ubb38\uc790\uc5f4\ub85c \ubc14\uafb8\uae30 \uc704\ud574 \ud544\uc694\ud55c \uc5f0\uc0b0\uc758 \ucd5c\uc18c \ud69f\uc218\ub97c \ub73b\ud55c\ub2e4. \ud55c \ubb38\uc790\uc5f4\uc5d0 \ub300\ud574 \uc0bd\uc785, \uc0ad\uc81c, \ubcc0\uacbd\uc758 \uc5f0\uc0b0\uc744 \uba87 \ubc88\uc5d0 \uac78\uccd0 \ubc14\uafc0 \uc218 \uc788\ub294\uc9c0\ub97c \uae30\uc900\uc73c\ub85c \ub450 \ube44\uad50 \ub300\uc0c1\uc758 \uc720\uc0ac\ub3c4\ub97c \ud310\ub2e8\ud55c\ub2e4.<\/p>\n

‘KITTEN’\uacfc ‘SITTING’\uc744 \ube44\uad50\ud55c\ub2e4\uace0 \ud588\uc744 \ub54c, \ud3b8\uc9d1 \uac70\ub9ac\ub97c \uad6c\ud558\ub294 \uacfc\uc815\uc740 \uc544\ub798\uc640 \uac19\uc774 2\ucc28\uc6d0 \ubc30\uc5f4\uc744 \ud1b5\ud574 \ud655\uc778\ud560 \uc218 \uc788\ub2e4. \ube44\uad50 \ub300\uc0c1 \ubb38\uc790\uc5f4\uc744 \ub450 \ucd95\uc5d0 \ub450\uace0 \uacf5\uc9d1\ud569\uc5d0\uc11c \ubd80\ud130 ‘S’, ‘SI’, ‘SIT’, …, ‘SITTING’ \ubb38\uc790\uc640 {}, ‘K’, ‘KI’, …, ‘KITTEN’ \ubb38\uc790\uc5f4\uc744 \ucc28\ub840\ub300\ub85c \ube44\uad50\ud574 \ub098\uac04\ub2e4.<\/p>\n

\uccab\ubc88\uc9f8 \ud589\uacfc \uc5f4\uc5d0\ub294 \uc544\ub798\uc640 \uac19\uc774 \uacf5\uc9d1\ud569\uacfc \ube44\uad50\ud558\uae30 \ub54c\ubb38\uc5d0 \uc0bd\uc785 \uc5f0\uc0b0\uc774 \uc774\ub904\uc838\uc57c \ud558\ubbc0\ub85c \ubb38\uc790\uc5f4\uc758 \uae38\uc774\uc640 \uac19\ub2e4.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n
–<\/th>\n{}<\/th>\nS<\/th>\nI<\/th>\nT<\/th>\nT<\/th>\nI<\/th>\nN<\/th>\nG<\/th>\n<\/tr>\n<\/thead>\n
{}<\/td>\n0<\/td>\n1<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n5<\/td>\n6<\/td>\n7<\/td>\n<\/tr>\n
K<\/td>\n1<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
I<\/td>\n2<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
T<\/td>\n3<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
T<\/td>\n4<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
E<\/td>\n5<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n
N<\/td>\n6<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\uc774\uc5b4\uc11c \ub450\ubc88\uc9f8 \ud589\uacfc \uc5f4\uc758 \uac12\uc744 \ucc44\uc6cc\ub123\uc744 \ub54c\uc5d0\ub294 \uc138 \uac00\uc9c0 \uc0c1\ud0dc\uac12\uc5d0 \ub530\ub77c \uac12\uc774 \uc815\ud574\uc9c4\ub2e4.<\/p>\n

    \n
  1. D[i – 1][j]\uc5d0\uc11c A[i]\ub97c \ubcc0\ud615\ud560 \ub54c A[1, i – 1]\uc740 B[1, j]\uc640 \ub3d9\uc77c\ud558\uac8c \ubcc0\ud615\ub418\uc5b4 \uc788\uc73c\ubbc0\ub85c A[i]\ub294 \uc0ad\uc81c\ub418\uc5b4\uc57c \ud55c\ub2e4.<\/li>\n
  2. D[i][j – 1]\uc5d0\uc11c B[j]\ub97c \ubcc0\ud615\ud560 \ub54c A[1, i]\ub294 B[1, j – 1]\uacfc \ub3d9\uc77c\ud558\uac8c \ubcc0\ud615\ub418\uc5b4 \uc788\uc73c\ubbc0\ub85c \uc5ec\uae30\uc5d0 B\uac00 \ud55c \uae00\uc790 \uc99d\uac00\ud558\uac8c \ub418\uba74, A\uc758 \ub4a4\uc5d0 B[j]\ub97c \uc0bd\uc785\ud574\uc57c \ud55c\ub2e4.<\/li>\n
  3. D[i – 1][j – 1]\uc5d0\uc11c A[i]\uc640 B[j]\ub97c \ubcc0\ud615\ud560 \ub54c A[i]\uc640 B[j]\uc758 \uac12\uc774 \uac19\ub2e4\uba74 A\ub97c \ucd94\uac00\uc801\uc73c\ub85c \ubcc0\ud615\ud560 \ud544\uc694\uac00 \uc5c6\ub2e4. \ub300\uc2e0 A[i]\uc640 B[j]\uac00 \ub2e4\ub974\ub2e4\uba74 A[i]\ub97c B[j]\ub85c \uc218\uc815\ud558\ub294 \uc5f0\uc0b0\uc774 \ud544\uc694\ud558\ub2e4.<\/li>\n<\/ol>\n

    \uc810\ud654\uc2dd\uc73c\ub85c \ub098\ud0c0\ub0b4\uba74 \ub2e4\uc74c\uacfc \uac19\uace0,<\/p>\n

    $$ D[i][j] = min \\begin{cases} D[i-1][j-1] + 1 \\quad (\\text{if } A[j] \\text{ != } B[j])\\ D[i][j] + 1 \\ D[i][j-1] + 1 \\end{cases} $$<\/p>\n

    \ubc30\uc5f4\uc744 \ubaa8\ub450 \ucc44\uc6b0\uba74 \uc544\ub798\uc640 \uac19\uc740 \uacb0\uacfc\ub97c \uc5bb\uc744 \uc218 \uc788\ub2e4.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n
    –<\/th>\n{}<\/th>\nS<\/th>\nI<\/th>\nT<\/th>\nT<\/th>\nI<\/th>\nN<\/th>\nG<\/th>\n<\/tr>\n<\/thead>\n
    {}<\/td>\n0<\/td>\n1<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n5<\/td>\n6<\/td>\n7<\/td>\n<\/tr>\n
    K<\/td>\n1<\/td>\n1<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n5<\/td>\n6<\/td>\n7<\/td>\n<\/tr>\n
    I<\/td>\n2<\/td>\n2<\/td>\n1<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n5<\/td>\n6<\/td>\n<\/tr>\n
    T<\/td>\n3<\/td>\n3<\/td>\n3<\/td>\n1<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n5<\/td>\n<\/tr>\n
    T<\/td>\n4<\/td>\n5<\/td>\n4<\/td>\n3<\/td>\n1<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n<\/tr>\n
    E<\/td>\n5<\/td>\n6<\/td>\n5<\/td>\n5<\/td>\n4<\/td>\n2<\/td>\n3<\/td>\n4<\/td>\n<\/tr>\n
    N<\/td>\n6<\/td>\n7<\/td>\n6<\/td>\n6<\/td>\n6<\/td>\n5<\/td>\n2<\/td>\n3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    \uc18c\uc2a4\ucf54\ub4dc<\/h2>\n

    Python\uc73c\ub85c \uc704 \ucca0\ucc28\ub97c \uad6c\ud604\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\ub2e4.<\/p>\n

    def print_mat_2d(mat):\n  for i in range(len(mat)): print(mat[i])\n\n#A,B = input(),input()\nA,B = \"kitten\",\"sitting\"\nla,lb = len(A),len(B)\n\nd=[[0 for _ in range(int(lb+1))] for _ in range(int(la+1))]\nfor i in range(1,la+1): d[i][0]=i\nfor i in range(1,lb+1): d[0][i]=i\n\nfor i in range(1,la+1):\n  for j in range(1,lb+1):\n    d[i][j] = d[i-1][j-1] if A[i-1] == B[j-1] else min(min(d[i-1][j-1],d[i][j-1]),d[i-1][j-1])+1\n\nprint_mat_2d(d)\nprint(\"Edit distance of '\"+A+\"' and '\"+B+\"' is\", d[la][lb])\n<\/code><\/pre>\n
    print_mat_2d<\/code> \ud568\uc218\ub294 \ub514\ubc84\uae45\uc744 \uc704\ud574 \ucd94\uac00\ud55c \ud568\uc218.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Edit Distance \ud3b8\uc9d1 \uac70\ub9ac(Edit Distance) \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uace0 Python\uc73c\ub85c Edit Distance \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud574\ubcf8\ub2e4. ‘KITTEN’\uacfc ‘SITTING’ \ubb38\uc790\uc5f4 \ube44\uad50 \ud3b8\uc9d1 \uac70\ub9ac(Edit Distance)\ub294 \uc5b4\ub5a4 \ubb38\uc790\uc5f4\uc744 \ub2e4\ub978 \ubb38\uc790\uc5f4\ub85c \ubc14\uafb8\uae30 \uc704\ud574 \ud544\uc694\ud55c \uc5f0\uc0b0\uc758 \ucd5c\uc18c \ud69f\uc218\ub97c \ub73b\ud55c\ub2e4. \ud55c \ubb38\uc790\uc5f4\uc5d0 \ub300\ud574 \uc0bd\uc785, \uc0ad\uc81c, \ubcc0\uacbd\uc758 \uc5f0\uc0b0\uc744 \uba87 \ubc88\uc5d0 \uac78\uccd0 \ubc14\uafc0 \uc218 \uc788\ub294\uc9c0\ub97c \uae30\uc900\uc73c\ub85c \ub450 \ube44\uad50 \ub300\uc0c1\uc758 \uc720\uc0ac\ub3c4\ub97c \ud310\ub2e8\ud55c\ub2e4. ‘KITTEN’\uacfc ‘SITTING’\uc744 \ube44\uad50\ud55c\ub2e4\uace0 \ud588\uc744 \ub54c, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[17,10],"tags":[150,34],"class_list":["post-839","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-python","tag-algorithm","tag-python"],"_links":{"self":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/839","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/comments?post=839"}],"version-history":[{"count":5,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/839\/revisions"}],"predecessor-version":[{"id":1284,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/839\/revisions\/1284"}],"wp:attachment":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/media?parent=839"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/categories?post=839"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/tags?post=839"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}