Как оценить полноту парсинга: метод Линкольна–Петерсена

Почему ваш парсер может выдавать неполные данные

Представьте: вы написали парсер, который собирает вакансии компании с LinkedIn. Запуск прошёл успешно, данные есть, но при повторном запуске результаты отличаются. Оказывается, вы получили не все вакансии, а лишь случайную выборку. Как понять, что данных не хватает, и как оценить полноту? В этой статье мы разберём метод, borrowed из экологии — метод Линкольна–Петерсена, и покажем, как применить его в Python для оценки полноты парсинга.

Проблема: нестабильная пагинация и её последствия

При работе с API LinkedIn я обнаружил, что параметр start не гарантирует последовательную выдачу страниц. Запросы с start=0 и start=10 могут вернуть пересекающиеся наборы вакансий. В моём эксперименте при глубине 3 страницы около 33% ID отличались, а при 10 страницах — 61%. Это значит, что простой цикл по смещениям собирает не все вакансии, а лишь их часть.

Последствия оказались двоякими: во-первых, функция отслеживания изменений (какие вакансии открылись/закрылись) давала ложные срабатывания — вакансии, которые просто не попали в текущую выборку, помечались как закрытые. Во-вторых, сам базовый список был неполным, но внешне это никак не проявлялось.

Почему стандартные критерии остановки не работают

Правило «четыре пустых запроса подряд»

Первая попытка определить завершение сбора была эвристической: остановиться, если четыре последовательных запроса не добавили новых данных. Но математика показывает, что это ненадёжно. Если у вас уже есть 650 из 700 вакансий, вероятность того, что страница из 10 не добавит ничего нового, равна (650/700)^10 ≈ 0.478. Четыре таких подряд случаются с вероятностью около 5% — и это лишь на текущем уровне полноты. По мере приближения к полному сбору вероятность растёт, но правило срабатывает в произвольный момент, зависящий от неизвестной нам полноты. Получается замкнутый круг: мы останавливаемся, предполагая, что почти всё собрано, но это предположение и есть то, что мы пытаемся проверить.

Правило «два полных прохода должны совпасть»

Вторая попытка — собрать данные дважды и требовать точного совпадения. Это строго, но бесполезно: две случайные выборки из большого множества почти никогда не совпадают. Условие не выполнялось, и функция не выдавала результат.

Решение: метод Линкольна–Петерсена

Ключевая идея — рассматривать повторные запросы не как повторные попытки, а как выборки. Экологи считают рыбу в пруду так: ловят некоторое количество, метят, выпускают, затем ловят снова и смотрят, сколько меченых попало во второй улов. Если меток мало — пруд большой. Формула Линкольна–Петерсена:

N ≈ (размер выборки A × размер выборки B) / (число общих элементов)

Применим это к парсингу: разделим наши запросы на две группы (например, по чётности проходов), соберём две выборки и оценим общее количество элементов по их пересечению.

Реализация на Python:

def estimate_total(sample_a: set, sample_b: set) -> dict:
    """Оценка общего количества по методу Линкольна–Петерсена."""
    a = len(sample_a)
    b = len(sample_b)
    overlap = len(sample_a & sample_b)
    if overlap == 0:
        return {'total': None, 'reason': 'overlap-too-small'}
    total = round(a * b / overlap)
    return {'total': total, 'a': a, 'b': b, 'overlap': overlap}

Покрытие вычисляется как доля собранного к оценке общего: coverage = len(собранное) / estimated_total. Это даёт ответ на вопрос «сколько ещё пропущено».

В реальном прогоне на 800 запросов оценка дала 880 вакансий, и фактическое исчерпание произошло на 880. Ранее я останавливался на 93 запросах, считая, что собрал всё.

Типичные ошибки при применении метода

Ошибка 1: разделение выборок по чётности запросов

В первой версии я делил запросы на нечётные и чётные. Оценка дала 1334 при фактических 880 — на 50% больше. Причина: смещение start увеличивается на 1 с каждым запросом, поэтому нечётные запросы попадали на нечётные страницы, чётные — на чётные. Выборки брались из разных частей пула, что занижало пересечение и завышало N. Метод предполагает, что обе выборки из одной популяции.

Исправление: разделять по проходам (sweep), когда каждый проход покрывает все смещения:

sweep = r // pages  # номер прохода
start = (r % pages) * PAGE_SIZE
if sweep % 2 == 0:
    sample_a.add(job_id)
else:
    sample_b.add(job_id)

Ошибка 2: вырождение формулы

Когда одна выборка полностью содержится в другой, формула возвращает размер большей выборки. Например, выборки 20 и 681 с пересечением 20 дают N = 20*681/20 = 681 — оценка равна уже собранному, покрытие 100%. Это ложная уверенность. Защита — проверять не только размер, но и форму выборок:

MIN_SAMPLE = 20
MIN_BALANCE = 0.5  # меньшее / большее
if min(a, b) < MIN_SAMPLE:
    return {'total': None, 'reason': 'sample-too-small'}
if min(a, b) / max(a, b) < MIN_BALANCE:
    return {'total': None, 'reason': 'samples-unbalanced'}
if overlap < 10:
    return {'total': None, 'reason': 'overlap-too-small'}

Также важно не доверять оценке, пока обе выборки не совершат хотя бы один полный проход.

Ошибка 3: лечение симптома вместо причины

Увидев вырождение, я поднял минимальный размер выборки до 50. Это сломало компании с ~25 вакансиями: они не могли дать выборку в 50 элементов. Средние компании стали неопределимыми. Настоящая причина — дисбаланс (20 против 681), а не абсолютный размер. Поэтому минимальный размер вернул к 20, а защиту обеспечивают баланс и правило двух проходов. Для маленьких компаний (когда ни одна страница не заполнена полностью) можно использовать отдельный путь: если страница не заполнена, значит, следующей нет, и данные полны.

Ошибка 4: изменение параметров между запусками

Если изменить лимит запросов или фильтр, сравнение с предыдущим запуском покажет ложные закрытия. Например, уменьшив лимит с 30 до 20, вы получите «закрытие» 10 вакансий, хотя они просто не собраны. Решение — проверять сопоставимость наблюдений перед сравнением:

if ctx.truncated:
    return blank('truncated-this-run')
if prev_point.truncated:
    return blank('previous-run-was-truncated')
if ctx.filter_key != prev_point.filter_key:
    return blank('filters-changed')

Тогда opened и closed возвращают null с причиной, а не ложные числа.

Что выводить в отчёте

Каждая строка компании должна содержать не только данные, но и метрики полноты:

{
    'open_jobs': 880,
    'estimated_total': 880,
    'coverage': 1.0,
    'estimated_missing': 0,
    'change_margin_of_error': 0,
    'collection_complete': True,
    'requests_used': 523
}

change_margin_of_error — критически важная метрика. Если в этом запуске пропущено m вакансий, а в предыдущем m', то кажущееся изменение замусорено величиной до m + m'. При покрытии 99% на 880 вакансиях пропущено около 9, поэтому изменение ±18 находится в пределах шума. Поэтому целевое покрытие для отслеживания изменений должно быть выше, чем для простого списка. Число без погрешности провоцирует необоснованные выводы.

Дополнительно: LinkedIn возвращает HTTP 400 для start ≥ 1000. В эксперименте из 800 запросов ровно 20 провалились (1000, 1010, … 1190), остальные успешны. Смещения до 1000 достаточно, так как каждый проход даёт новую выборку.

Практические выводы

1. «Нет новых результатов» — не доказательство полноты. Это информация о доле уже собранного, которую вы и пытаетесь измерить. Любой критерий остановки на этой основе цикличен.
2. Повторные запросы — это выборки, а не повторные попытки. Перестаньте сливать их в один бакет, и данные ответят на вопрос, для которого нужен был новый эксперимент.
3. Вырожденная формула возвращает число, а не ошибку. 20×681/20=681 арифметически верно, но семантически мусор. Если формула имеет режим вырождения, защищайте её форму и возвращайте «не знаю» вместо значения по умолчанию.
4. Тишина и полнота неразличимы, если не сообщать разницу. Раньше «660 вакансий» и «880 вакансий» выглядели одинаково. Теперь строка показывает, что именно собрано и насколько уверенно.

Попробуйте прямо сейчас: возьмите свой парсер, который обходит постранично, разделите запросы на две выборки по проходам и оцените общее количество по формуле Линкольна–Петерсена. Вы удивитесь, насколько часто ваши данные неполны.