Сортировка структур в порядке наименьшего изменения

Question

Это оказалось непонятным. Я перефразирую

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

struct element
{
uint32 positions[8];
}

Эти записи не зависят от порядка.
Формат выходного файла определен следующим образом:

byte  present;  // each bit indicating whether position[i] is present
uint32 position0;
-- (only bits set in Present are actually written in the file).  
uint32 positionN;  // N is the bitcount of "present"
byte  nextpresent;   

Все записи гарантированно уникальны, поэтому «текущий» байт 0 представляет EOF. Файл анализируется путем обновления «текущей» структуры с существующими полями, и результат добавляется в список.

Например: {1, 2, 3}, {2, 3, 2}, {4, 2, 3}
Было бы: 111b 1 2 3 001b 4 111b 2 3 2
Сохранение 2 чисел от несортированного подхода.

Моя цель - минимизировать размер выходного файла.

Answer 1

Ваша проблема

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

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

Ваши предположения

Из того, что вы сказали нам, я не вижу никакой реальной причины для того, чтобы вы разделяли свои 32 байта так, как вы описали (кроме того факта, что границы слов удобны)! Если вы получите те же данные обратно, вас действительно волнует, закодированы ли они как восемь лотов по 4 байта, или шестнадцать лотов по 2 байта, или как одно огромное 32-байтовое целое число?

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

Ваш вопрос

Вернемся к исходному вопросу, если вы действительно хотите пойти по этому пути. Легко представить себе выбор стартовой записи (я не думаю, что это будет иметь большое значение, но, вероятно, имеет смысл выбрать «наименьший» или «наибольший») и вычисление расстояния Хэмминга до всех других записей. Затем вы можете выбрать тот с минимальным расстоянием, чтобы сохранить следующий, и повторить. Очевидно, это O (n ^ 2) в количестве записей. К сожалению, эта статья (которую я не читал и не понимал подробно) заставляет выглядеть так, что вычисление минимального расстояния Хэмминга от одной строки до набора других является по сути сложным и не очень хорошим приближения.

Очевидно, что вы могли бы получить более сложную ситуацию, отсортировав свои записи по весу Хэмминга (который сводится к числу населенностей этого 32-байтового целого числа), которое равно O (n log (n)) количество записей. Затем используйте разностное кодирование результата. Но я не думаю, что это создаст ужасно хорошую схему сжатия: целые числа от 0 до 7 могут выглядеть примерно так:

000, 100, 010, 001, 101, 011, 110, 111

0, 4, 2, 1, 5, 3, 6, 7

Что возвращает нас к вопросу, который я задавал ранее: вы уверены, что ваша схема сжатия лучше, чем нечто более стандартное для ваших конкретных данных?

Answer 2

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

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

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