Python: как быстрее вычислить сходство по Jaccard

Question

В lst_test содержится около 98 000 предложений (длина от 5 до 100 слов) и около 1000 предложений (длина от 5 до 100 слов).Для каждого предложения в lst_test я хочу найти, плагиатируется ли оно из предложения в lst_train.Если предложение является плагиатом, я должен вернуть идентификатор в lst_train или в противном случае ноль.

Теперь я хочу вычислить сходство jaccard каждого предложения в lst_test относительно каждого предложения в lst_train.Вот мой код, b.JaccardSim вычисляет схожесть jaccard двух предложений:

lst_all_p = []
for i in range(len(lst_test)):
    print('i:', i)
    lst_p = []
    for j in range(len(lst_train)):
        b = textSimilarity.TextSimilarity(lst_test[i], lst_train[j])
        lst_p.append(b.JaccardSim(b.str_a,b.str_b))
    lst_all_p.append(lst_p)

Но я обнаружил, что каждый раз вычисления одного предложения с каждым предложением в lst_train занимает больше 1 минуты.Поскольку существует около 1000 предложений, для его завершения может потребоваться около 1000 минут.Это слишком долго.

Ребята, знаете ли вы, как сделать скорость вычислений быстрее или лучший способ решить проблему, чтобы обнаружить предложение, плагиатируется из предложения в lst_train?

Answer 1

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

Если вы хотите найти плагиат, вам следует изучить обнаружение почти дубликатов и локальное хеширование . MinHash и SimHash являются хорошими отправными точками, и библиотека datasketch также может быть полезна.

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