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

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

Возможно, вы захотите взглянуть на формат GIF и его алгоритм сжатия. Просто думайте о своей матрице как о Bitmap...

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

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

Я бы начал с run-length-encoding, посмотрите, как это работает. Как только это заработает, попробуйте добавить некоторые трюки, например, ссылки на разделы предыдущего ряда. Так, ряд может быть закодирован как: 126 нулей, 8 единиц, 1000 записей, скопированных непосредственно из предыдущего ряда, 32 нуля. Кажется, что это может быть очень эффективно в вашем примере.

У меня нет конкретного ответа для показанной вами матрицы. В конечно-элементном анализе (FEA) есть матрицы с избыточными данными. При реализации пакета FEA в моем дипломном проекте, я использовал метод skyline storage.

Некоторые ссылки:

Страница Intel для хранения разреженных матриц

Ссылка на Википедию

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

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

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

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

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

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

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

Ваше описание пространства 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 ТБ !!! Какую машину вы используете?

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

Многие из приведенных выше решений подходят.

Если вы работаете с файлом, подумайте об ориентированных на файл инструменты сжатия, такие как compress, bzip, zip, bzip2 и другие. Они работают очень хорошо, особенно если данные содержат избыточные ASCII-символы. Использование внешнего инструмента сжатия устраняет проблемы и трудности внутри вашего кода и сжимает как двоичные, так и ASCII-данные.

В вашем примере вы отображаете односимвольные числа. Числа 0-9 могут быть представлены меньшим четырехбитовым кодировки. Вы можете использовать дополнительные биты в байте в качестве счетчика. Четыре бита дают вам дополнительные коды для убежать в дополнительные... Но есть предостережение, которое восходит к старым ошибкам Y2K, когда использовались два символа в течение года. Кодирование байта из оффсета дало бы 255 лет, и те же два байта охватывали бы всю письменную историю и даже больше.

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

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

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

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

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

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

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 в качестве примера, потому что это проще всего, но вы можете использовать что-то другое (больше бит на состояние, изменение лучшего слияния и т.д.). Посмотрите работы Стефана Нильссона).

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

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

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

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

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

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

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

В этом методе мы сохраняем структуру строки * столбца матрицы.

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

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

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

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

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

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.

( Если прогоны длиннее нескольких байтов, то подсчитайте частоту для хэша, который вы создаете при выполнении 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

Один гигантский поток 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}

= 2 * 23 = 46 Bytes

Один гигантский поток 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

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

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

Пусть 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

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

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

Самый простой способ сделать это - чтобы каждый узел дерева квадрантов покрыл область 2 ^ n x 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 конечных узлов из нулей. (Вы получите еще больше узлов, если центрированный маленький квадрат не находится точно на некотором расстоянии степени двойки от левого и верхнего краев, а не на некоторой точной степени двойки).

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