Вопросы Теги

Эффективный способ сохранить дерево Huffman

Вы можете использовать iloc, который берет индекс и предоставляет результаты. iloc[row_indexes, column_indexes]

Таким образом, df.iloc[0,:] займет первую (0-ую) строку и все столбцы. Он передаст обратно Series, так что вы можете использовать понимание списка [str (x) для x в итерируемом] для передачи значений в виде строк. 

import pandas as pd

df = pd.DataFrame({'a':[1, 2], 'b':[3, 4], 'c':[5, 6]})

[str(x) for x in df.iloc[0,:]]

['1', '3', '5']
34
задан Bill the Lizard 16 September 2012 в 15:34
поделиться

4 ответа

Поскольку вам уже нужно реализовать код для обработки побитового слоя поверх вашего организованного байта потока / файла Вот мое предложение.

Не храните фактические частоты, они не нужны для декодирования. Тем не менее, вам нужно фактическое дерево.

Таким образом, для каждого узла, начиная с корня:

  1. Если leaf-node: Вывести 1-битный + N-битный символ / байт
  2. Если не leaf-node, выходной 0-бит. Затем одинаково закодируйте оба дочерних узла (сначала слева, затем справа).

Чтобы прочитать, сделайте следующее:

  1. Бит чтения. Если 1, то прочитать N-битный символ / байт, вернуть новый узел вокруг него без дочерних элементов
  2. Если бит равен 0, декодировать левый и правый дочерние узлы одинаково, и вернуть новый узел вокруг них с этими дочерними элементами, но нет значения

Листовой узел - это, по сути, любой узел, у которого нет дочерних элементов.

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

Псевдокод для расчета: 

Tree-size = 10 * NUMBER_OF_CHARACTERS - 1
Encoded-size = Sum(for each char,freq in table: freq * len(PATH(char)))

Расчет размера дерева занимает лист, а не -лимитные узлы учитываются, и встроенного узла меньше, чем символов.

SIZE_OF_ONE_CHARACTER будет числом битов, и эти два дадут вам общее количество битов, которое будет занимать мой подход к дереву + закодированные данные

PATH (c) - это функция / таблица, которая выдала бы битовый путь от корня до этого символа в дереве.

Вот псевдокод для поиска на C #, который предполагает, что один символ просто простой байт. и вывод будет 92 бита или 12 байтов. Сравните это с 20 * 8 байтами, необходимыми для хранения исходных 20 символов без кодировки, вы сэкономите 8 байтов.

Окончательный результат, включая начальное дерево, выглядит следующим образом. Каждый символ в потоке (AE) кодируется как 8 битов, тогда как 0 и 1 - это просто один бит. Пространство в потоке просто отделяет дерево от закодированных данных и не занимает места в конечном выводе. 

001A1C01E01B1D 0000000000001100101010101011111111010101010

Для конкретного примера, который есть в комментариях, AABCDEF, вы получите следующее:

Вход: AABCDEF

Частоты:

  • A: 2
  • B: 1
  • C: 1
  • D: 1
  • E: 1
  • F: 1

Дерево: 

        7
  -------------
  |           4
  |       ---------
  3       2       2
-----   -----   -----
A   B   C   D   E   F
2   1   1   1   1   1

Пути:

  • A: 00
  • B: 01
  • C: 100
  • D: 101
  • E: 110
  • F: 111

Дерево: 001A1B001C1D01E1F = 59 бит
Сравните это с 20 * 8 байтами, необходимыми для хранения исходных 20 символов без кодировки, вы сэкономите 8 байтов.

Окончательный результат, включая начальное дерево, выглядит следующим образом. Каждый символ в потоке (AE) кодируется как 8 битов, тогда как 0 и 1 - это просто один бит. Пространство в потоке просто отделяет дерево от закодированных данных и не занимает места в конечном выводе. 

001A1C01E01B1D 0000000000001100101010101011111111010101010

Для конкретного примера, который есть в комментариях, AABCDEF, вы получите следующее:

Вход: AABCDEF

Частоты:

  • A: 2
  • B: 1
  • C: 1
  • D: 1
  • E: 1
  • F: 1

Дерево: 

        7
  -------------
  |           4
  |       ---------
  3       2       2
-----   -----   -----
A   B   C   D   E   F
2   1   1   1   1   1

Пути:

  • A: 00
  • B: 01
  • C: 100
  • D: 101
  • E: 110
  • F: 111

Дерево: 001A1B001C1D01E1F = 59 бит
Сравните это с 20 * 8 байтами, необходимыми для хранения исходных 20 символов без кодировки, вы сэкономите 8 байтов.

Окончательный результат, включая начальное дерево, выглядит следующим образом. Каждый символ в потоке (AE) кодируется как 8 битов, тогда как 0 и 1 - это просто один бит. Пространство в потоке просто отделяет дерево от закодированных данных и не занимает места в конечном выводе. 

001A1C01E01B1D 0000000000001100101010101011111111010101010

Для конкретного примера, который есть в комментариях, AABCDEF, вы получите следующее:

Вход: AABCDEF

Частоты:

  • A: 2
  • B: 1
  • C: 1
  • D: 1
  • E: 1
  • F: 1

Дерево: 

        7
  -------------
  |           4
  |       ---------
  3       2       2
-----   -----   -----
A   B   C   D   E   F
2   1   1   1   1   1

Пути:

  • A: 00
  • B: 01
  • C: 100
  • D: 101
  • E: 110
  • F: 111

Дерево: 001A1B001C1D01E1F = 59 бит
в том числе дерево для начала, заключается в следующем. Каждый символ в потоке (AE) кодируется как 8 битов, тогда как 0 и 1 - это просто один бит. Пространство в потоке просто отделяет дерево от закодированных данных и не занимает места в конечном выводе. 

001A1C01E01B1D 0000000000001100101010101011111111010101010

Для конкретного примера, который есть в комментариях, AABCDEF, вы получите следующее:

Вход: AABCDEF

Частоты:

  • A: 2
  • B: 1
  • C: 1
  • D: 1
  • E: 1
  • F: 1

Дерево: 

        7
  -------------
  |           4
  |       ---------
  3       2       2
-----   -----   -----
A   B   C   D   E   F
2   1   1   1   1   1

Пути:

  • A: 00
  • B: 01
  • C: 100
  • D: 101
  • E: 110
  • F: 111

Дерево: 001A1B001C1D01E1F = 59 бит
в том числе дерево для начала, заключается в следующем. Каждый символ в потоке (AE) кодируется как 8 битов, тогда как 0 и 1 - это просто один бит. Пространство в потоке просто отделяет дерево от закодированных данных и не занимает места в конечном выводе. 

001A1C01E01B1D 0000000000001100101010101011111111010101010

Для конкретного примера, который есть в комментариях, AABCDEF, вы получите следующее:

Вход: AABCDEF

Частоты:

  • A: 2
  • B: 1
  • C: 1
  • D: 1
  • E: 1
  • F: 1

Дерево: 

        7
  -------------
  |           4
  |       ---------
  3       2       2
-----   -----   -----
A   B   C   D   E   F
2   1   1   1   1   1

Пути:

  • A: 00
  • B: 01
  • C: 100
  • D: 101
  • E: 110
  • F: 111

Дерево: 001A1B001C1D01E1F = 59 бит
Данные: 000001100101110111 = 18 бит
Сумма: 59 + 18 = 77 бит = 10 байт

Поскольку оригинал состоял из 7 символов с 8 битами = 56, у вас будет слишком много служебных данных для таких маленьких фрагментов данных.

77
ответ дан 27 November 2019 в 16:12
поделиться

ветви - 0, листья - 1. Сначала пройдитесь по глубине дерева, чтобы получить его «форму» 

e.g. the shape for this tree

0 - 0 - 1 (A)
|    \- 1 (E)
  \
    0 - 1 (C)
     \- 0 - 1 (B)
         \- 1 (D)

would be 001101011

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

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

4
ответ дан 27 November 2019 в 16:12
поделиться

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

ОБНОВЛЕНИЕ : Как указал j_random_hacker в комментарии, вы на самом деле не можете этого сделать: вам нужны сами значения частоты. Они объединяются и «всплывают» вверх, когда вы строите дерево. Эта страница описывает способ построения дерева из таблицы частот. В качестве бонуса он также сохраняет этот ответ от удаления, упомянув способ сохранения дерева:

Самый простой способ вывести само дерево Хаффмана - сначала, начиная с корня, сбросить сначала левую часть, а затем Правая сторона. Для каждого узла выведите 0, для каждого листа выведите 1, за которым следуют N битов, представляющих значение.

2
ответ дан 27 November 2019 в 16:12
поделиться

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

То есть, если у вас есть дерево / коды, упомянутые Лассе:

  • A: 00
  • B: 110
  • C: 01
  • D: 111
  • E: 10

Затем вы можете сохранить их как: 2, 3, 2, 3, 2

И на самом деле этой информации достаточно, чтобы восстановить таблицу Хаффмана, если вы всегда используете один и тот же набор символов - скажем, ASCII. (Это означает, что вы не можете пропускать буквы - вам придется указать длину кода для каждой, даже если она равна нулю.)

Если вы также наложите ограничение на длину битов (скажем, 7 бит), вы можете хранить каждое из этих чисел, используя короткие двоичные строки. Таким образом, 2,3,2,3,2 становится 010 011 010 011 010 - что умещается в 2 байта.

Если вы хотите, чтобы действительно сумасшедший, вы могли бы сделать то, что делает DEFLATE, и сделать другую таблицу Хаффмана длин этих кодов и заранее сохраните ее длины кодов. Тем более, что они добавляют дополнительные коды для «вставить ноль N раз подряд», чтобы еще больше сократить время.

RFC для DEFLATE не так уж и плох, если вы ' Вы уже знакомы с кодированием Хаффмана: http://www.ietf.org/rfc/rfc1951.txt

11
ответ дан 27 November 2019 в 16:12
поделиться
Другие вопросы по тегам:

Похожие вопросы: