Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
1.5 kB
3
Indexable
Never
def backtrace(d : np.ndarray):
    """Backtrace for Levenstein Distance

    :param d: Levenstein Distance matrix (np.ndarray)
    :return path:
    :return path:
    """
    path = []
    mods = []
    
    ##########################################
    cur_pos = (d.shape[0] - 1, d.shape[1] - 1)
    # Если кто-то из них 0, то код не остановится и где-то могут выйти отрицательные индексы
    # В питоне это не вызовет ошибки, так как отрицательным индексам соответствуют элементы с конца
    while cur_pos[0] != 0 or cur_pos[1] != 0:
        path.append(cur_pos)

        cur = d[cur_pos[0], cur_pos[1]]
        top = d[cur_pos[0], cur_pos[1] - 1]
        left = d[cur_pos[0] - 1, cur_pos[1]]
        diag = d[cur_pos[0] - 1, cur_pos[1] - 1]

        minimal = min(top, left, diag)

        if diag == minimal:
            if diag == cur:
                mods.append("same")
            elif diag < cur:
                mods.append("subst")
            else:
                raise RuntimeError("Error")
            cur_pos = (cur_pos[0] - 1, cur_pos[1] - 1)

        elif top == minimal:
            mods.append("insert")
            cur_pos = (cur_pos[0], cur_pos[1] - 1)

        elif left == minimal:
            mods.append("del")
            cur_pos = (cur_pos[0] - 1, cur_pos[1])

        else:
            raise RuntimeError("Error")