Как сравнить есть ли уже такой файл в базе или нет?

Question

[AstonMartin]

Добрый день!

Помогите с задачей, пожалуйста.

Есть несколько сотен тысяч PDF файлов. Постоянно добавляются новые файлы и надо оперативно определять есть ли уже такой файл среди существующих или нет, с точностью совпадения, допустим в 99%. Поэтому по хэшам не подходит.

Как бы вы подошли к решению такой задачи? Какие есть готовые инструменты для этого? Идеально если под node.js

Comments

[Akina]

с точностью совпадения, допустим в 99%. Поэтому по хэшам не подходит.

Вот как раз при высокой, но не 100% точности, сравнение хэшей подходит как нельзя лучше.

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

[AstonMartin]

Akina, а как при не 100% точности подходит сравнение хэшей?
Их вся суть же в том, что при незначительном изменении файла хэш меняется полностью.

Думали еще из файлов выдирать контент, закидывать его в elasticsearch и потом для новых файлов по нему делать поиск. Если находятся данные с 99% совпадением, то считаем их одинаковыми.

[Akina]

а как при не 100% точности подходит сравнение хэшей?

Равенство хэшей не гарантирует равенства исходных объектов. Я имел в виду, что при равенстве хэшей без проверки самих файлов есть ненулевой шанс на коллизию.

Думали еще из файлов выдирать контент, закидывать его в elasticsearch и потом для новых файлов по нему делать поиск.

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

Answer 1

[Довольный Айтишникъ]

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

Comments

[AstonMartin]

Да, про хэши конечно подумал.
Но файлы могут отличаться на чуть чуть. Поэтому и написал, чтобы можно было определять совпадение на 99%.
Типа как делают поисковые системы.

[Довольный Айтишникъ]

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

[AstonMartin]

Довольный Жизнью, нейронные сети тут, по моему, ни при чем. Им же надо много образцов правильных решений.

Рассматриваем этот проект https://fusejs.io/ и эластик.

[Everything_is_not_so_bad]

Довольный Жизнью , это подходит для 100% совпадения. А у дубликаты документа с 99% совпадения не будут найдены.
Кроме того, для определения 100% совпадения вместо комбинации MD5 и SHA1 проще просто взять SHA-256/BLAKE2.

Answer 2

[12rbah]

с точностью совпадения, допустим в 99%.

Вот посмотрите Как сравнить два текста в JS? . https://stackoverflow.com/questions/5042873/javasc...

Проверку на хеш в вашем случае тоже можно делать, т.к. pdf довольно редко редактируют и все передают одну и ту же книгу.

Есть несколько сотен тысяч PDF файлов.

Это реальная проблема или просто от нечего делать придумали? Слишком мало информации по самим документам. в некоторых сферах, где много типовых отчетов это обычное дело когда документ на 95% похож на другой, поменяться может например только одна цифра в дате, и такой документ нельзя будет отбраковывать. И из пдфа вы не всегда можете извлечь текст для сравнения. В общем довольно много подводных камней. Поэтому стоит более конкретно определиться с задачей.

upd: в общем есть еще такая особенность, что нужно правильно выбрать средство для извлечения текста, т.к. многие средства извлекают не всегда весь текст. Ну и еще интересно как быстро вы сравните 1 pdf со 200-300к других pdf, как по мне затраты на этот процесс будут слишком большими. Можно конечно сравнить только часть текста. Да кстати, извлечение текста из pdf медленный процесс, текст из некоторых страниц может извлекаться больше секунды на обычных процах (тестил на документах в 600-700 страниц), я пользовался только некоммерческими решениями, возможно вы найдете что-то быстрее, но парсить pdf вам придется явно не на ноде, т.к. это слишком медленно будет.

Comments

[AstonMartin]

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

Хэш конечно тоже будем пробовать.

За ссылки спасибо!

Answer 3

[Aetae]

Очевидно pdf -> картинка -> одна из множества технологий поиска по картинкам, на хабре полно статей.

Вот только сама задача - бред. PDF - это документ, документы имеют определённый формат и похожи друг на друга по умолчанию. Отличие документа от того же документа с подписью гендира технически - минимально, практически - абсолютно.

Так что выкиньте это из головы, и юзайте хэши.

Comments

[AstonMartin]

Да, вы привели правильный пример. Допустим один документ с подписью, а другой без. И надо признать их одинаковыми и не добавлять копию в базу.

[Akina]

AstonMartin,

Допустим один документ с подписью, а другой без. И надо признать их одинаковыми и не добавлять копию в базу.

Файл с подписью - документ, по сравнению с ним файл без подписи - ничто, нуль, пустое место.

Ещё вариант - есть документ, он проходит регистрацию и получает регномер, формируется новый документ с добавленными номером и датой, Вы определяете его как дубликат и опускаете в корзину...

Answer 4

[Everything_is_not_so_bad]

Можно использовать что-то наподобие перцептивного хэша, а для определения схожести между документом и набором других использовать поиск по СУБД при помощи расстояния Хэмминга.

По описанию задачи перекликается с вопросом Как сравниваются перцептивные хэши?

Comments

[AstonMartin]

Спасибо, посмотрю!