Untitled
unknown
python
3 years ago
1.5 kB
4
Indexable
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")
Editor is loading...