Как эффективно хранить матрицу с сильно избыточными значениями

Question

У меня очень большая матрица (100M строк на 100M столбцов), в которой много повторяющихся значений рядом друг с другом.Например:

8 8 8 8 8 8 8 8 8 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 4 8 8 1 1 1 1 1 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 3 3 3 3 3 3 3 3 3 3 3

Я хочу, чтобы структура данных / алгоритм хранили такие матрицы как можно более компактно.Например, вышеприведенная матрица должна занимать только пространство O (1) (даже если матрица была растянута произвольно большой), потому что существует только постоянное количество прямоугольных областей, где каждая область имеет только одно значение.

Повторение происходит как по строкам, так и по столбцам вниз, поэтому простой подход сжатия матрицы строка за строкой недостаточно хорош.(Для этого потребуется минимум O (num_rows) места для хранения любой матрицы.)

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

Answer 1

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

Answer 2

Теперь для моего предпочтительного метода.

Хорошо, как я уже упоминал в предыдущих ответах, строки с одинаковыми записями в каждом столбце в матрице A умножатся на один и тот же результат в матрице AB.Если мы сможем сохранить эту взаимосвязь, то теоретически мы сможем значительно ускорить вычисления (профилировщик - ваш друг).

В этом методе мы поддерживаем структуру строки * столбца матрицы.

Каждая строкасжимается любым способом, который может распаковать достаточно быстро, чтобы не слишком сильно влиять на скорость умножения.RLE может быть достаточно.

Теперь у нас есть список сжатых строк.

Мы используем метод энтропийного кодирования (например, Шеннона-Фано, Хаффмана или арифметическое кодирование), но мы не сжимаемданные в строках с этим, мы используем его для сжатия набора строк.Мы используем его для кодирования относительной частоты строк.Т.е. мы обрабатываем строку так же, как стандартное энтропийное кодирование будет обрабатывать символ / байт.

В этом примере RLE сжимает a строку, а Хаффман сжимает весь set строк.

Так, например, учитывая следующую матрицу (с префиксом номеров строк, Хаффман использовал для простоты объяснения)

0 | 8 8 8 8 8 8 8 8 8 8 8 8 8 |
1 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
2 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
3 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
4 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
5 | 8 4 8 8 1 1 1 1 1 8 8 8 8 |
6 | 8 8 8 8 8 8 8 8 8 8 8 8 8 |
7 | 8 8 3 3 3 3 3 3 3 3 3 3 3 |

Длина серии в кодировке

0 | 8{13}                    |
1 | 8{1} 4{1} 8{2} 1{5} 8{4} |
2 | 8{1} 4{1} 8{2} 1{5} 8{4} |
3 | 8{1} 4{1} 8{2} 1{5} 8{4} |
4 | 8{1} 4{1} 8{2} 1{5} 8{4} |
5 | 8{1} 4{1} 8{2} 1{5} 8{4} |
6 | 8{13}                    |
7 | 8{2} 3{11}               |

Итак, 0 и 6 появляются дважды, а 1 - 5 появляются 5 раз.7. только один раз.

Таблица частот

A: 5 (1-5) | 8{1} 4{1} 8{2} 1{5} 8{4} |
B: 2 (0,6) | 8{13}                    |
C: 1    7  | 8{2} 3{11}               |

Дерево Хаффмана

    0|1
   /   \
  A    0|1
      /   \
     B     C

Таким образом, в этом случае требуется один бит (для каждой строки) для кодирования строк 1 -5 и 2 бита для кодирования строк 0, 6 и 7.

(Если количество циклов превышает несколько байтов, то подсчет freq для хэша, который вы создаете при выполнении RLE).

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

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

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

Просмотр строк в A с тем же столбцомзаписи умножаются на один и тот же результат в AB по вектору B, вы можете кэшировать результат и использовать его вместо его повторного вычисления (всегда полезно избегать умножений 100M * 100M, если можете).

Ссылки на дополнительную информацию:

Арифметическое кодирование + Статистическое моделирование = Сжатие данных

Приоритетные очереди и STL

Арифметическое кодирование

Код Хаффмана

Сравнение

Несжатый

    0   1   2   3   4   5   6   7
  =================================
0 | 3   3   3   3   3   3   3   3 |
  |-------+               +-------|
1 | 4   4 | 3   3   3   3 | 4   4 |
  |       +-----------+---+       |
2 | 4   4 | 5   5   5 | 1 | 4   4 |
  |       |           |   |       |
3 | 4   4 | 5   5   5 | 1 | 4   4 |
  |---+---|           |   |       |
4 | 5 | 0 | 5   5   5 | 1 | 4   4 |
  |   |   +---+-------+---+-------|
5 | 5 | 0   0 | 2   2   2   2   2 |
  |   |       |                   |
6 | 5 | 0   0 | 2   2   2   2   2 |
  |   |       +-------------------|
7 | 5 | 0   0   0   0   0   0   0 |
  =================================

= 64 байта

Quadtree

    0   1   2   3   4   5   6   7
  =================================
0 | 3 | 3 |       |       | 3 | 3 |
  |---+---|   3   |   3   |---+---|
1 | 4 | 4 |       |       | 4 | 4 |
  |-------+-------|-------+-------|
2 |       |       | 5 | 1 |       |
  |   4   |   5   |---+---|   4   |
3 |       |       | 5 | 1 |       |
  |---------------+---------------|
4 | 5 | 0 | 5 | 5 | 5 | 1 | 4 | 4 |
  |---+---|---+---|---+---|---+---|
5 | 5 | 0 | 0 | 2 | 2 | 2 | 2 | 2 |
  |-------+-------|-------+-------|
6 | 5 | 0 | 0 | 2 | 2 | 2 | 2 | 2 |
  |---+---+---+---|---+---+---+---|
7 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  =================================

0 +- 0 +- 0 -> 3
  |    +- 1 -> 3
  |    +- 2 -> 4
  |    +- 3 -> 4
  +- 1      -> 3
  +- 2      -> 4
  +- 3      -> 5
1 +- 0      -> 3
  +- 1 +- 0 -> 3
  |    +- 1 -> 3
  |    +- 2 -> 4
  |    +- 3 -> 4
  +- 2 +- 0 -> 5
  |    +- 1 -> 1
  |    +- 2 -> 5
  |    +- 3 -> 1
  +- 3      -> 4
2 +- 0 +- 0 -> 5
  |    +- 1 -> 0
  |    +- 2 -> 5
  |    +- 3 -> 0
  +- 1 +- 0 -> 5
  |    +- 1 -> 5
  |    +- 2 -> 0
  |    +- 3 -> 2
  +- 2 +- 0 -> 5
  |    +- 1 -> 0
  |    +- 2 -> 5
  |    +- 3 -> 0
  +- 3 +- 0 -> 0
       +- 1 -> 2
       +- 2 -> 0
       +- 3 -> 0
3 +- 0 +- 0 -> 5
  |    +- 1 -> 1
  |    +- 2 -> 2
  |    +- 3 -> 2
  +- 1 +- 0 -> 4
  |    +- 1 -> 4
  |    +- 2 -> 2
  |    +- 3 -> 2
  +- 2 +- 0 -> 2
  |    +- 1 -> 2
  |    +- 2 -> 0
  |    +- 3 -> 0
  +- 3 +- 0 -> 2
       +- 1 -> 2
       +- 2 -> 0
       +- 3 -> 0

((1*4) + 3) + ((2*4) + 2) + (4 * 8) = 49 leaf nodes 
49 * (2 + 1) = 147 (2 * 8 bit indexer, 1 byte data)
+ 14 inner nodes -> 2 * 14 bytes (2 * 8 bit indexers)
= 175 Bytes

Хэш области

    0   1   2   3   4   5   6   7
  =================================
0 | 3   3   3   3   3   3   3   3 |
  |-------+---------------+-------|
1 | 4   4 | 3   3   3   3 | 4   4 |
  |       +-----------+---+       |
2 | 4   4 | 5   5   5 | 1 | 4   4 |
  |       |           |   |       |
3 | 4   4 | 5   5   5 | 1 | 4   4 |
  |---+---|           |   |       |
4 | 5 | 0 | 5   5   5 | 1 | 4   4 |
  |   + - +---+-------+---+-------|
5 | 5 | 0   0 | 2   2   2   2   2 |
  |   |       |                   |
6 | 5 | 0   0 | 2   2   2   2   2 |
  |   +-------+-------------------|
7 | 5 | 0   0   0   0   0   0   0 |
  =================================

0: (4,1; 4,1), (5,1; 6,2), (7,1; 7,7)         | 3
1: (2,5; 4,5)                                 | 1
2: (5,3; 6,7)                                 | 1
3: (0,0; 0,7), (1,2; 1,5)                     | 2
4: (1,0; 3,1), (1,6; 4,7)                     | 2
5: (2,2; 4,4), (4,0; 7,0)                     | 2

Регионы: (3 + 1 +1 + 2 + 2 + 2) * 5 = 55 байт {4-байтовый прямоугольник, 1-байтовые данные)

{Таблица поиска является отсортированным массивом, поэтому она нетребуется дополнительное хранилище}.

RLE в кодировке Хаффмана

0   | 3 {8}                                 | 1
1   | 4 {2} | 3 {4} | 4 {2}                 | 2
2,3 | 4 {2} | 5 {3} | 1 {1} | 4 {2}         | 4
4   | 5 {1} | 0 {1} | 5 {3} | 1 {1} | 4 {2} | 5
5,6 | 5 {1} | 0 {2} | 2 {5}                 | 3
7   | 5 {1} | 0 {7}                         | 2


RLE Data:    (1 + 3+ 4 + 5 + 3 + 2) * 2 = 36
Bit Stream:   20 bits packed into 3 bytes = 3
Huffman Tree: 10 nodes * 3 = 30
= 69 Bytes

Один поток RIG Giant

3{8};4{2};3{4};4{4};5{3};1{1};4{4};5{3};1{1};4{2};5{1};0{1};
5{3};1{1};4{2};5{1};0{2};2{5};5{1};0{2};2{5};5{1};0{7}

= 2 * 23 = 46 Bytes

Один поток Giant RLE, закодированный с общим префиксом свертывания

3{8};
4{2};3{4};
4{4};5{3};1{1};
4{4};5{3};
1{1};4{2};5{1};0{1};5{3};
1{1};4{2};5{1};0{2};2{5};
5{1};0{2};2{5};
5{1};0{7}

0 + 0 -> 3{8};4{2};3{4};
  + 1 -> 4{4};5{3};1{1};

1 + 0 -> 4{2};5{1} + 0 -> 0{1};5{3};1{1};
  |                + 1 -> 0{2}
  |
  + 1 -> 2{5};5{1} + 0 -> 0{2};
                   + 1 -> 0{7}

3{8};4{2};3{4}           | 00
4{4};5{3};1{1}           | 01
4{4};5{3};1{1}           | 01
4{2};5{1};0{1};5{3};1{1} | 100
4{2};5{1};0{2}           | 101
2{5};5{1};0{2}           | 110
2{5};5{1};0{7}           | 111

Bit stream: 000101100101110111
RLE Data:  16 * 2 = 32
Tree:   : 5 * 2 = 10 
Bit stream: 18 bits in 3 bytes = 3
= 45 bytes

Answer 3

Если ваши данные действительно обычные, вам может быть полезно хранить их в структурированном формате; например ваш пример матрицы может быть сохранен как следующий список инструкций "fill-rectangle":

(0,0)-(13,7) = 8
(4,1)-(8,5)  = 1

(Затем, чтобы посмотреть значение конкретной ячейки, вы должны были бы перебирать список по списку, пока не найдете прямоугольник, содержащий эту ячейку)

Answer 4

Как предположил Ира Бакстер, вы можете хранить матрицу в виде дерева квадрантов с листьями, содержащими единичные значения.

Самый простой способ сделать это, чтобы каждый узел дерева дерева покрывал область 2 ^ nx 2^ n, и каждый неконечный узел указывает на своих 4 потомков размером 2 ^ (n-1) x 2 ^ (n-1).

Вы можете получить немного лучшее сжатие с адаптивным квадродеревом, которое позволяетнерегулярное подразделение.Затем каждый неконечный узел сохраняет точку среза (B, G) и указывает на своих 4 дочерних узлов.Например, если какой-то нестворительный узел покрывает область от (A, F) в верхнем левом углу до (C, H) в нижнем правом углу, то его 4 дочерние области охвата (A, F) до (B-1, G-1) (A, G) - (B-1, H) (B, F) - (C, G-1) (B, G) - (C, H).

Вы бы попытались выбрать (B, G) точку отсечения для каждого неконечного узла, чтобы он соответствовал некоторому реальному делению в ваших данных.

Например, скажем, у вас есть матрица смаленький квадрат в середине, заполненный девятками и нулями в других местах.

С простым квадродеревом степеней двух вы получите как минимум 21 узел: 5 неконечных узлов, 4 листовых узладевятки и 12 листовых узлов нулей.(Вы получите еще больше узлов, если центральный маленький квадрат не будет точно на некотором расстоянии двух степеней от левого и верхнего краев, а не на некоторой точной степени двойного).

С помощью адаптивного дерева quadtree, если вы достаточно умны, чтобы выбрать точку среза для корневого узла в верхнем левом углу этого квадрата, то для нижнего правого дочернего элемента корня вы выберите точку среза наВ нижнем правом углу квадрата можно представить всю матрицу в 9 узлах: 2 неконечных узла, 1 листовой узел для девяток и 6 листовых узлов для нулей.

Answer 5

Знаете ли вы о .... деревьях интервалов?

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

Здесь вы можете эффективно описать свои прямоугольники и присвоить им значение.Конечно, прямоугольники могут перекрываться, вот что делает их эффективными.

0,0-n,n --> 8
4,4-7,7 --> 1
8,8-8,n --> 3

Затем при запросе значения в одном конкретном месте возвращается список из нескольких прямоугольников, и вам необходимо определить самый внутренний:это значение в этом месте.

Answer 6

Я не уверен, почему этот вопрос был задан вики-сообществом, но так оно и есть.

Я буду полагаться на предположение, что у вас есть приложение линейной алгебры, и что ваша матрица имеет прямоугольный типизбыточности.Если это так, то вы можете сделать что-то намного лучше, чем квадри, и чище, чем разрезать матрицу на прямоугольники (что обычно является правильной идеей).

Пусть M будет вашей матрицей, пусть v будет вектором, который вы хотитеумножить на M, и пусть A будет специальной матрицей

A = [1 -1  0  0  0]
    [0  1 -1  0  0]
    [0  0  1 -1  0]
    [0  0  0  1 -1]
    [0  0  0  0  1]

Вам также понадобится обратная матрица к A, которую я назову B:

B = [1 1 1 1 1]
    [0 1 1 1 1]
    [0 0 1 1 1]
    [0 0 0 1 1]
    [0 0 0 0 1]

Умножениевектор v на A быстрый и простой: вы просто берете разности последовательных пар элементов v. Умножить вектор v на B также быстро и просто: элементы Bv являются частичными суммами элементов v. Тогда вы хотитеиспользуйте уравнение

Mv = B AMA B v

Матрица АМА разрежена: в середине каждая запись представляет собой чередующуюся сумму из 4 записей M, которые составляют квадрат 2 x 2.Вы должны быть в углу одного из прямоугольников в M, чтобы эта переменная сумма была ненулевой.Поскольку AMA разрежена, ее ненулевые записи можно хранить в ассоциативном массиве и использовать умножение разреженной матрицы, чтобы применить его к вектору.

Answer 7

Ваше описание O (1) места для матрицы размером 100M x 100M сбивает с толку.Если у вас есть конечная матрица, то ваш размер является константой (если только программа, которая генерирует матрицу, не изменяет ее).Таким образом, количество места, необходимое для хранения, также является постоянным, даже если вы умножаете его на скаляр.Определенно, время чтения и записи матрицы не будет равно O (1).

Разреженная матрица - это то, о чем я мог бы подумать, чтобы уменьшить объем пространства, необходимого для хранения такой матрицы.Вы можете записать эту разреженную матрицу в файл и сохранить ее в виде tar.gz, который будет дополнительно сжимать данные.

У меня есть вопрос, что означает M в 100M?Это означает мегабайт / миллион?Если да, то этот размер матрицы будет 100 x 10 ^ 6 x 100 x 10 ^ 6 байт = 10 ^ 16/10 ^ 6 МБ = 10 ^ 10/10 ^ 6 ТБ = 10 ^ 4 ТБ !!!Какую машину вы используете?

Answer 8

Самый простой подход - использовать кодирование длины серии в одном измерении, а не беспокоиться о другом измерении.

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

Другой простой подход - попробовать заполнение прямоугольной заливкой - начните с правого верхнего пикселя и увеличьте его до максимально возможного прямоугольника (в ширину); затем пометьте все эти пиксели как «готово» и возьмите самый верхний правый оставшийся пиксель, повторяйте, пока не закончите. (Возможно, вы захотите хранить эти прямоугольники в каком-то BSP или квад-дереве.)

Высокоэффективный метод - не оптимальный, но, вероятно, достаточно хороший - состоит в том, чтобы использовать двоичное дерево разбиения пространства, где «пространство» измеряется не пространственно, а числом изменений. Вы бы рекурсивно обрезали так, чтобы у вас было одинаковое количество изменений слева и справа (или сверху и снизу - предположительно, вы бы хотели сохранить вещи квадратными) и, так как ваши размеры стали меньше, чтобы вы сократили столько изменения по мере возможности. В конце концов вы в конечном итоге отрежете два прямоугольника друг от друга, каждый из которых имеет одинаковое число; тогда остановись (Кодирование RLE в x и y быстро подскажет вам, где находятся точки изменения.)

Answer 9

хорошо, вам нужен алгоритм сжатия, попробуйте RLE (Run Length Encoding), он работает очень хорошо, когда данные сильно избыточны.

Answer 10

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

1. Матрица сильно избыточна, не обязательно разрежена.
2. Мы хотим минимизировать объем хранилища (на диске и в ОЗУ).
3. Мы хотим, чтобы была возможность умножить A [m * n] на вектор B [n * 1], чтобы добраться до AB [m * 1] без предварительного распаковывания (по крайней мере, не больше, чем требуется для выполнения расчетов).
4. Нам не нужен произвольный доступ к любой записи A [i * j] - все операции выполняются над матрицей.
5. Умножение выполняется онлайн (по мере необходимости), и поэтому должно быть максимально эффективным.
6. Матрица статическая.

Можно попробовать все виды хитроумных схем для обнаружения прямоугольников или самоподобия и т. Д., Но это приведет к снижению производительности при выполнении умножения. Я предлагаю 2 относительно простых решения.

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

Если данные преимущественно смещены в сторону горизонтального повторения, то может сработать следующее.

Подумайте о матрице, сплющенной в массив (так или иначе она действительно хранится в памяти). Э.Г.

A
| w0 w1 w2 |
| x0 x1 x2 |
| y0 y1 y2 |
| z0 z1 z2 |

становится

A’
| w0 w1 w2 x0 x1 x2 y0 y1 y2 z0 z1 z2 |

Мы можем использовать тот факт, что любой индекс [i,j] = i * j.

Итак, когда мы выполняем умножение, мы перебираем массив «матрицы» A 'с k = [0..m * n-1] и индексируем в вектор B, используя (k mod n), и в вектор AB с (K Div N). «Div» - целочисленное деление.

Так, например, A[10] = z1. 10 mod 3 = 1 и 10 div 3 = 3 A[3,1] = z1.

Теперь перейдем к сжатию. Мы выполняем нормальный прогон фрезерного кодирования (RLE), но вместо A, а не A. С плоским массивом будут более длинные последовательности повторений, следовательно, лучшее сжатие. Затем после кодирования прогонов мы делаем другой процесс, где мы извлекаем общие подстроки. Мы можем либо выполнить форму сжатия словаря, либо обработать данные прогона в некоторый вид оптимизированного по пространству графа, например, дерево радиксов / суффиксов или устройство вашего собственного создания, которое объединяет вершины и хвосты. Граф должен иметь представление всех уникальных строк в данных. Вы можете выбрать любое количество методов, чтобы разбить поток на строки: сопоставление префиксов, длины или чего-то еще (независимо от того, что подходит вашему графику лучше всего), но делать это на границе прогона, а не в байтах, иначе ваше декодирование будет усложнено. Граф становится конечным автоматом, когда мы распаковываем поток.

Я собираюсь использовать битовый поток и Patricia trie в качестве примера, потому что он простейший, но вы можете использовать что-то другое (больше битов на изменение состояния, лучшее объединение и т. Д. Ищите документы Stefan Nilsson ).

Чтобы сжать данные прогона, мы строим хеш-таблицу на графике. Таблица отображает строку в битовую последовательность. Вы можете сделать это, пройдя по графику и закодировав каждую левую ветвь как 0 и правую ветвь как 1 (произвольный выбор).

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

Если вы перевернете процесс, используя поток битов для обхода графика, пока не достигнете конечного / конечного узла, вы получите исходные данные прогона, которые вы можете декодировать на лету, чтобы получить поток целых чисел, против которого вы умножаете вектор B, чтобы получить AB. Каждый раз, когда у вас заканчиваются прогоны, вы читаете следующий бит и ищите соответствующую ему строку. Мы не заботимся о том, что у нас нет произвольного доступа к A, потому что он нужен нам только в B (B, который может быть сжат по диапазону / интервалу, но не обязательно).

Так что, хотя RLE смещен к горизонтальным участкам, мы все еще получаем хорошее вертикальное сжатие, потому что общие строки сохраняются только один раз.

Я объясню другой метод в отдельном ответе, так как он слишком длинный, но этот метод можетна самом деле ускоряет вычисления из-за того, что повторяющиеся строки в матрице A умножаются на один и тот же результат в AB.