1

I still don't get it yet how the 2D list/array works to figure out the cost between the strings (Is the tuple in matrix[len(a)][len(b)] right ?

I would like some explanation please kk

I have something going on already. I filled the base cases but don't know how to access the tuples already filled to compute all other cells the code:

    from enum import Enum


    class Operation(Enum):
        """Operations"""

        DELETED = 1
        INSERTED = 2
        SUBSTITUTED = 3

        def __str__(self):
            return str(self.name.lower())

    def distances(a, b):
        """Calculate edit distance from a to b"""


        # generating 2d list
        matrix = []
        for i in range(len(a)+1): #string a and rows
            matrix.append([])
            for j in range(len(b)+1): #string b and columns
                matrix[i].append(0)

        # base cases
        c = 1
        for i in range(len(a)):
            matrix[i+1][0] = (c, Operation.DELETED)
            c += 1
        c = 1
        for j in range(len(b)):
            matrix[0][j+1] = (c, Operation.INSERTED)
            c += 1


        #filling in
        for i in range(len(a)):
            for j in range(len(b)):
                matrix[i+1][j+1] = ('x','y')



        print(matrix)

    distances('cat','ate')
2

See this: https://stackoverflow.com/questions/30792428/wagner-fischer-algorithm

It was the only way I was able to understand the algorithm. Then, once you know what's going on, check this: https://www.youtube.com/watch?v=b6AGUjqIPsA

4
  • up, my code. I think that my code needs to access the first element in the base cases tuples in order to compute the other cells. I dont get this yet – Rafael Áquila May 1 '18 at 23:08
  • First, you have to fill the matrix with the base cases. Your first column and your first row will have the values 0,1,2,3 and so on. Once you have those values, then you can calculate the element (1, 1) of the matrix. Why? Because now you have the values (0,0), (0,1) and (1,0), so you can apply the algorithm (find the minimum of those three value and all that) in order to calculate (1,1). Now that you have the value (1,1), you'll be able to calculate (1,2). Once you have (1,2), calculate (1,3), and so on. This way, you'll be able to fill the entire matrix. – Camilo May 2 '18 at 4:20
  • I get this but that's the problem. Each element is a tuple and I still don't know how to access the first element in the tuple that lives inside the 2d list. I need to iterate over these values in order to fill the cells. – Rafael Áquila May 2 '18 at 23:39
  • Oh, okay... Maybe the answer is useful to someone else, ha. If I get you right this time, you can access the first element of a tuple through the index 0 (tuple[0]). So, you'll have something like this in your code: matrix[i][j][0] – Camilo May 3 '18 at 19:06
2

The cost is actually matrix[len(a)][len(b)][0] (as matrix[len(a)][len(b)] is a tuple like (4, Operation.INSERTED). But you are meant to return the matrix (a list of lists of tuples), and the calling code will figure out.

edit, to answer questions not clear from the actual question but comments:

I assume you watched and understood all the videos on dynamic programming?

matrix[i][j] is equivalent to transforming a[:i] into b[:j].

The base case is matrix[0][0]. This is equivalent to ""->"", means nothing to do, or tuple (0, None). You could also consider a base case elements of form matrix[i][0]. Those are equivalent to "abc"->"", so they can only be constructed by deletion. Elements of form matrix[0][j] can be constructed only by insertion.

All other elements can be constructed with any of the three operations, pick the one with the smallest associated total cost. Don't forget that a substitution of equal characters has no cost (as you don't change anything).

2
  • What I don't get it is how to fill the cells, how to choose the operation and the number of them – Rafael Áquila Apr 29 '18 at 17:49
  • The base cases (first row and column) and the rest of the matrix – Rafael Áquila Apr 29 '18 at 18:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .