D
Christian Giammatteo Portfolio
Roblox • C# • C++ • Python
Docs / Python Projects/Min Edit Distance

Min Edit Distance

Python ProjectsSchool Work

Overview

Python program that tries to compute the minimum edit distance (Levenshtein distance) between itself and another string, using dynamic programming.

Key Systems & Features

  • Dynamic Programming
  • Levenshtein Distance

Code Examples

Below are some code snippets from this project.

Source Code
PYTHON
class myclass():
  def greeting(self, x):
    print( 'hello', x, self)

o = myclass()

class mystr(str):
  def greeting( self):
    print( 'hello', self)

  def ins_cost(self,c):
    return 1
  def del_cost(self,c):
    return 1
  def sub_cost(self,c1,c2):
    if c1 == c2:
      return 0
    else:
      return 2

  def print_table(self,table):
    num_rows = len(table[0])
    num_cols = len(table)
    for r in range(num_rows-1,-1,-1):
      for c in range(num_cols):
        print( table[c][r], end=' ')
      print()

  def med(self, target):
    source = '#' + self
    target = '#' + target

    # initialize the table
    table = []
    for c in range(len(target)):
      col = []
      for r in range(len(source)):
        col.append(None)
      table.append(col)

  ## an alternative way to initialize the table:
  ##  table = [ [ None for r in range(len(source)) ]
  ##            for c in range(len(target)) ]

    table[0][0] = (0,None,None)
    for r in range(1,len(source)):
      table[0][r] = (table[0][r-1][0] + self.del_cost(source[r]), 0, r-1)
    for c in range(1,len(target)):
      table[c][0] = (table[c-1][0][0] + self.ins_cost(target[c]), c-1, 0)

    for c in range(1,len(target)):
      for r in range(1,len(source)):
        ic = (table[c-1][r] + self.ins_cost(target[c]), c-1, r)
        dc = (table[c][r-1] + self.del_cost(source[r]), c, r-1)
        sc = (table[c-1][r-1] + self.sub_cost(source[r],target[c]), c-1, r-1)
        table[c][r] = min(ic, dc, sc)

    self.print_table(table)
    return table[-1][-1]

s = mystr('stephen')

Links