Кодовая строка

[Cryonyx]

Привет всем. Мне собственно нужно вот что:
Есть набор различных подстрок, входящих в исходную строку, и есть их частоты, вычисленные по LZW. Как лучше всего на их основе сгенерировать коды, которые бы, по Хаффману, были наименьшей длины для наиболее часто встречающихся подстрок и наибольшей - для наиболее редких. И ещё - как это потом скомпоновать в результирующую строку таким образом, чтобы можно было потом эти коды выковырять.

[tyomitch]

Ищи где-нибудь на algolist.manual.ru
Алгоритм существует, но я его помню весьма приблизительно. Строится какое-то дерево, 1 в коде - спуск по левому ребёнку, 0 - по правому, или типа того. Получается легковыковыриваемый префиксный код

[Cryonyx]

Это Хаффман и есть. Дело здесь не столько в том, чтобы сгенить коды, а в том, чтобы сгенить их так, что потом легко будет выковырнуть из код-строки. К примеру, у нас есть коды 11, 100, 101, 1000...
Если мы просто запихнём их в код-строку, то получим примерно следующее: 111001011000... А отсюда выдрать коды фактически невозможно. Если же делать разделитель, скажем, "00", то нужно следить, чтобы в кодах этот разделитель не встречался, понимаешь?
В общем, я такой алг накидал, но он очень быстро приводит к переполнению буфера Примерно при 30-40 различных кодах. Вот я и хочу это как-то обойти..

[tyomitch]

Cryonyx, Хаффман даёт префиксный код. Т.е. коды 100 и 1000 одновременно получиться не могут.
Префиксный код можно записывать в строку безо всякого разделителя, и однозначно потом восстановить.
Перечитай Алголист, а?

[Arcanoid]

Надо в результирующую строку ещё и структуру дерева запихать чтобы можно было коды потом достать.. по крайней мере так в JPEGе делается.

[tyomitch]

Надо в результирующую строку ещё и структуру дерева запихать чтобы можно было коды потом достать.. по крайней мере так в JPEGе делается.

Вовсе не обязательно. В Deflate, например, предопределённое дерево, и его не надо передавать со строкой.