Сходство на низове между два вектора от думи

Имам два много дълги O(100k) списъка с думи и трябва да намеря всички подобни двойки. Моето решение има времева сложност O(n*m). Това ли е начин за оптимизиране на този алгоритъм - намаляване на неговата сложност?

def are_similar(first, second):
    threshold = 0.88
    return difflib.SequenceMatcher(a=first.lower(), b=second.lower()).ratio() > threshold


list_1 = ["123456","23456",  ...] # len(list_1) ~ 100k
list_2 =["123123","asda2131", ...] # len(list_2)~ 500k

similar = []
for element_list1 in list_1:
    for element_list2 in list_2:
        if are_similar(element_list1,element_list2 ):
            similar.append((element_list1,element_list2 ))

print (similar)

Кой е най-добрият начин за паралелизиране на горния код? Текущата ми реализация, която не е включена, използва мултипроцесиране. Обединяване на първия цикъл.


python semantics
person user1877600    schedule 05.02.2018    source източник
comment
Просто съм любопитен, симетричен ли е are_similar? Това е are_similar(x, y) == are_similar (y, x)?   -  person Elmex80s    schedule 06.02.2018
comment
@Elmex80s да, симетричен е.   -  person user1877600    schedule 06.02.2018
comment
Не е решение, а гнида, вие всъщност не изчислявате семантичното сходство на два списъка с този метод. Това по никакъв начин не улавя значението на двете части от текста и дали те са сходни.   -  person Nick Chapman    schedule 06.02.2018
comment
@NickChapman прав си. Редактирах името на темата.   -  person user1877600    schedule 06.02.2018

Отговори (1)


arrow_upward
1
arrow_downward

Мога да предложа друго решение, но не съм сигурен дали искате точно същото, което предлагам. Първо, има две lists, ако съпоставим един елемент от списък със самия него, сходството е 1, т.е. точно съвпадение. Така че можем да започнем със следващата дума за сравнение. Сега нека вземем всички думи в единичен списък, като вземем набор от списъци.

list_1 = ["123456","23456",  ...] # len(list_1) ~ 100k
list_2 =["123123","asda2131", ...] # len(list_2)~ 500k


list_3 = list_1 + list_2
list_3 = list(set(list_3)) # this will merge all same words to a list of unique words.
similar = []
for i in range(0, len(list_3)):
    if are_similar(list_3[i], list_3[i+1]):
        similar.append((list_3[i],list_3[i+1]))

print (similar)

Взех тук списък от набор от list of words за сравнение, тъй като ако можем да сравняваме точно едни и същи думи отново и отново и следователно намаляваме значително броя на сравненията на повтарящи се думи. Сложността на този метод е O(n). Надявам се това да помогне.

person Harry_pb    schedule 05.02.2018