Интеграция сервиса «Проверка по списку недействительных российских паспортов» или как сжать csv-файл в 38 раз21.08.2021 13:31

Постановка задачи

Имеется ежедневно обновляемый архив со списком недействительных российских паспортов в формате csv: http://сервисы.гувм.мвд.рф/info-service.htm? sid=2000. Размер архива list_of_expired_passports.csv.bz2 — 506 MB, размер распакованного csv-файла — 1,6 GB.

Требуется реализовать вспомогательный REST-сервис, для использования внутри компании, со следующими возможностями:

  • Проверка наличия паспорта (Серия + Номер) в списке недействительных паспортов.

  • Возможность обновления данных без прерывания работы сервиса.

Исследуем содержимое csv-файла

Исходный csv-файл содержит более 137 148 000 записей большинство из которых записаны в одинаковом формате ^\d{4},\d{6}$, но также встречаются и буквенные серии (~10000 записей).

PASSP_SERIES,PASSP_NUMBER
6004,270563
6004,270579
6004,270611
...
ХЕР6,37039
ХИБА,601006
ХУЕР,685239
ЯГ01,3332

Возможно ли сжать данный csv-файл, чтобы было приемлемо работать с ним в памяти?

Да! Используя то, что большинство записей представлены в числовом виде, а также что для задачи проверки наличия паспорта в списке не имеет значения в каком порядке расположены строки, данный csv-файл можно запаковать значительно лучше чем это делают популярные архиваторы. А точнее до 42 MB, что в 38 раз компактнее исходного csv-файла и в 11 раз компактнее csv-файла сжатого bzip2.

Данные в таблице на 16.08.2021.

Формат

Размер в байтах

list_of_expired_passports.csv.bz2

506,340,184

list_of_expired_passports.csv

1,649,037,938

list_of_expired_passports.csv.pdata

42,876,427

Предлагаемый алгоритм сжатия .pdata (passport data)

Хочу сразу оговориться что этот алгоритм не является универсальным и применим только в рамках данной задачи сжатия csv-файла в котором много записей паспортов представлено в числовом виде.

Возьмем для примера первую запись из csv-файла: 6004,270563.

  1. Удалим запятую между серией и номером паспорта.

  2. Далее разобьем строку на 2 части по 7 и 3 символа соответственно и представим в виде чисел: 6004270 и 563.

  3. Первое число будем хранить в формате Int32 и использовать в качестве ключа Dictionary для фильтра чисел у которых совпадают первые 7 цифр.

  4. Второе 3-значное число может принимать значения от 0 до 999. Однако нам не надо сохранять данное число целиком, достаточно знать есть ли оно в файле или нет. Поэтому все числа от 0 до 999 будем кодировать массивом из 1000 бит, что соответствует массиву из 125 байт.

Реализация алгоритма сжатия

PassportDataStorage.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace FileFormat.PassportData
{
    public class PassportDataStorage
    {
        private const int PART1_LENGTH = 7;
        private const int PART2_LENGTH = 3;
        public const int PART2_NUM_VALUES = 1000;

        private readonly IBitMatrix _numbers;
        private readonly ISet _strings;

        public PassportDataStorage()
        {
            _numbers = new BitMatrix(PART2_NUM_VALUES);
            _strings = new HashSet();
        }

        public PassportDataStorage(IBitMatrix numbers, IEnumerable strings)
        {
            _numbers = numbers;
            _strings = new HashSet(strings);
        }
        
        public string Header { get; set; }

        public ISet Strings => _strings;

        public IBitMatrix Numbers => _numbers;
        
        public void Add(string value)
        {
            if (string.IsNullOrEmpty(value))
            {
                return;
            }

            if (IsOnlyNumbers(value))
            {
                var (row, column) = SplitNumbersValue(value);
                _numbers[row, column] = true;
            }
            else
            {
                _strings.Add(value);
            }
        }

        public bool Contains(string value)
        {
            if (string.IsNullOrEmpty(value))
            {
                throw new ArgumentNullException(nameof(value));
            }

            bool result;
            if (IsOnlyNumbers(value))
            {
                var (row, column) = SplitNumbersValue(value);
                result = _numbers[row, column];
            }
            else
            {
                result = _strings.Contains(value);
            }

            return result;
        }

        private bool IsOnlyNumbers(string value)
        {
            if (value.Length == 11 && value[4] == ',')
            {
                var numbers = value.Substring(0, 4) + value.Substring(5, 6);
                return numbers.All(char.IsDigit);
            }

            return false;
        }

        private (int, int) SplitNumbersValue(string value)
        {
            var onlyNumbers = value.Substring(0, 4) + value.Substring(5, 6);
            var part1 = onlyNumbers.Substring(0, PART1_LENGTH);
            var part2 = onlyNumbers.Substring(PART1_LENGTH, PART2_LENGTH);
            return (int.Parse(part1), int.Parse(part2));
        }
    }
}

protobuf-описание формата файла .pdata (passportdata.proto)

syntax = "proto3";

message PassportDataMessage
{
    string csv_header = 1;
    repeated NumbersMap numbers_only_map = 2;
    repeated string other_lines = 3;
}

message NumbersMap
{
    int32 seven_digits_key = 1;
    bytes three_digits_bits_value = 2;
}

Ссылки

© Habrahabr.ru