Аналитика

[saippuakauppias]

Прежде чем начать работу - нужно провести рисёрч инструментов/библиотек для удаления нечётких дубликатов строк, которые уже кем-то написаны. И полезно будет сразу же почитать о видах хешей (MinHash, SimHash, MurmurHash).

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

[OlesyaSokolova]

http://www.codeisart.ru/python-shingles-algorithm/
что такое алгоритм шинглов и зачем он нужен
Этапы:
1)канонизация строк:

• очистить текст от ненужных нам знаков и слов, которые не несут смысла при сравнении (т.е. надо сначала определить, какие знаки и слова не нужны)
  На этом этапе можно подключить всякие морфологические анализаторы, например, чтобы привести все слова к единственному числу, именительному падежу и т.д.

2)Разбить текст на подпоследовательности — шинглы.
В статье идет речь про сравнение двух текстовых документов, в нашем случае можно рассмотреть каждую строку как небольшой такой документ, и за шинглы принять слова. Или можно задать длину шингла и выделять из строк последовательности символов заданной длины.

3. Будут сравниваться контрольные суммы шинглов (на этом этапе нужен алгоритм хэширования)
   (например, алгоритм хэширования CRC32 (библиотека binascii))

4. далее

---

Если есть 2 строки, проходимся по каждой -> есть 2 массива контрольных сумм (контрольные суммы для каждого шингла-слова). Далее сравниваем эти множества, можно посчитать количество совпадений, задать число - процент совпадений, на основании которого решаем, являются ли строки нечеткими дубликатами (например, при совпадении >=85% контрольных сумм строки считаются нечеткими дубликатами, и удаляем один из дубликатов.)
Т.е. можно сделать базу, состоящую из массивов; идем по тексту, для каждой строки составляем массив контрольных сумм по её словам. Для каждой новой строки формируется новый массив, и нужно как-то проверить, есть ли такой же массив в базе... Хранить хэш для каждого массива (вместо хэша для строки)? Чтобы не сравнивать каждый массив поэлементно... в общем, не знаю :)

[OlesyaSokolova]

Как сравнивать шинглы: https://housecomputer.ru/seo/shingles/shingles-algorithm.html ( с помощью 84х статических функций)
На этапе подготовки текст разбивается на шинглы = подпоследовательности из слов, в каждой - 10 слов
Проблема: чем больше слов, тем больше получится шинглов, а значит потребуется больше операций сравнения -> неэффективно
Решение: сделать количество сравнений фиксированным, в данном случае - 84.
Пояснение:

1. для каждого шингла рассчитывается 84 значения контрольной суммы через разные функции (например SHA1, MD5, CRC32 и т.д., всего 84 функции). Для каждого текста получается 84 набора контрольных сумм (для каждой функции)
2. из каждого набора каким-то образом выбираем одно значение - например, минимальное. Получится 84 итоговых значения.
3. в итоге из двух текстов получается два набора по 84 элемента, посчитать отношение одинаковых значений -> результат.

[OlesyaSokolova]

библиотека для нечёткого сравнения строк строк, как пользоваться: https://habr.com/ru/post/491448/
(https://pypi.org/project/fuzzywuzzy/)

[OlesyaSokolova]

Есть ещё библиотека whoosh: https://readthedocs.org/projects/whoosh/downloads/pdf/latest/
На 41 странице есть описание fuzzy plugin. На мой взгляд, это может пригодиться на этапе канонизации строк: можно искать похожие слова в строках и заменять их, чтобы они были точно одинаковыми.
Вот здесь пример, как использовать: https://overcoder.net/q/769568/%D0%BD%D0%B5%D1%87%D0%B5%D1%82%D0%BA%D0%B8%D0%B9-%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BE%D0%B2%D1%8B%D0%B9-%D0%BF%D0%BE%D0%B8%D1%81%D0%BA-%D0%B2-%D0%BF%D0%B8%D1%82%D0%BE%D0%BD%D0%B5

[saippuakauppias]

Будет полезно ознакомиться: https://moz.com/devblog/near-duplicate-detection

Бенчмарк большого количества хеш-функций: https://github.com/rurban/smhasher - возможно стоит присмотреться и понять подойдут ли самый быстрые для нашей задачи

[bddin]

Libraries:
Rapid fuzzy string matching using the Levenshtein Distance
https://maxbachmann.github.io/RapidFuzz/

python-string-similarity - a library implementing different string similarity and distance measures using Python
https://github.com/luozhouyang/python-string-similarity

SnaPy - python library for detecting near duplicate texts in a corpus at scale using Locality Sensitive Hashing
https://pypi.org/project/snapy/

deduplication removes duplicate documents via popular algorithms such as SimHash, SpotSig, Shingling
https://pypi.org/project/deduplication/

The Python Record Linkage Toolkit is a library to link records in or between data sources. The toolkit provides most of the tools needed for record linkage and deduplication. The package is developed for research and the linking of small or medium sized files.
https://pypi.org/project/recordlinkage/