Блог

Я пытаюсь найти похожие электронные письма в списке. Для этого,

database.head()

     TID PID Names
0   22330   134575  tim
1   22333   134578  tim.rand
2   22328   134571  rand.001
3   22340   134568  pankit090
4   22325   134569  timrook
  

emailsdb = database['Names'].values.tolist()
Теперь часть итерации

 list = []
for email in emailsdb :
    result = process.extractBests(email, emailsdb, score_cutoff=85, limit=100)
    list.append(result)
  

Вывод списка

 [[('tim', 100), ('tim.rand', 90), ('timrook', 90)],
 [('tim.rand', 100), ('tim', 90)],
 [('rand.001', 100)],
 [('pankit090', 100),
  ('pankit001', 89),
  ('pankit002', 89),
  ('pankit003', 89),
  ('pankit004', 89),
  ('pankit005', 89)],
 [('timrook', 100), ('tim', 90)],
 [('pankit001', 100),
  ('pankit090', 89),
  ('pankit002', 89),
  ('pankit003', 89),
  ('pankit004', 89),
  ('pankit005', 89)],
 [('pankit002', 100),
  ('pankit090', 89),
  ('pankit001', 89),
  ('pankit003', 89),
  ('pankit004', 89),
  ('pankit005', 89)],
  

но я хочу избежать (‘tim’, 100), (‘tim.rand’, 100), (‘rand.001’, 100), (‘pankit090’, 100), (‘timrook’, 100), (‘pankit001’, 100), (‘pankit002’, 100) потому что они, очевидно, идеально подходят

Публикую это как еще один ответ, поскольку это решает проблему совершенно другим способом, в свете обсуждения, которое у нас было в чате.

Подход —

1. Если вы используете коммутативную функцию для получения совпадений строк, то фактически вы можете вычислить только нижнюю треугольную матрицу матрицы расстояний, поскольку f (x, y) будет таким же, как f (y, x).

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

3. Итак, сначала вы берете индексы для нижней треугольной матрицы и выполняете итерацию по ним, чтобы вычислить левое расстояние электронных писем с этими индексами. Вы не выполняете итерацию по диагонали матрицы расстояний f (x, x), потому что это тривиально, а позже вы устанавливаете ее как высокое значение, например 999, чтобы вы могли найти минимальные значения оценки в каждой строке.

4. Это дает вам матрицу расстояний (см. Выходные данные). Далее для каждой строки (email) вы находите ближайшую строку (минимальное расстояние) и создаете ее как кортеж наилучших совпадений (см. Выходные данные)

5. Теперь проблема здесь в том, что даже если ни одна из строк не соответствует так хорошо, она все равно с жадностью получит ближайшую.

6. Итак, наконец, вы можете использовать fuzz.ratio между этими строками и получить нечеткие оценки, по которым вы можете фильтровать. Итак, теперь вы можете избежать совпадений с мусором и получать только те, которые действительно совпадают выше определенного порога. Это дает окончательные соответствующие строки (см. Выходные данные)

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

 import pandas as pd
import numpy as np

#!pip install python-Levenshtein
from Levenshtein import distance
from fuzzywuzzy import fuzz, process

#CHECKING COMMUTATIVE PROPERTY
distance('abcd','bdca') == distance('bdca', 'abcd')
###OUTPUT - TRUE

fuzz.ratio('abcd','bdca') == fuzz.ratio('bdca', 'abcd')
###OUTPUT - FALSE


#Create dummy matrix
m = np.zeros((len(emailsdb),len(emailsdb)))

#Get lower triangular matrix indices
i,j = np.tril_indices(len(emailsdb))

#iterate over lower triangular and get Levenshtein distance for lower triangular
for k in zip(i,j):
    if k[0]!=k[1]:
        m[k] = distance(emailsdb[k[0]], emailsdb[k[1]])
    else:
        m[k] = 0

#Copy lower triangular to upper traingular thanks to COMMUTATIVE PROPERTY
m = m   m.T

#Filling diagonal with 999 so that same string doesnt show up with minimum distance
np.fill_diagonal(m, 999)
print("distance matrix = ")
print(m)

#Get best matches with minimum distance
matches = list(zip([i for i in emailsdb], [emailsdb[i] for i in np.argmin(m, axis=0)]))

print("Best matches = ")
print(matches)


#OPTIONAL -> Filtering out irrelavant matches based on fuzzy match
f = [(*i,fuzz.ratio(*i)) for i in matches if fuzz.ratio(*i)>50]

print("final matching strings - ")
print(f)
  

 distance matrix = 
[[999.   5.   8.   8.   4.]
 [  5. 999.   8.   9.   4.]
 [  8.   8. 999.   6.   8.]
 [  8.   9.   6. 999.   9.]
 [  4.   4.   8.   9. 999.]]


Best matches = 
[('tim', 'timrook'), ('tim.rand', 'timrook'), ('rand.001', 'pankit090'), ('pankit090', 'rand.001'), ('timrook', 'tim')]


final matching strings - 
[('tim', 'timrook', 60), ('tim.rand', 'timrook', 53), ('timrook', 'tim', 60)]
  

Вот код для обработки нечеткого поиска, а затем удаления результатов для исходного списка адресов электронной почты. Поскольку это короткий список, удаление списка совпадений имеет тот же эффект, что и простая очистка исходного списка. Обратите внимание, что процесс удаления мог быть включен в первый цикл отправки электронной почты, но я оставил их отдельными для ясности. Я добавил запись zzzz, чтобы проверить оценку.

 from fuzzywuzzy import fuzz
from fuzzywuzzy import process

# original email list
emailsdb = [
'tim',
'tim.rand',
'rand.001',
'pankit090',
'timrook',
'pankit001',
'pankit002',
'pankit003',
'pankit004',
'pankit005',
'zzzz'
]

print('emailsdb:', emailsdb)

# do fuzzy search and score other emails (including self)
lstres = []
for email in emailsdb :
    result = process.extractBests(email, emailsdb, score_cutoff=85, limit=50)
    lstres.append(result)
    
print('WuzzyResult:', lstres)

# scan match list and create set 
setremove = set()  # no duplicates
for r in lstres:
   setremove |= ({t[0] for t in r})
   
print('setremove:', setremove)

# remove matches from original set
for e in setremove:
   emailsdb.remove(e)
   
print('emailsdb:', emailsdb)
  

Вывод:

 emailsdb: ['tim', 'tim.rand', 'rand.001', 'pankit090', 'timrook', 'pankit001', 'pankit002', 'pankit003', 'pankit004', 'pankit005', 'zzzz']

WuzzyResult: [
[('tim', 100), ('tim.rand', 90), ('timrook', 90)], 
[('tim.rand', 100), ('tim', 90)], [('rand.001', 100)], 
[('pankit090', 100), ('pankit001', 89), ('pankit002', 89), ('pankit003', 89), ('pankit004', 89), ('pankit005', 89)], 
[('timrook', 100), ('tim', 90)], 
[('pankit001', 100), ('pankit090', 89), ('pankit002', 89), ('pankit003', 89), ('pankit004', 89), ('pankit005', 89)], 
[('pankit002', 100), ('pankit090', 89), ('pankit001', 89), ('pankit003', 89), ('pankit004', 89), ('pankit005', 89)], 
[('pankit003', 100), ('pankit090', 89), ('pankit001', 89), ('pankit002', 89), ('pankit004', 89), ('pankit005', 89)], 
[('pankit004', 100), ('pankit090', 89), ('pankit001', 89), ('pankit002', 89), ('pankit003', 89), ('pankit005', 89)], 
[('pankit005', 100), ('pankit090', 89), ('pankit001', 89), ('pankit002', 89), ('pankit003', 89), ('pankit004', 89)], 
[('zzzz', 100)]
]

setremove: {'pankit002', 'pankit005', 'tim', 'rand.001', 'pankit003', 'zzzz', 'pankit090', 'pankit001', 'timrook', 'pankit004', 'tim.rand'}

emailsdb: []
  

Вы можете удалить элементы, которые вы знаете (возможно, с помощью предопределенных знаний), которые вы не хотите сравнивать. Это можно сделать, извлекая эти элементы, а затем сравнивая их, а затем вставляя их обратно.

Это должно решить часть вашей проблемы. Я просто pop выбираю тот же элемент из списка перед сравнением, а затем insert возвращаю его обратно перед следующим циклом. Проверьте печатный вывод для получения более подробной информации —

 import pandas as pd
from fuzzywuzzy import fuzz, process

emailsdb = list(df['Names'])

l = []
for i in range(len(emailsdb)) : 
    email = emailsdb[i] #Popping based on index, rather than comparing email in emailsdb
    emailsdb.pop(i) #Pop the same email string in the list of emails
    print("comparing:",[email],'->',emailsdb)
    result = process.extractBests(email, emailsdb, score_cutoff=85, limit=100)
    l.append(result)
    emailsdb.insert(i, email) #Insert it back

print(l)
  

 comparing: ['tim'] -> ['tim.rand', 'rand.001', 'pankit090', 'timrook']
comparing: ['tim.rand'] -> ['tim', 'rand.001', 'pankit090', 'timrook']
comparing: ['rand.001'] -> ['tim', 'tim.rand', 'pankit090', 'timrook']
comparing: ['pankit090'] -> ['tim', 'tim.rand', 'rand.001', 'timrook']
comparing: ['timrook'] -> ['tim', 'tim.rand', 'rand.001', 'pankit090']

[[('tim.rand', 90), ('timrook', 90)], [('tim', 90)], [], [], [('tim', 90)]]
  

Как вы можете видеть, избыточные сравнения не являются частью выходных данных.

Обратите внимание, я НЕ СРАВНИВАЮ электронное письмо, которое есть в списке адресов электронной почты, со всем списком адресов электронной почты для его удаления. Я просто удаляю 0-е, 1-е, 2-е … индексное электронное письмо из списка электронной почты, используя последовательный характер итерации для удаления электронного письма. Это значительное ускорение.

Вы можете изменить этот подход для работы с наборами элементов, которые, как вы уже знаете, похожи и их не нужно сравнивать.

P.S: Пожалуйста, пожалуйста, пожалуйста, пожалуйста, не используйте list в качестве имени переменной 🙂