List elements to consider each's nearest 3 neighbors

Question

A list of strings, some of them are actually of the same content (as outlined) but of minor difference.

I want to find out the similar strings. A possible way is by using similarity ratio from SequenceMatcher of (difflib).

from difflib import SequenceMatcher
import itertools

mylist = [

"I say,",
"It's in the reach of my arms",
"The span of my hips,",
"The stride of my step,",
"The curl of my lips.",
"I'm a woman",
"Phenomenally.",
"Phenomenal woman,",
"That's me.",
"I say.",
"It's the fire in my eyes,",
"And the flash of my teeth,",
"The swing in my waist,",
"And the joy in my feet.",
"I'm a woman.",
"Phenomenally!",
"Phenomenal women,",
"That's us.",
]

for a, b in itertools.combinations(mylist, 2):
    score = SequenceMatcher(None, a, b).ratio()
    if score >= 0.90:
        print (a + " TO " + b + " : " + str(SequenceMatcher(None, a, b).ratio()))

Output:

I'm a woman TO I'm a woman. : 0.9565217391304348
Phenomenally. TO Phenomenally! : 0.9230769230769231
Phenomenal woman, TO Phenomenal women, : 0.9411764705882353

When the list became very long, it takes long time to generate the output, so I am thinking to sort the list, and only measure the similarity of each string/element's nearest 3 neighbors.

For example, for elements #1 in the sorted list, it only measure itself against #2,#3,#4. for elements #10 in the sorted list, it only measure itself against [#7,#8,#9], and [#11,#12,#13].

So I tried:

mylist.sort(reverse=False)

for num, content in enumerate(mylist):
    for a in mylist[num+1:num+4]:
        score = SequenceMatcher(None, a, content).ratio()
        if score >= 0.90:
            print (a + " TO " + content + " : " + score)


for num, content in enumerate(mylist):
    if num >= 4:
        for a in mylist[num-1:num-4]:
            score = SequenceMatcher(None, a, content).ratio()
            if score >= 0.90:
                print (a + " TO " + content + " : " + str(score))

Much faster it works with long list. But I am wondering, is there a better way? Thank you.

user_2307345 · Answer

In my opinion, it might be better to use the levenshtein distance. It has a computational complexity of O(n^(2 - ε)). According to wiki:

the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.

you can check this implementation for reference. Excerp from the link:

import numpy as np

def levenshtein(seq1, seq2):
    size_x = len(seq1) + 1
    size_y = len(seq2) + 1
    matrix = np.zeros ((size_x, size_y))
    for x in xrange(size_x):
        matrix [x, 0] = x
    for y in xrange(size_y):
        matrix [0, y] = y

    for x in xrange(1, size_x):
        for y in xrange(1, size_y):
            if seq1[x-1] == seq2[y-1]:
                matrix [x,y] = min(
                    matrix[x-1, y] + 1,
                    matrix[x-1, y-1],
                    matrix[x, y-1] + 1
                )
            else:
                matrix [x,y] = min(
                    matrix[x-1,y] + 1,
                    matrix[x-1,y-1] + 1,
                    matrix[x,y-1] + 1
                )
    print (matrix)
    return (matrix[size_x - 1, size_y - 1])

Or if you want to use a library, you can freely use python-Levenshtein

List elements to consider each's nearest 3 neighbors

1 Answers