C Библиотека для сжатия последовательных положительных целых чисел

У вас есть два конфликтующих требования:

1. Вы хотите сжимать очень маленькие элементы (по 8 байтов каждый).
2. Вам необходим эффективный произвольный доступ для каждого элемента.

Второе требование, скорее всего, наложит фиксированную длину для каждого элемента.

Вы пропустили критическая информация о количестве строк, которые вы собираетесь проиндексировать.

Но учитывая, что вы говорите, что ожидаете, что минимальная длина индексированной строки будет 256, сохранение индексов как 64% приводит к при большая часть 3% накладных расходов. Если общая длина строкового файла меньше 4 ГБ, вы можете использовать 32-битные индексы и понести 1,5% накладных расходов. Эти числа подсказывают мне, что если сжатие имеет значение, лучше сжимать строки, а не индексы . Для этой проблемы подходит вариант LZ77.

Если вы хотите попробовать безумную идею, поместите каждую строку в отдельный файл, поместите их все в zip-файл и посмотрите, как вы можете справиться с zziplib . Это, вероятно, будет не очень хорошо, но с вашей стороны это почти ноль.

Приветствуются дополнительные данные по проблеме:

• Количество строк
• Средняя длина строки
• Максимальная длина строки строка
• Средняя длина строк
• Степень сжатия файла строк с помощью gzip
• Разрешено ли вам изменять порядок строк для улучшения сжатия

РЕДАКТИРОВАТЬ

Комментарий и исправленные вопрос делает проблему намного яснее. Мне нравится ваша идея группировки, и я бы попробовал простую дельта-кодировку, сгруппировал бы дельты и использовал код переменной длины в каждой группе. Я бы не стал указывать 64 как размер группы - я думаю, вы, вероятно, захотите определить это эмпирически.

Вы запросили существующие библиотеки. Что касается группировки и дельта-кодирования, я сомневаюсь, что вы найдете много. Что касается целочисленных кодов переменной длины, я не вижу особого подхода к библиотекам C, но вы можете найти кодировки переменной длины в Perl и Python . На эту тему есть масса статей и несколько патентов, и я подозреваю, что вам придется создавать собственные. Но есть несколько простых кодов, и вы можете попробовать UTF-8 - он может кодировать целые числа без знака до 32 бит, и вы можете взять код C из Plan 9 , и я уверен, что многие другие источники.

Что именно вы пытаетесь сжать? Если вы думаете об общем пространстве индекса, действительно ли стоит экономить место?

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

Для быстрого поиска индексы будут реализованы с использованием чего-то вроде B + Tree .

Вы работаете в Windows? Если это так, я рекомендую создать файл mmap, используя наивное решение, предложенное вами изначально, а затем сжать файл с помощью сжатия NTLM . Код вашего приложения никогда не знает, что файл сжат, и ОС выполняет сжатие файла за вас. Возможно, вы не думаете, что это будет очень производительным или хорошим сжатием, но я думаю, вы будете удивлены, если попробуете это.

Мы можем сделать это, получив ScrollViewer , который присутствует в ControlTemplate ListView. Если у вас есть доступ к ScrollViewer, то есть много различных методов прокрутки.

Во-первых, мы можем создать ListView, к которому мы хотим добавить этот эффект:

<ListView ItemsSource="{Binding Percents}"
      SelectionChanged="OnSelectionChanged"
      x:Name="uiListView"/>

public List<int> Percents { get; set; }

public Window1()
{
    InitializeComponent();

    Percents = new List<int>();
    for (int i = 1; i <= 100; i++)
    {
        Percents.Add(i);
    }
    this.DataContext = this;
}

Нам также понадобится то, что мы можем использовать для получения ScrollViewer из ListView. Раньше я использовал нечто подобное для работы с настраиваемой прокруткой, и мы можем использовать это и здесь.

public static DependencyObject GetScrollViewer(DependencyObject o)
{
    if (o is ScrollViewer)
    { return o; }

    for (int i = 0; i < VisualTreeHelper.GetChildrenCount(o); i++)
    {
        var child = VisualTreeHelper.GetChild(o, i);

        var result = GetScrollViewer(child);
        if (result == null)
        {
            continue;
        }
        else
        {
            return result;
        }
    }

    return null;
}

Теперь нам просто нужно обработать событие SelectionChanged. Поскольку мы пытаемся прокрутить элемент в начало списка, лучший вариант - прокрутить вниз, а затем повторно прокрутить вверх до выбранного элемента. Как вы сказали, ScrollIntoView будет прокручиваться до тех пор, пока элемент не станет видимым, помощники, от первого лица их использования в ваших собственных приложениях, это факт что только ОДИН помощник класса для данного class может быть в области видимости в любое время ". ... "То есть, если у вас есть два помощника по объему будет признан только ОДИН компилятором. Вы не получите ничего предупреждения или даже намеки на любые другие поэтому номер записи часто вообще не нужно было повторять. А дельта смещения слова часто умещается в пределах одного или двух байтов. Вот код, который я использовал.

Поскольку он написан на C ++, код может быть бесполезен для вас как есть, но может быть хорошей отправной точкой для написания подпрограмм сжатия.

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

IndexCompressor.h

//
// index compressor class
//

#pragma once

#include "File.h"

const int IC_BUFFER_SIZE = 8192;

//
// index compressor
//
class IndexCompressor
{
private :
   File        *m_pFile;
   WA_DWORD    m_dwRecNo;
   WA_DWORD    m_dwWordNo;
   WA_DWORD    m_dwRecordCount;
   WA_DWORD    m_dwHitCount;

   WA_BYTE     m_byBuffer[IC_BUFFER_SIZE];
   WA_DWORD    m_dwBytes;

   bool        m_bDebugDump;

   void FlushBuffer(void);

public :
   IndexCompressor(void) { m_pFile = 0; m_bDebugDump = false; }
   ~IndexCompressor(void) {}

   void Attach(File& File) { m_pFile = &File; }

   void Begin(void);
   void Add(WA_DWORD dwRecNo, WA_DWORD dwWordNo);
   void End(void);

   WA_DWORD GetRecordCount(void) { return m_dwRecordCount; }
   WA_DWORD GetHitCount(void) { return m_dwHitCount; }

   void DebugDump(void) { m_bDebugDump = true; }
};

IndexCompressor.cpp

//
// index compressor class
//

#include "stdafx.h"
#include "IndexCompressor.h"

void IndexCompressor::FlushBuffer(void)
{
   ASSERT(m_pFile != 0);

   if (m_dwBytes > 0)
   {
      m_pFile->Write(m_byBuffer, m_dwBytes);
      m_dwBytes = 0;
   }
}

void IndexCompressor::Begin(void)
{
   ASSERT(m_pFile != 0);
   m_dwRecNo = m_dwWordNo = m_dwRecordCount = m_dwHitCount = 0;
   m_dwBytes = 0;
}

void IndexCompressor::Add(WA_DWORD dwRecNo, WA_DWORD dwWordNo)
{
   ASSERT(m_pFile != 0);
   WA_BYTE buffer[16];
   int nbytes = 1;

   ASSERT(dwRecNo >= m_dwRecNo);

   if (dwRecNo != m_dwRecNo)
      m_dwWordNo = 0;
   if (m_dwRecordCount == 0 || dwRecNo != m_dwRecNo)
      ++m_dwRecordCount;
   ++m_dwHitCount;

   WA_DWORD dwRecNoDelta = dwRecNo - m_dwRecNo;
   WA_DWORD dwWordNoDelta = dwWordNo - m_dwWordNo;

   if (m_bDebugDump)
   {
      TRACE("%8X[%8X] %8X[%8X] : ", dwRecNo, dwRecNoDelta, dwWordNo, dwWordNoDelta);
   }

   // 1WWWWWWW
   if (dwRecNoDelta == 0 && dwWordNoDelta < 128)
   {
      buffer[0] = 0x80 | WA_BYTE(dwWordNoDelta);
   }
   // 01WWWWWW WWWWWWWW
   else if (dwRecNoDelta == 0 && dwWordNoDelta < 16384)
   {
      buffer[0] = 0x40 | WA_BYTE(dwWordNoDelta >> 8);
      buffer[1] = WA_BYTE(dwWordNoDelta & 0x00ff);
      nbytes += sizeof(WA_BYTE);
   }
   // 001RRRRR WWWWWWWW WWWWWWWW
   else if (dwRecNoDelta < 32 && dwWordNoDelta < 65536)
   {
      buffer[0] = 0x20 | WA_BYTE(dwRecNoDelta);
      WA_WORD *p = (WA_WORD *) (buffer+1);
      *p = WA_WORD(dwWordNoDelta);
      nbytes += sizeof(WA_WORD);
   }
   else
   {
      // 0001rrww
      buffer[0] = 0x10;

      // encode recno
      if (dwRecNoDelta < 256)
      {
         buffer[nbytes] = WA_BYTE(dwRecNoDelta);
         nbytes += sizeof(WA_BYTE);
      }
      else if (dwRecNoDelta < 65536)
      {
         buffer[0] |= 0x04;
         WA_WORD *p = (WA_WORD *) (buffer+nbytes);
         *p = WA_WORD(dwRecNoDelta);
         nbytes += sizeof(WA_WORD);
      }
      else
      {
         buffer[0] |= 0x08;
         WA_DWORD *p = (WA_DWORD *) (buffer+nbytes);
         *p = dwRecNoDelta;
         nbytes += sizeof(WA_DWORD);
      }

      // encode wordno
      if (dwWordNoDelta < 256)
      {
         buffer[nbytes] = WA_BYTE(dwWordNoDelta);
         nbytes += sizeof(WA_BYTE);
      }
      else if (dwWordNoDelta < 65536)
      {
         buffer[0] |= 0x01;
         WA_WORD *p = (WA_WORD *) (buffer+nbytes);
         *p = WA_WORD(dwWordNoDelta);
         nbytes += sizeof(WA_WORD);
      }
      else
      {
         buffer[0] |= 0x02;
         WA_DWORD *p = (WA_DWORD *) (buffer+nbytes);
         *p = dwWordNoDelta;
         nbytes += sizeof(WA_DWORD);
      }
   }

   // update current setting
   m_dwRecNo = dwRecNo;
   m_dwWordNo = dwWordNo;

   // add compressed data to buffer
   ASSERT(buffer[0] != 0);
   ASSERT(nbytes > 0 && nbytes < 10);
   if (m_dwBytes + nbytes > IC_BUFFER_SIZE)
      FlushBuffer();
   CopyMemory(m_byBuffer + m_dwBytes, buffer, nbytes);
   m_dwBytes += nbytes;

   if (m_bDebugDump)
   {
      for (int i = 0; i < nbytes; ++i)
         TRACE("%02X ", buffer[i]);
      TRACE("\n");
   }
}

void IndexCompressor::End(void)
{
   FlushBuffer();
   m_pFile->Write(WA_BYTE(0));
}