Оценивать похожесть кусков текста, python

https://habr.com/ru/company/antiplagiat/blog/429634/

Спасибо, интересная статья и алгоритм вроде не сложный, можно самому написать. Но может есть что-то готовое? :)

import Levenshtein https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0

Есть онлайн сервисы для проверки. Наверняка, у них есть API. Тогда останется напитонить только доступ к ним.

2MrClon

Кажется, то что надо. Спасибо!

Эта метрика определенно хороша для исправления опечаток в отдельных словах или сравнении строк, но не для больших текстов с описанием вакансии.

Жаль… А что посоветуете для текстов размером со страницу-две?

либа — lucene

сервант на ней — solr

и там точно было про compare texts

Не эксперт в этом, но гугл выдает такое: https://towardsdatascience.com/overview-of-text-similarity-metrics-3397c4601f50

Так-то да, но как простейшее решение которое можно просто взять и подключить — сойдёт. По хорошему тут конечно нужная как минимум проверка на синонимы

Это еще глубже в кроличью нору: морфология.

Угу, я написал про синонимы и подумал что ещё тут стоит упомянуть, подумал и решил что не хочу с утра пораньше нырять в эту нору, поэтому ограничился упоминанием синонимов (:

difflib.

В Python'е есть модуль difflib. С его помощью можно вычислить похожесть текстов: https://docs.python.org/3/library/difflib.html#difflib.SequenceMatcher.ratio

у нее только недостаток, что ее реализация нативная, а значит при попытке сравнить два текста по 100 килобайт, интерпретатор задумается на пару секунд

Положить в elasticsearch и использовать запросы more like this.

Я заметил, что в базе появляются похожие вакансии

Вы серьезно? Кто бы мог такое представить, что куски текста будут идентичны. Тут уж пишите скрипт для вывода всех вакансий, либо берите какую-то особенную – по дате, по популярности, по чему-то-там-еще.

Вы серьезно? Кто бы мог такое представить, что куски текста будут идентичны.

Проблема не в том, что куски текста повторяются, я понимаю, что в разных вакансиях присутствуют похожие формулировки. Проблема в том, что есть дубли одних и тех же вакансий и для придания им уникальности в наименовании компании и/или должности внесены небольшие изменения.

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

Положить в elasticsearch и использовать запросы more like this.

Кстати интересное предложение, скорее даже больше посмотреть на nosql базу и немного с этим разобраться.

more like this

А это позволяет в каком-то количественном показателе измерять похожесть?

Ну сколько лет уже повторять здесь на форуме… Левенштайн алгоритм - это только учебное пособие для начинающих (хелоу ворлд типа). В реальных условиях работы риалтайм распознавания ошибок им не применимо.

Это даже хуже сортировки методом пузырька.

Казалось бы при чём тут

риалтайм распознавания ошибок

Положить в elasticsearch и использовать запросы more like this.

И так, почитал я и посмотрел видео про elasticsearch. Первое впечатление - это довольно гибкий инструмент поисковых запросов по базе. Под поисковыми запросами я имею ввиду, когда у нас есть некий короткий(!) паттерн, который надо проверить на присутствие в неких текстовых «документах». Гибкость системы в том, что она позволяет делать не строгий запрос, а например перемещать слова в паттерне, предположить грамматическую ошибку, искать два слова из трех и т.п. Причем, результатом поиска будет не просто список документов, которые удовлетворяют запросу, а список отсортированный по релевантности.

Я не изучил в систему запросов elasticsearch достаточно глубоко, но что-то мне показалось, что под мои задачи - сравнить похожесть двух объемных кусков текста, каждый из которых совсем не похож на паттерн, эта система не совсем подходит. Я, конечно, могу ошибаться, давайте попробуем сформулировать запрос в elasticsearch, который мне позволит сравнить один кусок текста, с другими кусками текста и выдать мне некую цифру, которая будет характеризовать похожесть. Не подскажите, как вы это видите?

Тип запроса, который тебе нужен, я указал в первом своем сообщении.

Можно отдельно ещё какую-то свою «меру похожести» ввести, после фильтра elasticsearch. В современном мире в этом рулят нейронки, от word2vec до BERT :).

Попробовал разобраться с этим, установил elasticsearch и создал индекс и несколько документов

PUT /test
{
    "mappings" : {
        "properties" : {
            "description" : { 
                "type" : "text",
                "term_vector": "yes"
            }
        }
    }
}

PUT /test/_doc/1
{
    "description" : "Index operations can be made conditional and only be performed if the last modification to the document was assigned the sequence number and primary term specified"
}

PUT /test/_doc/2
{
    "description" : "There is no \"correct\" number of actions to perform in a single bulk request. Experiment with different settings to find the optimal size for your particular workload."
}

PUT /test/_doc/3
{
    "description" : "Index operations  can be 123 made conditional and only be performed if the last modification to the document was assigned the sequence number and primary term specified."
}

Дальше сделал запрос на выборку

{
    "query": {
        "more_like_this" : {
            "fields" : ["description"],
            "like" : "Index operations  can be 123 made conditional and only be performed if the last modification to the document was assigned the sequence number and primary term specified.",
            "min_term_freq" : 1,
            "max_query_terms" : 5,
            "min_doc_freq": 1
        }
    }
}

Если «max_query_terms» : 5, то выдает все 3 документа, если 10, то уже 2, т.е. увеличение max_query_terms ведет к устрожению поиска, но в тоже время добиться выдачи одного документа не удалось. Если min_term_freq выставить на 2 или больше, всегда поиск выдает 3 документа

Честно говоря не понял, как регулировать строгость поиска, чтобы он в итоге выдавал один документ и что min_term_freq и max_query_terms значат.

Подскажите.

Все параметры расписаны - https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-mlt-query.html#mlt-query-term-selection. max_query_terms=5 - слишком мало для больших документов. По-дефолту 25, должно быть нормально, можно даже увеличить, у вас не миллионы документов.

Зачем добиваться выдачи одного документа? Если туда сложить вакансии с дублями, то логично было бы выдавать все дубли?

Ещё есть https://www.elastic.co/guide/en/elasticsearch/reference/current/analysis-shingle-tokenfilter.html, он составляет ngram’ы слов, как выше в статье на хабре. Подключается через настройку анализатора.

Все параметры расписаны

Да я читал, но понять не могу, хоть у меня и хороший английский.

max_query_terms The maximum number of query terms that will be selected. Increasing this value gives greater accuracy at the expense of query execution speed. Defaults to 25.

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

Я не понимаю, про какое количество условий запроса идет речь? Как оно считается?

min_term_freq The minimum term frequency below which the terms will be ignored from the input document. Defaults to 2.

Минимальная частота условий, ниже которой условия будут игнорироваться из входящего документа.

Какая еще частота условий? Хоть бы объяснили, что они под этими терминами имеют ввиду.

Зачем добиваться выдачи одного документа? Если туда сложить вакансии с дублями, то логично было бы выдавать все дубли?

Мне надо понять, как регулировать точность сравнения, если вдруг будут ложные срабатывания?

«terms» - подразумеваются не условия, а слова, токены

как регулировать точность сравнения, если вдруг будут ложные срабатывания?

Параметром minimum_should_match.

Если это прямо таки небольшие изменения просто сравните количество повторяющихся в них слов, а потом прикиньте порог «одинаковости»

«terms» - подразумеваются не условия, а слова, токены

Т.е. term - это слова в поисковой (like) фразе? Я правильно понимаю, max_query_terms означает количество слов, которые будут выбраны из поисковой фразы и по которым будет осуществлен поиск, в моем случае нужно указать число побольше, т.к. поисковая фраза будет длинная?

min_term_freq это минимальная частота слов в исходном документе, по которым будет осуществляться поиск. Т.е. если мы хотим, чтобы поиск осуществлялся только по словам в поисковой фразе, которые встречаются в ней 3 или более раз, мы устанавливаем параметр 3? В моем случае параметр будет 1.

minimum_should_match - этот надо на практике покрутить и посмотреть, что получается. Спасибо.

Мудреная эта тема elasticsearch. Тяжело заходит после реляционных бд.

Хм, что-то получилось. Эксперименты показали, что это вроде как-то работает. :) Сейчас попробую выгрузить нужные мне записи из mysql в el и посмотреть, уже как ведет себя эта поисковая система на реальных данных.

Если это прямо таки небольшие изменения просто сравните количество повторяющихся в них слов, а потом прикиньте порог «одинаковости»

Если не использовать готовых инструментов, а писать алгоритм с нуля. То мне ближе такой подход: https://habrastorage.org/webt/wu/l1/h5/wul1h5pywezeyiglohu_v7so4jm.png

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

Но я хочу сначала разобраться с elasticsearch раз уже он мне попался :)

Казалось бы при чём тут

При том, что расстояние Левенштайна предусматривает только «очепятки» в виде перестановки символов.

А ты о чём?

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

Итоги работы с elasticsearch

1. Эксперименты с загрузкой кусков html провалился сразу, много ложных срабатываний. Чтобы это пофиксить:

- удалил все html тэги

- заменил все символы, кроме алфавитных на пробелы

- удалил все короткие слова меньше 3 символов и оставил по одному пробелу между словами

2. После такого изменения текста стало лучше :), но все равно есть ложные срабатывания, когда поисковый документ (паттерн) короткий.

Я думаю дожать это еще одно условием добавить в поиске, чтобы размер исходного текста не отличался от того где ищем более чем на 15%. Не знаете как это сделать?

Короче, окончание истории, плюнул на этот elasticsearch и сделал по схеме антиплагиата:

- удаляю из текста все html тэги
- заменяю все, кроме алфавита пробелами и делаю .lower()
- удаляю все слова, в которых меньше чем три буквы
- разбиваю текст на слова
- объединяю первое, второе и третье слово и считаю их хэш
- объединяю второе, третье и четвертое слово и считаю их хэш
....
- удаляю повторяющиеся хэши

Сравниваю list с хэшами одного документа с lists с хешами других документов, высчитывая процент совпадений. Все, работает на ура.