Использование контекстного кодирования Хаффмана в задаче сжатия векторов высокой размерности

В работе рассматривается задача сжатия векторов высокой размерности на примере дескрипторов изображений SIFT из датасета SIFT1M, а также глубоких нейросетевых дескрипторов из датасета DEEP1B. Классическим решением данной задачи является применение алгоритма Product Quantization (PQ) к исходному множеству векторов для получения нового множества целочисленных векторов с фиксированным и задаваемым в качестве параметра алгоритма коэффициентом сжатия. Алгоритм Product Quantization является алгоритмом сжатия с потерями, причём потери неизвестны до применения алгоритма. В существующих модификациях алгоритма PQ, таких как Optimized Product Quantization (OPQ), или Additive Quantization (AQ) оптимизируется ошибка кодирования, при том же коэффициенте сжатия, что и в исходном алгоритме. В данной работе предлагается применить к выходу Product Quantization биграммное Хаффмановское кодирование, чтобы оптимизировать коэффициент сжатия, при фиксированной ошибке кодирования, вносимой Product Quantization. В работе разработаны два метода сжатия, основанные на построении минимального остовного дерева, а также на лексикографической сортировке кодированных при помощи Product Quantization векторов. Оба метода дают различную степень сжатия на различных параметрах запуска и датасетах, от 5.6 до 1.4 бита на каждый байт выходного объёма Product Quantization, однако требуют дополнительных вычислительных мощностей, а также значительных объёмов оперативной памяти как для кодирования, так и для декодирования. Кроме того, оба метода вводят переменный размер элементов датасета, что лишает возможности произвольного доступа к векторам, а также фиксируют структуру хранения векторов в датасете. Тем не менее, предложенный алгоритм может быть использован в задачах сжатия векторов, где применим алгоритм Product Quantization, а указанные дополнительные ограничения не играют большой роли.