Многоиндексный поиск¶

При сверке реестра с архивом документов необходимо для каждой строки реестра найти документы с совпадающими значениями полей. Полный перебор всех документов для каждой строки слишком медленный при больших объёмах данных (тысячи строк × тысячи документов). Многоиндексный поиск решает эту задачу за счёт предварительного построения указателей.

Реализация распределена между модулями registry_search.py и matching.py. Подробное описание функций приведено в разделах Импорт и поиск по реестру и Сопоставление с реестром.

Общая идея¶

Перед началом поиска программа загружает все документы из базы данных и строит два указателя:

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

Поиск по обратному указателю выполняется за постоянное время O(1), в отличие от полного перебора O(N).

Построение прямого указателя¶

Метод _build_document_index загружает документы и для каждого формирует запись вида:

идентификатор документа → {
    "from_content.contract_number" → ("08V-0801", "080801", "number"),
    "from_content.contract_date"   → ("01.07.2008", "2008-07-01", "date"),
    "from_content.contractor"      → ("ООО \"Компания\"", "ооо компания", "text")
}

Каждое поле хранится в тройке: исходное значение, нормализованное значение и тип поля. Тип определяется автоматически по имени пути:

Имя содержит	Тип поля
`number`, `act_number`, `buh_number`	Номер
`date`	Дата
`amount`	Сумма
Все остальные	Текст

Нормализация зависит от типа: для номеров --- извлечение цифр, для дат --- приведение к ГГГГ-ММ-ДД, для сумм --- приведение к числу, для текста --- нижний регистр и удаление знаков препинания.

Построение обратного указателя¶

Метод _build_reverse_index проходит по прямому указателю и для каждого нормализованного значения создаёт обратную запись:

"from_content.contract_number" → {
    "080801" → {doc_id_1, doc_id_7, doc_id_15},
    "12345"  → {doc_id_3},
    ...
}

Индексирование дат с несколькими толкованиями¶

Для полей типа «дата» в обратный указатель записываются все возможные нормализации (см. Сравнение неоднозначных дат). Например, если документ содержит дату 03/05/2023, в указатель попадают две записи:

"from_content.contract_date" → {
    "2023-05-03" → {doc_id_1, ...},
    "2023-03-05" → {doc_id_1, ...}
}

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

Индексирование сумм¶

Для полей типа «сумма» значение округляется до двух знаков после запятой и записывается как строка. При диапазонном поиске программа не может заранее внести все возможные значения в указатель, поэтому диапазон проверяется на этапе подсчёта баллов.

Двухфазный поиск¶

Для каждой строки реестра поиск выполняется в две фазы.

Фаза 1: отбор кандидатов через обратный указатель¶

Метод _find_candidates использует обратный указатель для быстрого отбора документов. Для каждого поля правила сопоставления применяется своя стратегия:

Тип поля	Способ сравнения	Стратегия отбора
Номер	Точный	Точное совпадение нормализованных цифр. Если не найдено --- поиск подстроки (номер реестра содержится в номере документа или наоборот)
Дата	Точный	Все толкования даты ищутся в указателе
Дата	Диапазонный	Все толкования ± допуск в днях
Сумма	Точный	Точное совпадение округлённой суммы
Сумма	Диапазонный	Все суммы в пределах указанного процента
Текст	Точный	Точное совпадение нормализованного текста
Текст	Вхождение	Поиск подстроки в обоих направлениях
Текст	Приблизительный	Обратный указатель не используется --- требуется полный перебор

Если среди полей правила есть хотя бы одно индексируемое, но кандидатов не найдено --- строка считается без совпадений. Если все поля приблизительные --- проверяются все документы (это самый медленный случай).

Фаза 2: подсчёт баллов¶

Для каждого документа-кандидата вычисляется балл по каждому полю, а затем --- взвешенная сумма (подробнее --- в разделе Система баллов). Если сумма достигает минимального порога правила, документ считается совпавшим.

Оптимизации¶

Ранний выход¶

Если по точному указателю уже найдено достаточно совпадений (10 документов на строку), приблизительный поиск пропускается.

Ограничение кандидатов для нечёткого поиска¶

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

Пакетная обработка строк¶

Строки реестра обрабатываются порциями по 100 штук. После каждой порции результаты записываются в базу данных операцией массовой записи (bulk_write). Это снижает количество обращений к базе и ускоряет запись.

Кэширование документов¶

Документы загружаются из базы один раз перед началом поиска. Указатели строятся тоже один раз. Повторная загрузка не требуется, пока реестр не изменился.

Где используется¶

Поиск по реестру (registry_search.py) --- основной потребитель. Оба указателя строятся в начале поиска и используются для всех строк реестра.
Сопоставление с реестром (matching.py) --- использует аналогичную структуру указателей для синхронного поиска, вызываемого из интерфейса.
Фоновая задача Celery (tasks.py) --- дублирует логику построения указателей для автономного выполнения в фоновом процессе.