Перечислите элементы, чтобы рассмотреть 3 ближайших соседа

Question

Список строк, некоторые из которых на самом деле имеют одинаковое содержание (как обрисовано в общих чертах), но с небольшим отличием.

Я хочу найти похожие строки. Возможный способ - использовать коэффициент сходства из SequenceMatcher из ( 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()))

Вывод:

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

Когда список стало очень длинным, генерация вывода занимает много времени, поэтому я думаю отсортировать список и измерить только сходство ближайших 3 соседей каждой строки / элемента.

Например, для элементов # 1 в отсортированный список, он сравнивает себя только с № 2, № 3, № 4. для элементов № 10 в отсортированном списке он сравнивает себя только с [# 7, # 8, # 9] и [# 11, # 12, # 13].

Итак, я попытался:

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))

Намного быстрее это работает с длинным списком. Но мне интересно, есть ли лучший способ? Спасибо.

Answer 1

Вообще говоря, есть два уровня, которые влияют на время выполнения вашего алгоритма: сколько времени занимает вычисление оценки для одной пары строк и сколько пар вы сравниваете. Как уже указывалось в другом ответе, вы могли бы рассмотреть возможность использования другого показателя c.

. Сосредоточив внимание на второй точке: с N строками, используя базовый c комбинационный подход, вы получаете NxN / 2 сравнения. Ваш модифицированный пример использует heuristi c (соседи в отсортированном списке), чтобы сузить количество сравнений, давая только что-то вроде 10xN сравнений. В то же время, этот heuristi c может не учитывать все интересные пары. Например, «диапазон моих бедер» и «диапазон моих бедер» нельзя сравнивать, потому что они расположены слишком далеко друг от друга в отсортированном списке.

Улучшение может заключаться в сборе строк по длине (вместо этого сортировки), и сравнивайте каждую строку только с теми, которые, например, на 5 символов короче или длиннее. Это может привести к большему количеству пар, чем ваш подход сортировки, и займет больше времени, но вы можете найти кандидатов, которых подход сортировки не даст:

from difflib import SequenceMatcher
from itertools import groupby

mylist = [
  #...
]

# sort strings into sets by length:
stringsByLength = {l : frozenset(g) for l, g in groupby(sorted(mylist, key=len), len)}

for s in mylist:
    # find candidates by length:
    lengths = range(max(1, len(s) - 5), len(s) + 6)
    candidates = (v for l in lengths for v in stringsByLength.get(l, set()) if v > s)
    for c in candidates:
        score = SequenceMatcher(None, s, c).ratio()
        if score >= 0.90:
            print ("{} TO {} : {}".format(s, c, score))

Answer 2

На мой взгляд, было бы лучше использовать расстояние Левенштейна . Он имеет вычислительную сложность O(n^(2 - ε)). Согласно вики:

расстояние Левенштейна между двумя словами - это минимальное количество односимвольных правок (вставок, удалений или замен), необходимых для замены одного слова на другое.

вы можете проверить эту реализацию для справки. Выдержка из ссылки:

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])

Или, если вы хотите использовать библиотеку, вы можете свободно использовать python-Левенштейн