Edit_Distance_Between_Two_Strings.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Edit_Distance_Between_Two_Strings",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/kenanmorani/Speech_Signal_Processing_idu/blob/main/Edit_Distance_Between_Two_Strings.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5QK1cJmiqBqh"
      },
      "source": [
        "# Problem\n",
        "Write a computer program to compute the minimum edit distance between two strings. Compute the edit distance between the following strings using your code. Additionally, determine the best path. \n",
        "Apply the code on the following strings transformations:               \n",
        "AHMET -> MUHAMMET                                         \n",
        "INTENTION -> EXECUTION                            \n",
        "KERAMET -> MERHAMET                  \n",
        "\n",
        "In the code, define the cost for each operation as follows:          \n",
        "Delete cost = 0.7                   \n",
        "Insert cost = 0.7                              \n",
        "Substitute cost = 1.0                    \n",
        "Match does not have a cost"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GrWgk3ppqOSv"
      },
      "source": [
        "# Solution\n",
        "* The following solution uses a 'Recursive Function' to compute the edit distance between strings.\n",
        "* 'string1' or 'seq1' is the source string and 'string2' or 'seq2' is the target string \n",
        "* Edit Distance Definiftion:                                  \n",
        "Edit distance can be defined as a method for quantifying how dissimilar two strings are to one another. The strings can be two words for an example. The edit distance algorithm counts the minimum number of operations which are required to transform one of the string to the other."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SHsd64fJfrzj"
      },
      "source": [
        "# Edit Distance costs\n",
        "del_cost = 0.7 # The delete cost\n",
        "ins_cost = 0.7 # The insert cost\n",
        "sub_cost = 1  # The substitute cost\n",
        "# Match does not have a cost"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DObpqqbLonXT"
      },
      "source": [
        "# Building a recursive for the two strings and compute the edit distance and the operations path\n",
        "# String1 is a resource and string2 is the target\n",
        "\n",
        "def edit_distance_recurse(seq1, seq2, operations=[]):\n",
        "\n",
        "     # If string2 is empty, then just delete string1 \n",
        "    if len(seq2) == 0:\n",
        "        operations = operations + ([f\"Delete `{seq1}` from sequence1.\"] if len(seq1) else [])\n",
        "        return len(seq1), operations\n",
        "\n",
        "    # If the string1 is empty, then just replace it with string2\n",
        "    if len(seq1) == 0:\n",
        "        operations = operations + ([f\"Insert `{seq2}` into sequence1.\"] if len(seq2) else [])\n",
        "        return len(seq2), operations\n",
        "    \n",
        "    # If intial values of the strings 1 and 2 are equal, then make no changes\n",
        "    if seq1[0] == seq2[0]:\n",
        "        operations = operations + [f\"Make no change for character `{seq1[0]}`. There is no cost\"]\n",
        "        return edit_distance_recurse(seq1[1: ], seq2[1: ], operations)\n",
        "    \n",
        "    # If insertion was needed, then calcualte the cost\n",
        "    ins_operations = operations + [f\"Insert `{seq2[0]}` in sequence1. The cost is 0.7\"]\n",
        "    insertion, ins_operations = edit_distance_recurse(seq1, seq2[1: ], ins_operations)\n",
        "    \n",
        "    # If deletion was needed, then calculate the cost\n",
        "    del_operations = operations + [f\"Delete `{seq1[0]}` from sequence1. The cost is 0.7\"]\n",
        "    deletion, del_operations = edit_distance_recurse(seq1[1: ], seq2, del_operations)\n",
        "    \n",
        "    # If substitution was needed, then calculate the cost\n",
        "    sub_operations = operations + [f\"Replace `{seq1[0]}` in sequence1 with `{seq2[0]}`. The cost is 1\"]\n",
        "    substitution, sub_operations = edit_distance_recurse(seq1[1: ], seq2[1: ], sub_operations)\n",
        "    \n",
        "    # calculating the minimum cost\n",
        "    min_cost = min(insertion + ins_cost, deletion + del_cost, substitution + sub_cost)\n",
        "    \n",
        "    if min_cost == (substitution + sub_cost):\n",
        "        return min_cost, sub_operations\n",
        "    elif min_cost == deletion + del_cost:\n",
        "        return min_cost, del_operations\n",
        "    else:\n",
        "        return min_cost, ins_operations"
      ],
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1vxJCTp1otQk",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "97b7fc09-c3fb-483c-be15-b655c207dc2b"
      },
      "source": [
        "seq1 = \"AHMET\"\n",
        "seq2 = \"MUHAMMET\"\n",
        "score, operations = edit_distance_recurse(seq1, seq2)\n",
        "print(f\"Edit Distance between `{seq1}` and `{seq2}` is: {score}\")\n",
        "print(\"\\nOperations performed are:\\n\")\n",
        "for operation in operations:\n",
        "    print(operation)"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Edit Distance between `AHMET` and `MUHAMMET` is: 3.0999999999999996\n",
            "\n",
            "Operations performed are:\n",
            "\n",
            "Replace `A` in sequence1 with `M`. The cost is 1\n",
            "Insert `U` in sequence1. The cost is 0.7\n",
            "Make no change for character `H`. There is no cost\n",
            "Insert `A` in sequence1. The cost is 0.7\n",
            "Make no change for character `M`. There is no cost\n",
            "Insert `M` in sequence1. The cost is 0.7\n",
            "Make no change for character `E`. There is no cost\n",
            "Make no change for character `T`. There is no cost\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zMVj3vDso5do",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c0d7729a-7b4d-4f23-da76-8eff870ecd3c"
      },
      "source": [
        "seq1 = \"INTENTION\"\n",
        "seq2 = \"EXECUTION\"\n",
        "score, operations = edit_distance_recurse(seq1, seq2)\n",
        "print(f\"Edit Distance between `{seq1}` and `{seq2}` is: {score}\")\n",
        "print(\"\\nOperations performed are:\\n\")\n",
        "for operation in operations:\n",
        "    print(operation)"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Edit Distance between `INTENTION` and `EXECUTION` is: 4.4\n",
            "\n",
            "Operations performed are:\n",
            "\n",
            "Replace `I` in sequence1 with `E`. The cost is 1\n",
            "Replace `N` in sequence1 with `X`. The cost is 1\n",
            "Delete `T` from sequence1. The cost is 0.7\n",
            "Make no change for character `E`. There is no cost\n",
            "Replace `N` in sequence1 with `C`. The cost is 1\n",
            "Insert `U` in sequence1. The cost is 0.7\n",
            "Make no change for character `T`. There is no cost\n",
            "Make no change for character `I`. There is no cost\n",
            "Make no change for character `O`. There is no cost\n",
            "Make no change for character `N`. There is no cost\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xrP7tktKpT0C",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "485fe748-6ea1-496c-aae1-551c29b62ada"
      },
      "source": [
        "seq1 = \"KERAMET\"\n",
        "seq2 = \"MERHAMET\"\n",
        "score, operations = edit_distance_recurse(seq1, seq2)\n",
        "print(f\"Edit Distance between `{seq1}` and `{seq2}` is: {score}\")\n",
        "print(\"\\nOperations performed are:\\n\")\n",
        "for operation in operations:\n",
        "    print(operation)"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Edit Distance between `KERAMET` and `MERHAMET` is: 1.7\n",
            "\n",
            "Operations performed are:\n",
            "\n",
            "Replace `K` in sequence1 with `M`. The cost is 1\n",
            "Make no change for character `E`. There is no cost\n",
            "Make no change for character `R`. There is no cost\n",
            "Insert `H` in sequence1. The cost is 0.7\n",
            "Make no change for character `A`. There is no cost\n",
            "Make no change for character `M`. There is no cost\n",
            "Make no change for character `E`. There is no cost\n",
            "Make no change for character `T`. There is no cost\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VbQkEknzjUIi"
      },
      "source": [
        "# References: \n",
        " * https://towardsdatascience.com/learn-to-implement-edit-distance-from-scratch-7a6f34412d07\n",
        " * https://www.geeksforgeeks.org/edit-distance-dp-5/\n",
        " * https://en.wikipedia.org/wiki/Edit_distance"
      ]
    }
  ]
}