К-свёртка

Понятие к-свёртки

Рассмотрим множества не повторяющихся натуральных чисел. Причем чаще всего элементы этих множеств следуют друг за другом, то есть если a1,a2,a3 из A, то часто a2=a1+1, a3=a2+1 ... Для оптимизации хранения данной информации можно использовать к-свёртку.

К-свёртка представляет собой последовательность байт, кратную 4. Блоки из четырёх байт записаны в прямом порядке (от младшего к старшему), классифицируются на 3 вида по значению первых двух бит старшего байта следующим образом:

  • 10 - блок A типа
  • 00 - блок B типа
  • 01 - блок C типа
Порядок нумерации бит в блоке:
              ...      89ABCDEF 01234567
    +--------+--------+--------+--------+
    |   3    |   2    |   1    |   0    |
    +--------+--------+--------+--------+
Пример:
    в файле: 0x00 0x22 0x63 0x80
    число  : 0x806F2200
    в bin  : 10000000 01101111 00100010 00000000

В к-свёртке каждое натуральное число N представлено парой чисел A и B в виде N = 30*A + B, где

if(N%30 == 0)
        A = N/30 - 1
        B = 30
else
        A = N/30
        B = N%30

При этом натуральное A будем называть индексом, а натуральное B <=30 остатком. Остаток B представляется в памяти числом (1 << 32) + (1 << (30 - B)) (см. таблицу)

Пример представления остатка
b     двоичное представление                  запись в файле
1     10100000 00000000 00000000 00000000     0x00 0x00 0x00 0xA0
2     10010000 00000000 00000000 00000000     0x00 0x00 0x00 0x90
3     10001000 00000000 00000000 00000000     0x00 0x00 0x00 0x88
4     10000100 00000000 00000000 00000000     0x00 0x00 0x00 0x84
...
29    10000000 00000000 00000000 00000010     0x00 0x20 0x00 0x80
30    10000000 00000000 00000000 00000001     0x00 0x10 0x00 0x80

Несколько натуральных чисел группируются по индексу. Если индексы двух натуральных чисел совпадают, их остатки суммируются. Затем пары (индекс, сумма остатков) записываются в порядке увеличения индекса. Сумма остатков не что иное как блок типа A. Индексы преобразуются в блоки типа B путем вычитания из каждого следующего индекса текущего (то есть остается только разница между индексами). Если разница равна 1, то такой индекс не записывается. Если сумма остатков равна (1 << 32) + 0x0x3ffffffff (единицы заполнены полностью), то не имеет смысла хранить сумму остатков. В таком случае, вместо суммы остатков хранят блок вида (1 << 31) + K, где К - количество таких блоков, идущих друг за другом.

Пример создания к-свёртки из последовательности

Свернём следующую последовательность из 97 элементов: 61, 65, 90, 91, 92, 93, ...,154, 156, 157, ..., 184, 193

N1  = 61,  N1  = 30*2 + 1,  (2, 1)
N2  = 65,  N2  = 30*2 + 5,  (2, 5)
N3  = 90,  N3  = 30*2 + 30  (2, 30)
N4  = 91,  N4  = 30*3 + 1   (3, 1)
N5  = 92,  N5  = 30*3 + 2   (3, 2)
...                           ,
N33 = 120, N33 = 30*3 + 30  (3, 30)
N34 = 121, N34 = 30*4 + 1   (4, 1)
N35 = 122, N35 = 30*4 + 2   (4, 2)
...                           ,
N63 = 150, N63 = 30*4 + 30  (4, 30)
N64 = 151, N64 = 30*5 + 1   (5, 1)
N65 = 152, N65 = 30*5 + 2   (5, 2)
N66 = 153, N66 = 30*5 + 3   (5, 3)
N67 = 154, N67 = 30*5 + 4   (5, 4)
N68 = 156, N68 = 30*5 + 6   (5, 6)
N69 = 157, N69 = 30*5 + 7   (5, 7)
...
N96 = 184, N96 = 30*6 + 4   (6, 4)
N97 = 193, N97 = 30*6 + 13  (6, 13)

Группируем:

(2, {1, 5, 30})
(3, {1, 2, ..., 30})
(4, {1, 2, ..., 30})
(5, {1, 2, 3, 4, 6, 7, ..., 30})
(6, {1, 2, 3, 4, 13})

В парах с индексами 3 и 4 присутствуют все остатки от 1 до 30, поэтому их можно представить блоком типа C: 0x3fffff + 2. Индексы, начиная со 2 идут друг за другом, поэтому можно их не записывать. Таким образом свёртка записывается в следующем виде:

1. Индекс 2
2. Сумма остатков 1, 5, 30
3. C-блок 0x3fffff + 2
4. Сумма остатков 1, 2, 3, 4, 6, 7, ..., 30
5. Сумма остатков 1, 2, 3, 4, 13

В бинарной системе счисления (группировка по 4 байта)

1. 00000000 00000000 00000000 00000010
2. 10100010 00000000 00000000 00000001
3. 01000000 00000000 00000000 00000010
4. 10111101 11111111 11111111 11111111
5. 10111100 00000010 00000000 00000000

В шестнадцатеричной:

1. 0x00 0x00 0x00 0x02
2. 0xA2 0x00 0x00 0x01
3. 0x40 0x00 0x00 0x02
4. 0xBD 0xFF 0xFF 0xFF
5. 0xBC 0x02 0x00 0x00

Итого, дамп памяти в прямом порядке байт данной свёртки будет выглядеть так:

00000000 02 00 00 00 01 00 00 A2 02 00 00 40
00000010 FF FF FF BD 00 00 02 BC

Операции с к-свёрткой

  1. Добавить элемент
  2. Удалить элемент
  3. Изменить элемент
  4. Проверить наличие элемента
  5. Раскрыть в последовательность
  6. Свернуть последовательность в к-свёртку

Пример раскрытия к-свёртки в последовательность

Блоки типа A и C в свёртке имеют определенные индексы. Индексы следуют по порядку. Блоки типа B и C увеличивают значение индекса не на единицу, а на число, записанное в этом блоке (не считая биты, определяющие тип блока).

Пример нумерации блоков в свёртке:

        A               B               A               A               C
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|x00 x1F x03 x80|x02 x00 x00 x00|x00 x02 x00 xB8|x10 xD3 xA1 x80|x03 x00 x00 x40|
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
i=0             ==>             i=i+2=2         i=i+1=3         i=i+3=6

Раскроем к-свёртку

00000000 01 00 00 00 FF FF F7 86 00 00 00 BE

Разбиваем на блоки:

01 00 00 00 | FF FF F7 86 | 00 00 00 BE
     B             A             A

Блоки типа A и их индексы:

в файле       соотв. двоичное число                   индекс
FF FF F7 86   10000110 11110111 11111111 11111111     1
00 00 00 BE   10111110 00000000 00000000 00000000     2

Остатки FF FF F7 86:

10000100 00000000 00000000 00000000   4
10000010 00000000 00000000 00000000   5
10000000 10000000 00000000 00000000   7
10000000 10000000 00000000 00000000   8
...
10000000 00010000 00000000 00000000   10
10000000 00000100 00000000 00000000   12
10000000 00000010 00000000 00000000   13
...
10000000 00000000 00000000 00000001   30

Остатки 00 00 00 BE:

10100000 00000000 00000000 00000000   1
10010000 00000000 00000000 00000000   2
10001000 00000000 00000000 00000000   3
10000100 00000000 00000000 00000000   4
10000010 00000000 00000000 00000000   5

Соответствующая последовательность:

1*30 + 4  = 34
1*30 + 5  = 35
1*30 + 7  = 37
1*30 + 8  = 38
...
1*30 + 10 = 40
1*30 + 12 = 42
1*30 + 13 = 43
...
1*30 + 30 = 60
2*30 + 1  = 61
2*30 + 2  = 62

Проверка наличия элемента в свёртке

Проверка наличия системного номера в свёртке - простая операция. Для удобства свёртку можно хранить в виде множества пар (индекс, блок типа A). Необходимо преобразовать системный номер к виду sysnum = (a, b), где sysnum = 30a + b, то есть взять целую часть от деления на 30 и остаток. Целая часть определит пару (индекс, блок A) свёртки, "побитовое и" остатка с соответствующим блоком типа A даст ответ принадлежит ли данный системный номер свёртке.

Comments

comments powered by Disqus