Локально чутливе хешування

Принцип більшості функцій хешування відбитків документів полягає в тому, що вони завжди повертають один і той же результат для кожного окремого входу. Це називається детермінованою поведінкою. При цьому невелика зміна на вході викличе велику зміну на виході (фактично поверне зовсім інший хеш). Це особливо корисно, коли ми хочемо перевірити, чи змінився вхідний документ, а якщо змінився, то отримуємо щось зовсім інше. Прикладом такої функції є MD5 або SHA1.

Якщо ми хочемо вивести вміст вихідних даних з хешу, не існує простого способу зробити це, і у нас немає іншого вибору, окрім як перебирати кожен варіант до тих пір, поки ми не отримаємо збіг. Це пов'язано з тим, що через велику зміну виходу ми не можемо визначити шляхом ітерацій, чи наближаємося ми до мети, чи ні.

Деякі функції хешування, такі як BCrypt, для одних і тих же вхідних даних щоразу повертають інший результат, що робить їх стійкими до хешування паролів. Фактично на виході безпосередньо міститься сіль, що унеможливлює так звану словникову атаку. Ця функція корисна лише для хешування паролів, але дуже непридатна для перегляду документів.

Перевірка схожості документів та пошук дублювання контенту

Уявіть, що ми розв'язуємо алгоритм пошукової системи, яка хоче перевірити, наскільки змінилася веб-сторінка. Або ж він хоче швидко перевірити, чи текст з однієї сторінки схожий на текст на іншій сторінці, або навіть повністю дублюється.

Один із способів перевірити це - порівняти кожну сторінку між собою, що є дуже ресурсномістким для системи. Інший варіант - обчислити хеш SHA1, але він хешує вміст всього документа, і якщо сторінка змінюється всього на один символ, ми отримуємо інший хеш - тому він не підходить для цих цілей.

Тому одне з можливих рішень - обчислювати хеш з різних ділянок документа по-різному, а потім шукати зміни у виході функції хешування.

Принцип локально-чутливого хешування

Ми завантажили HTML-код веб-сторінки, для якої хочемо обчислити хеш. Ми ділимо документ на різні області (комірки) за алгоритмом, який потрібно правильно налаштувати.

Ми хешуємо кожен регіон окремо за загальним алгоритмом і об'єднуємо результат в один рядок.

Результатом може бути, наприклад, 3791744029724361934 (цей хеш контенту був наданий інструментом Ahrefs).

Наприклад, якщо ми знаємо, що вміст верхнього колонтитула представляє перші 5 символів, а нижнього колонтитула - останні 5 символів, ми знаємо, що середина рядка представляє вміст сторінки. Якщо вміст футера змінюється на всіх сторінках (наприклад, веб-майстер додає нове посилання, змінюється дата оновлення тощо), то при завантаженні нової версії сторінки в хеші в правій частині трохи змінюється лише кілька символів, і ми знаємо, що змінився тільки футер, а вміст залишається незмінним. Тож ми можемо проігнорувати таку зміну і не переглядати весь сайт.

Як Google оптимізує веб-сканування?

Інтернет-ботів потрібно економити там, де це можливо. Веб-сканування є дуже дорогим, а оновлення коштує обчислювального часу.

Наприклад, спостерігаючи за поведінкою алгоритму робота Google, я помітив, що він реагує лише на великі зміни в контенті. Якщо сторінка мало змінюється, то вона повзе в звичайному режимі. Але коли, наприклад, суттєво змінюються колонтитули сайту, він оцінює це як редизайн і перебирає одразу більшу частину сайту, щоб якнайшвидше отримати новий вигляд.

Він також виявляє дублікати на різних сайтах аналогічним чином. Коли група сторінок дуже схожа або має однаковий контент, вони отримують дуже схожий хеш, який робот може використовувати для швидкої перевірки схожості документів і може вибрати канонічний, а решту проігнорувати.

Реалізація функції хешування

Готової реалізації локально-чутливої функції хешування в PHP не існує. В той же час, я не знаю жодного вільно розповсюджуваного пакету, який би добре реалізовував цю функцію.

Jan Barášek   Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu:

Kontakt