Можете ли вы кодировать до меньшего количества бит, когда вам не нужно сохранять порядок?

Question

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

Поскольку наборы не сохраняют порядок, а List сохраняют, означает ли это, что мы можем кодировать мультимножество в меньшем количестве бит, чем List?

Если да, то как бы вы закодировали Multiset?

Если это так, то какие еще примеры, где нет необходимости сохранять порядок, сохраняют биты?

Обратите внимание, я просто использовал 32-разрядные целые числа в качестве примера. Имеет ли значение тип данных в кодировке? Нужен ли тип данных фиксированной длины и сопоставим, чтобы вы могли сэкономить?

EDIT

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

Answer 1

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

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

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

Answer 2

Операция сортировки, за которой следует дельта списка, приведет к сериализованной форме, которую будет легче сжать.

EG [2 12 3 9 4 4 0 11] -> [0 2 3 4 4 9 11 12] -> [0 2 1 1 0 5 2 1], который весит примерно вдвое меньше.

Answer 3

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

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

Answer 4

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

Это принципиально ad hoc, поскольку схема без потерь (та, в которой вы можете восстановить входные данные), которая сокращает некоторые наборы данных, должна увеличивать другие. Коллекция целых чисел с большим количеством повторов будет очень хорошо работать в мультикарте, но если нет повторений, вы используете много места на счетчиках повторений 1. Вы можете проверить это, запустив утилиты сжатия для разных файлов. Текстовые файлы имеют большую избыточность и обычно могут быть сильно сжаты. Файлы со случайными числами будут расти при сжатии.

Я не знаю, что действительно есть преимущество в потере информации о заказе. Это зависит от того, каковы фактические цифры, прежде всего, если есть много дублирования или нет.

Answer 5

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

Надеюсь, это то, что вы имели в виду ...