Координатные схемы сжатия

Тема в разделе "WASM.A&O", создана пользователем UbIvItS, 16 мар 2007.

  1. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    Наоборот - динамический вариант относительной адресации - такой:
    1. лопатим 64 байтные блоки (больше при 8 битной букве уже нельзя)
    2. если встречаются зацепки к цепочкам, складываем их отдельно для дополнительной проверки
    3. если в результате архивации видим крупные блоки с незаполненными или слабо заполненными адресами вот тогда и переходим к 2-3-4-5 битной адресации там где она актуальна :) есно как нибудь (способов много) пометив границы такого блока с повышенным сжатием. Что впрочем не исключает случая когда этим блоком с 4 битной адресацией окажется весь файл как в #48 :)

    [offtop]
    Во-во а тут обратная задача - океан в каплю ужать :)
    [/offtop]

    ЗЫ: А так мы вернулись к тому с чего начинали - ты так и не привёл примера данных которые бы прямым csc сжимались лучше чем относительным, только с маленькой поправкой - мне стала понятна суть алгоритма и теперь я уже совершенно точно уверен, что привести пример таких данных ты не сможешь :)))
     
  2. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    короче, реально надоело толочь воду в ступе - у меня на это нет времени, а самое главное желания.
    как сделаю прогу - выложу на сайт, а там сам сравнивай, ищи. а тебе рекомендую, коль не веришь мне и считаешь, что я несу ересь - проверяй все свои выкладки на практике(за что я ее люблю, она не дает тонуть в пустых мечтах и надеждах- весьма жестокая девочка не правда ли:)))), могет свершиться чудо и ты докажешь, что более пессимистичная модель может во всех случаях проиграть более оптимистичной:))) я тебя уже просил мне показать док-во, что твоя модель при всех равных условиях ВСЕГДА ПОКАЖЕТ ХОТЯ БЫ ТОТ ЖЕ РЕЗУЛЬТ, ПОКА Я РЕАЛЬНЫХ ДОКАЗАТЕЛЬСТВ НЕ ВИДЕЛ, КРОМЕ ДОМЫСЛОВ. короче, жди прогу.
     
  3. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    Ты не верно позиционируешь свою модель как "пессиместичную" и работающую на данных с "малой избыточностью", она не обладает ни тем ни другим свойством.
    Но ты совершенно прав:
    Вернёмся к теме либо если до тебя наконец дойдет принцып работы твоей же идеи, либо если у кого нибудь из нас наконец дойдут руки слепить пробный код. Успехов!!!
     
  4. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    Y_Mur
    итак, пришло время вернуться к нашим баранам. получилась забавная вещь ты прав и неправ одновремено: относительная адресация и впрямь самая пессимистичная, только эта адресация может быть разная, короче, качай маныча http://xproject-all.narod.ru/csc_compressing_algos3.7z. и ещё: прога пока получилась не столько для того, чтобы сжимать - сколько для того, чтобы считать:))) - из мана поймёшь о чём я:)
     
  5. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    в архиваторе для склейки массивов я юзаю след. подход:

    mass_one+=mass_two<<N , N - кол-во бит в mass_one
    какой код лучше приведенного по скорости??
     
  6. QuakeMan

    QuakeMan New Member

    Публикаций:
    0
    Регистрация:
    27 июн 2007
    Сообщения:
    17
    тема жива еще?
    я на днях задумался над кодировкой похожей на CISC... символы кодируются разной битовой длиной.
    схема такая
    00 - знач символ
    01 - тоже знач
    10 - +предыдущая длина
    11 - + 2 х предыдущая длина

    вот примеры кода:

    Код (Text):
    1. символ    код
    2. первый    00
    3. 2         01
    4. 3         10 00
    5. 4         10 01
    6. 5         11 00 00
    7. 6         11 00 01
    8. 7         11 01 00
    9. 8         11 01 01
    10. 9         11 10 00
    11. 10        11 10 01
    12. 11        11 11 00
    13. 12        11 11 01
    14. 13        10 10 00
    15. 14        10 10 01
    16. 15        10 11 00 00
    17. 16        10 11 00 01
    18. 17        10 11 01 00
    19. 18        10 11 01 01
    20. 19        10 11 10 00
    21. 20        10 11 10 01
    22. 21        10 11 11 00
    23. 22        10 11 11 01
    24. 23        10 10 10 00
    25. 24        10 10 10 01
    что бы было понятнее расшифровка символа подлинее
    Код (Text):
    1. 11 хх 11 хх хх хх 10 xx xx xx 0x
    х - значащие биты
    остальные биты - биты длины, первая 11 - после нее 4 бита, вторая 11 после нее 8 бит, и 10 после нее такая же длина как предыдущая - 8 бит.

    я конечно не думаю что подобной кодировки нет, но возможно ее местами было бы удобно использовать, в тех же алгоритмах сжатия (хотя в них чесно говоря не разбираюсь)
    последний пример длины позволяет использовать 2^15 значений - по кол-ву х
     
  7. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    QuakeMan
    что это за кодировка??
    по моим подсчётам актульными являются кодировки DSCC сегментная модель и относительная -опорная адресация с ограниченной длиной прыжка. по подсчётам Y_Mur'a CSC даёт результат уровня словарного алгоритма(сегмент 65 байт, длина буквы 8 бит).
     
  8. QuakeMan

    QuakeMan New Member

    Публикаций:
    0
    Регистрация:
    27 июн 2007
    Сообщения:
    17
    CISC не помню как дословно расшифровается
    вот в словаре глянул
    [complete-instuction-set computing] полный набор команд (архитектура процессора, в отличие от RISC)
    Комнды с переменной длиной в общем.
    Ну и в этой кодировке длина отдельного символа разная, а будет она для тебя актуальна или нет этого я уже не скажу.
     
  9. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    QuakeMan
    я в кодировках юзаю методики фиксации потерь, тоесть рост длины замещающего кода имеет макс. длину, заранее установленую: в твоём примере код распухает неограниченно.
     
  10. QuakeMan

    QuakeMan New Member

    Публикаций:
    0
    Регистрация:
    27 июн 2007
    Сообщения:
    17
    Ну возможно, хотя если символов всего 14, то кодирование одного от двух бит до 6-ти займет.
    Для символьной кодировки это довольно удобно по моему - чаще употребляемые символы кодируются под первые цепочки.
    Я вот щас глянул еще ряд 8 битных символов увидел
    11 xx 10 zx
    плюс 8 символов, все еще в восьми битной длине.
    вобще конечно надо просчитать эту кодировку, но пока у меня руки не дошли написать под нее формулу.

    еще обращай внимание - я это просто под символьную кодировку надумал (как альтернатива табличной), а как работают алгоритмы сжатия еще раз повторюсь я не знаю.
     
  11. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    QuakeMan
    я в мане настрокал как пашут координатки и как в словарных методиках фиксировать границу потерь, если хочешь, можешь почитать, правда, излагаю я довольно сжато:)), но, коли, будут вопросы - задавай.
     
  12. QuakeMan

    QuakeMan New Member

    Публикаций:
    0
    Регистрация:
    27 июн 2007
    Сообщения:
    17
    Я как понимаю, ты создаеш словарь, потом для каждого символа указываеш координаты?
     
  13. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    QuakeMan
    вся суть координаток в том, что границы между словарём и первыми вхождениями букв нет.
    архив выглядит так: [буква1][координаты_всех_вхождений_буквы1_кроме_первого],...,[буква(i)][координаты_всех_вхождений_буквы(i)_кроме_первого].
    по мере прочтения сегмента для каждой буквы формируется пакет, где сохраняются адреса вхождений буквы, затем пакеты склеиваются в порядке вхождения букв - в итоге получаем структуру архива в общем виде.
     
  14. QuakeMan

    QuakeMan New Member

    Публикаций:
    0
    Регистрация:
    27 июн 2007
    Сообщения:
    17
    а разница размеров архивируемого файла учитывается?
    или это исключительно для 4 гигабайтных файлов схема?

    з.ы. я в пм скинул номер аське, мне эта тема интересна немного.
     
  15. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    QuakeMan
    вообще, прямая адресация по всему файлу это полный саксссс: слишком здоровая ресурсоёмкость. имеет смысл мастырить либо сегментную DSCC, либо относительная -опорная адресация с ограниченой длиной прыжка. ещё очень важно учитывать плохие сегменты. иначе маздай ничего жать не будет:)).
    ну и еще на избыточных данных в координатках проку нет - они у того же лзв на реальном подсосе:), зато, если нужно сжать рар, зип - тут их стихия, правда, арифметик может координатки заткнуть за пояс, но властелин сжатия, что черепаха: слишком здоровый аппетит у него на проц.
    -
     
  16. QuakeMan

    QuakeMan New Member

    Публикаций:
    0
    Регистрация:
    27 июн 2007
    Сообщения:
    17
    сколько вот еще интересно выходит букв
    есть какая то статистика?
     
  17. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    не совсем понял о чём речь.
    сегментные CSC & DSCC с учётом плохих сегментов дают 0,21% и 0,32% на рар файлах.
    .................................................
    ЗЫ
    у тебя что аська не пашет?
     
  18. QuakeMan

    QuakeMan New Member

    Публикаций:
    0
    Регистрация:
    27 июн 2007
    Сообщения:
    17
    букв в смысле букв, в том же контексте что и в твоем доке
    их же ограниченное кол-во выходит
    кол-во букв на длину архива


    з.ы. вроде как запущена была
    сейчас другой клиент запущу
     
  19. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    QuakeMan
    здесь важно кол - во вхождений каждой буквы, коли она один раз входит, то на ней идёт потеря в один бит на любой схеме. а, вообще, я такой инфы не собирал - смотрел сугубо на процент сжатия. и ещё: я пока фактически сделал CSC без учёта плохих сегментов по ней я и считал эти 0,21 и 0,32%, надо заметить, оценки приближённые и заниженные.

    ЗЫ

    ты какую версию мана качнул?
     
  20. QuakeMan

    QuakeMan New Member

    Публикаций:
    0
    Регистрация:
    27 июн 2007
    Сообщения:
    17
    вроде как последнюю
    от 30.05