Vectorize pairwise edit distance computation How can I vectorize this function? It takes an array of array of tuples as input and computes the distance between elements using Levenshtein's method. I found some simpler examples but they weren't of much use for me since I couldn't apply the same logic for my problem. Any help with making this code more efficient will be appreciated!

def sim_mat(sequence):
    sim_mat = np.empty(sequence.shape[0], sequence.shape[0])
    for i in range(sequence.shape[0]):
        for j in range(i, sequence.shape[0]):
            distance = levenshtein(sequence[i], sequence[j])
            sim_mat [i, j] = sim_mat [j, i] = distance
    return sim_mat 


EDIT: Here is the levenshtein function that we use to compute the distance:

def levenshtein(seq1, seq2):
    m = len(seq1)
    n = len(seq2)
    dp = [[0]*(n + 1)]*(m + 1))
    for i in range(1, m + 1):
        dp[i][0] = get_sequence_length(seq1[:i])
    for j in range(1, n + 1):
        dp[0][j] = get_sequence_length(seq2[:j])
    for i in range(m + 1):
        for j in range(n + 1):
            if seq1[i - 1] == seq2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i][j - 1] + len(seq2[j - 1]),  # Insert
                               dp[i - 1][j] + len(seq1[i - 1]),  # Remove
                               dp[i - 1][j - 1] + max(len(sets_difference(seq1[i - 1], seq2[j - 1])),
                                                      len(sets_difference(seq2[j - 1], seq1[i - 1]))))
    return dp[m][n]


and get_sequence_length:

def get_sequence_length(sequence):
    return sum(map(len, sequence))


EDIT2: sets_difference

def sets_difference(set1, set2):
    return list(set(set1).difference(set2))


An example sequence would look like this:

[[('a', 'b', 'c'), ('c', 'd')], [('b', 'd', 'f')]]
I do not think vectorisation to buy you anything "in the upper levels".
My guess is the statement little use due to data dependencies is true even more than for 
parallel computing in general.
With SciPy/NumPy I'm out of my depth; drawing on Syncrossus levenshtein.py.
I'd need a better motivation for the distance function - I guess the minimum requirement being triangle inequality
Shot from the hip using set.symmetric_difference() as food for thought:

import numpy as np


def replacement_cost(s1, s2):
    return len(set(s1).symmetric_difference(s2))


def edit_distance(seq1, seq2):
    """ return edit distance between two list-like sequences of sequences
        Args:
            seq1, seq2: subscriptable objects compatible with len()
                containing objects comparable with the `==` operator.
    """
    m = len(seq1)
    n = len(seq2)
    dp = np.zeros(shape=(m, n))
    dp[0, :] = range(0, n)
    dp[:, 0] = range(0, m)

    for i in range(1, m):
        for j in range(1, n):
            cost = 0 if seq1[i] == seq2[j] \
                     else replacement_cost(seq1[i], seq2[j])
            dp[i][j] = min(dp[i][j - 1] + len(seq2[j - 1]),  # Insert
                           dp[i - 1][j] + len(seq1[i - 1]),  # Remove
                           dp[i - 1][j - 1] + cost)          # Replace
    return dp[m-1][n-1]