Ускорение парного нечеткого сопоставления строк в Python - PullRequest
Новая
       32

Ускорение парного нечеткого сопоставления строк в Python

0 голосов
/ 23 декабря 2018

У меня есть коллекция из 40 000 строк, и я хочу сравнить их сходство попарно, используя fuzz.token_set_ratio(), но мой мозг не настроен правильно, чтобы сделать это эффективным способом, даже после изучения векторизации.

ЗдесьВот пример: 

from fuzzywuzzy import fuzz

s = ["fuzzy was a strong bear", 
 "fuzzy was a large bear", 
 "fuzzy was the strongest bear you could ever imagine"]

similarities = []
l = len(s)

for i in range(l):
    similarities.append([])
    for j in range(l):
        similarities[i].append(fuzz.token_set_ratio(s[i], s[j]))
similarities

Теперь, очевидно, этот код имеет как минимум два коротких замысла.Во-первых, он использует неэффективные циклы for.Во-вторых, хотя получающаяся матрица similarities является симметричной (это не всегда верно, но пока игнорируйте это), и мне нужно только вычислить верхний или нижний треугольник, она вычисляет все элементы.Последнее, пожалуй, то, что я мог бы описать, но я ищу самый быстрый способ достижения similarities в Python.

Редактировать: Вот еще одна часть, возможно, полезной информации.Я попытался ускорить процесс, используя pdist, который, по-видимому, хорошо работает для некоторых подобных задач.Тем не менее, в этом случае он кажется медленнее, чем мои неэффективные циклы for по какой-то причине.

Вот код: 

from fuzzywuzzy import fuzz
from scipy.spatial.distance import pdist, squareform
import numpy as np

def pwd(string1, string2):
    return fuzz.token_set_ratio(string1, string2)

s = []
for i in range(100):
    s.append("fuzzy was a strong bear")
    s.append("fuzzy was a large bear")
    s.append("fuzzy was the strongest bear you could ever imagine")

def pwd_loops():
    similarities = []
    l = len(s)
    for i in range(l):
        similarities.append([])
        for j in range(l):
            similarities[i].append(fuzz.token_set_ratio(s[i], s[j]))

a = np.array(s).reshape(-1,1)
def pwd_pdist():
    dm = squareform(pdist(a, pwd))

%time pwd_loops()
#Wall time: 2.39 s

%time pwd_pdist()
#Wall time: 3.73 s
...