Как сравнить два списка по совпадениям слов в первом с предложениями во втором?

Question

Есть интересная задача, думаю как к ней поступиться. Есть 2-а списка: а содержит списко слов, b - 5 предложений.

Нужно подумать как лучше, циклом или может другим способом. Сравнить из a списка слова со всеми строками b списка, и выбрать из них топ 3 наиболее схожих, т.е. самых высоких по проценту совпадения.

a = ['мама', 'мыла', 'раму']
b = [
    'человек развивает свой ум'
    , 'мама любит котят'
    , 'мама ремонтирует раму'
    , 'папа моет рамы'
    , 'мама установила приложение'
    ]

Answer 1

Алгоритм:

сначала нормализуем слова - приводим все слова в нормальную форму (именительный падеж, настоящее время, etc.)
отбрасываем стоп-слова
строим разреженную бинарную матрицу (one hot encoding) для 5000 - 10000 наиболее часто употребляемых слов
далее можно считать косинусное расстояние между векторами (строками матрицы) и выбираем N векторов с наименьшим расстоянием

PS попробую набросать небольшой рабочий пример когда появится больше свободного времени

Answer 2

Ниже приведено 3 варианта решения 1) без нормализации, 2) с нормализацией слов, 3) с использованием difflib.

Вариант 1. Пример решения без нормализации слов:

a = ['мама', 'мыла', 'раму']
b = [
    'человек развивает свой ум',
    'мама любит котят',
    'мама ремонтирует раму',
    'папа моет рамы',
    'мама установила приложение',
]

set1 = set(w.lower() for w in a)
print(set1)

# веса похожести для каждого словосочетания
w = [(s, len(set(s.lower().split()) & set1)) for s in b]
print(w)

# сортировка в убывающем порядке по весам
c = sorted(w, key=lambda el: -el[1])
print(c)

# Топ 3
print(c[:3])

Результаты работы кода:

{'мыла', 'раму', 'мама'}
[('человек развивает свой ум', 0), ('мама любит котят', 1), ('мама ремонтирует раму', 2), ('папа моет рамы', 0), ('мама установила приложение', 1), ('Мамочка помыла все рамы и искупала котят', 0), ('Мама помыла раму', 2)]
[('мама ремонтирует раму', 2), ('Мама помыла раму', 2), ('мама любит котят', 1), ('мама установила приложение', 1), ('человек развивает свой ум', 0), ('папа моет рамы', 0), ('Мамочка помыла все рамы и искупала котят', 0)]
[('мама ремонтирует раму', 2), ('Мама помыла раму', 2), ('мама любит котят', 1)]

Вариант 2. Упрощенный вариант с нормализацией слов:

import pymorphy2
from functools import lru_cache

a = ['мама', 'мыла', 'раму']
b = [
    'человек развивает свой ум',
    'мама любит котят',
    'мама ремонтирует раму',
    'папа моет рамы',
    'мама установила приложение',
    'Мамочка помыла все рамы и искупала котят',
    'Мама помыла раму',
    'Маме моет мылом раму',
]

morphy = pymorphy2.MorphAnalyzer()
# Упрощенный метод нормализации слов, не совсем правильно преобразует слова:
# помыла-> помыть; мыла -> мыло; мамочка -> мамочка
# но правильно:
# маму -> мама, котят -> "котёнок", "мылом" -> "мыло"

@lru_cache(maxsize=32)
def normalize(word):
    return morphy.parse(word)[0].normal_form

set1 = set(normalize(w) for w in a)
print(set1)

# веса похожести для каждого словосочетания
w = [(s, len(set(normalize(w) for w in s.split()) & set1)) for s in b]
print(w)

# сортировка в убывающем порядке по весам
c = sorted(w, key=lambda el: -el[1])
print(c)

# Топ 3
print(c[:3])

Результаты работы кода варианта с нормализацией:

{'рам', 'мама', 'мыло'}
[('человек развивает свой ум', 0), ('мама любит котят', 1), ('мама ремонтирует раму', 2), ('папа моет рамы', 0), ('мама установила приложение', 1), ('Мамочка помыла все рамы и искупала котят', 0), ('Мама помыла раму', 2), ('Маме моет мылом раму', 3)]
[('Маме моет мылом раму', 3), ('мама ремонтирует раму', 2), ('Мама помыла раму', 2), ('мама любит котят', 1), ('мама установила приложение', 1), ('человек развивает свой ум', 0), ('папа моет рамы', 0), ('Мамочка помыла все рамы и искупала котят', 0)]
[('Маме моет мылом раму', 3), ('мама ремонтирует раму', 2), ('Мама помыла раму', 2)]

Pymorphy можно настроить и сделать чтобы он более точно определял нормальную форму слов.

Вариант 3. С использованием difflib:

import difflib

def similarity(s1, s2):
    normalized1 = s1.lower()
    normalized2 = s2.lower()
    matcher = difflib.SequenceMatcher(None, normalized1, normalized2)
    return matcher.ratio()

a = ['мама', 'мыла', 'раму']
b = [
    'человек развивает свой ум',
    'мама любит котят',
    'мама ремонтирует раму',
    'папа моет рамы',
    'мама установила приложение',
    'Мамочка помыла все рамы и искупала котят',
    'Мама помыла раму',
    'Маме моет мылом раму',
]

sa = " ".join(a)

# веса похожести для каждого словосочетания
w = [(s, similarity(sa, s),) for s in b]
print(w)

# сортировка в убывающем порядке по весам
c = sorted(w, key=lambda el: -el[1])
print(c)

# Топ 3 с коэффициентами
print(c[:3])

# Топ 3
print([s[0] for s in c[:3]])

Результаты работы варианта 3:

[('человек развивает свой ум', 0.2564102564102564), ('мама любит котят', 0.4666666666666667), ('мама ремонтирует раму', 0.6285714285714286), ('папа моет рамы', 0.5714285714285714), ('мама установила приложение', 0.45), ('Мамочка помыла все рамы и искупала котят', 0.5185185185185185), ('Мама помыла раму', 0.9333333333333333), ('Маме моет мылом раму', 0.7058823529411765)]
[('Мама помыла раму', 0.9333333333333333), ('Маме моет мылом раму', 0.7058823529411765), ('мама ремонтирует раму', 0.6285714285714286), ('папа моет рамы', 0.5714285714285714), ('Мамочка помыла все рамы и искупала котят', 0.5185185185185185), ('мама любит котят', 0.4666666666666667), ('мама установила приложение', 0.45), ('человек развивает свой ум', 0.2564102564102564)]
[('Мама помыла раму', 0.9333333333333333), ('Маме моет мылом раму', 0.7058823529411765), ('мама ремонтирует раму', 0.6285714285714286)]
['Мама помыла раму', 'Маме моет мылом раму', 'мама ремонтирует раму']

БЛОГ НА HUSL

Как сравнить два списка по совпадениям слов в первом с предложениями во втором?

Ответы (2 шт):