4.9.1. Алгоритм сортировки разделением множеств

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

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

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

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

Тест на существенность множества  можно резюмировать в следующем виде:

               (4.16)

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