Существует множество определений семьи в социологии. Наиболее популярно понимание семьикак объединения людей, основанного на кровном родстве, браке или усыновлении, которых связывает общность быта и (или) взаимная ответственность за воспитание детей. Семья включает в себя разнородные компоненты, связанные с физиологическими процессами, с психологией взаимоотношений, с нормами и ценностями культуры, с демографической динамикой, с экономическими условиями жизни, с государством,с политикой, с историей. По этой причине в социологии семья рассматривается как социальный институт, находящийся во взаимосвязи с другими институтами. С другой стороны, социология рассматривает семью как малую группу, как сравнительно автономную социальную систему со специфическими ценностями, установками, ролями. Следовательно, в социологии с её подходом изучения социального мира через взаимосвязь личного и общественного семья выступает в качестве посредника между индивидом и обществом.
Первоначальную основу семейных отношений составляет брак. Брак- это исторически меняющаяся форма отношений между мужчиной и женщиной, посредством которого общество упорядочивает и санкционирует их половую жизнь и устанавливает их супружеские права и обязанности. Можно сказать, что брак– этосовокупность норм, регулирующих отношения супругов друг к другу, их взаимные права и обязанности, а также их отношения к детям и совместному имуществу. Формы брака, используемые обществами, весьма разнообразны.
Иногда общество ограничивает выбор партнера в браке тем, что разрешает выбирать его только вне определенной узкой группы. Эта форма брака принято называть экзогамией. В нашем обществе это ограничение применяется для избежания кровосмесительных связей. Так, правовые нормы запрещают нам жениться на сестрах, двоюродных сестрах и некоторых других близких родственниках. Во многих обществах запрещено выбирать супруга внутри своего клана, деревни, а иногда даже племени.
В обществах есть и противоположные требования, когда выбор партнера в браке возможен лишь в пределах своей группы. Такой вид брака принято называть эндогамией. В современных обществах широко распространена расовая эндогамия или эндогамия сословная. Эндогамия характерна для закрытых групп типа каст, где путем эндогамных браков поддерживается их закрытость.
По количеству партнеров в браке различают моногамию и полигамию. Моногамия, ᴛ.ᴇ. брак одного мужчины с одной женщиной (в одно время) наиболее привычный для современных европейских обществ. Но в развитии большинства обществ практиковалась полигамия ᴛ.ᴇ. формы брака, при которых существует более одного партнер в супружестве. Возможны три формы полигамии. В первую очередь, групповой брак, при котором несколько мужчин и несколько женщин находятся одновременно между собой в брачных отношениях. Очень редкой формой полигамного брака является полиандрия, когда женщина имеет несколько мужей. Наиболее распространенной формой полигамного брака является полигиния, или многоженство. Как отмечает С.С. Фролов, мнение представителей современной Европы и Северной Америки о многоженстве в значительной степени этноцентрично. «Многие в нашем обществе, к примеру, считают, что культивирование такой формы брака ведет к деградации женщины, к превращению ее в рабыню. Это считается неслыханной жестокостью и вызывает возмущение (возможно, это чувство навеяно некоторыми фильмами о восточных владыках). При этом факты говорят об обратном. Трудно сказать, в каком обществе женщина имеет более высокий статус - в обществе с полигамной или моногамной формой брака. В первую очередь, даже в обществах, где широко распространена полигамная семья, браки обычно являются моногамными. Только наиболее преуспевающие люди с высоким статусом могут позволить себе иметь более одной жены. Во-вторых, обязанности между женами четко распределены, а первая жена очень часто оказывает решающее влияние на поведение мужа. Жизнь всех жен в достаточной степени обеспечена, и они, как правило, не желают для себя другой доли».
Кроме того по типу властных отношений различают патриархальный брак(власть у мужа), матриархальный брак (власть у жены) и эгалитарный брак (власть у обоих супругов). В современных европейских обществах преобладает эгалитарный брак.
К сожалению, брак не всегда бывает успешным и для исправления ситуации в современных обществах предусмотрен развод. Но, в то же время, обществу невыгодна любая нестабильность института семьи. По этой причине практически в каждом обществе существуют определенные правила и законы, затрудняющие развод или дающие привилегии одной из сторон. Большинство обществ стремится сделать развод весьма болезненной операцией. Особенно это касается тех обществ, где партнер по браку выбирается родителями. Очень часто в тех обществах, где большое значение имеет родственная семья, воспитание ребенка в случае развода частично берут на себя братья, сестры, дяди или тети. Как отмечает С.С. Фролов, «в нашем обществе с сильным акцентом на индивидуальную любовь при выборе партнера и при ярко выраженном приоритете нуклеарной семьи развод чаще всего влечет за собой трагические последствия как для детей, так и для взрослых».
Как социальный институт семья выполняет следующие функции в обществе
Функция сексуального регулирования состоит в том, что общество упорядочивает, направляет и регулирует естественные сексуальные потребности людей. Вместе с тем практически каждое общество имеет альтернативные пути удовлетворения сексуальных потребностей. Несмотря на то, что существуют определенные нормы супружеской верности, большинство обществ легко прощает нарушения этих норм.
Репродуктивная функция состоит в воспроизводстве новых поколений членов общества. При этом важно, чтобы дети были физически и психически здоровыми и впоследствии имели способности к обучению и социализации. Вместе с тем важным условием существования общества является регулирование рождаемости, избежание демографических спадов или, наоборот, взрывов. Семья - это основной институт, ответственный за воспроизводство новых членов общества. Другие пути неэффективны и, как правило, социально не одобряются. По этой причине появление ребенка вне института семьи обычно вызывает жалость, сострадание или осуждение.
Функция социализации состоит в том, что семья помогает ребенку усвоить нормы того общества, в котором он родился. Именно в семье закладываются основы формирования личности.С.С. Фролов отмечает, что «многие мыслители, начиная с Платона, говорили об обобществлении воспитания детей, однако все попытки социализации вне института семьи оказывались неудачными. К примеру, после революции в Советском Союзе были созданы специализированные программы общественного воспита-ния детей, с тем чтобы женщины могли участвовать в трудовом процессе. При этом данный эксперимент не получил широкого распространения. Сегодня в нашем обществе пытаются совместить усилия образовательных институтов и института семьи для успешной социализации детей, но семья по-прежнему удерживает первенство в социали-зации индивидов. В современном Израиле дети в кибуцах (кооперативных фермах) воспитываются в общих коттеджах и находятся под присмотром специальных воспитателей, в то время как их матери выполняют различные работы в тех же кибуцах. Родители обычно проводят с детьми около двух часов в день и весь день в субботу. По мнению некоторых обозревателей, такое воспитание проходит успешно, хотя у него существует много противников. Правда, так воспитывается лишь незначительное число детей Израиля. Эти редкие исключения, пожалуй, только подчеркивают первосте-пенное значение семьи для социализации детей. Семья для ребенка является первичной группой, именно с нее начинается развитие личности. Несмотря на появление позднее других первичных групп, у личности всегда остаются привитые в раннем детстве основные образцы поведения. Главным способом семейной социализации является копирование детьми моделей поведения взрослых членов семьи. Трудности социализации возникают в том случае, если ребенок ориентируется на неудачные образцы поведения родителей, которые приходят в противоречие с тем, что ребенок видит в других семьях. При этом часто возникает неудовлетворенность действиями матери или отца, и ребенок начинает искать у других личностей, в других первичных группах приемлемые модели поведения».
Эмоциональная функция состоит в удовлетворении потребности человека в интимном общении. «Психиатры считают, что основной причиной эмоциональных и поведен-ческих трудностей в общении и даже физических болезней является отсутствие любви, тепла и полноценного интимного общения в первич-ной группе, и прежде всего в семье. Огромное количество данных свидетельствует о том, что серьезные преступления и другие негативные отклонения намного чаще происходят у тех, кто в детстве был лишен заботы в семье, что дети, воспитанные в детских домах без любви матери и отца, гораздо в большей степени подвержены заболеваниям, психическим расстройствам, повышенной смертности, отклоня-ющемуся поведению. Доказано; что потребность людей в близком доверительном общении, интимности, эмоциональном выражении чувств близким людям является жизненно необходимым элементом существования. Благодаря своей структуре и качествам, семья служит самым важным источником эмоционального удовлетворения. Отношения родства и супружества предоставляют людям такую возможность».
Статусная функция состоит в том, что каждый человек, воспитанный в семье, получает в качестве наследия некоторые статусы, близкие к статусам членов его семьи. «Это прежде всего относится к таким важным для личности статусам, как национальность, место в городской или сельской культуре и др. В классовых обществах принадлежность семьи к определенному социальному слою предоставляет ребенку возможности и вознаграждения, характерные для этого слоя, и в подавляющем большинстве случаев определяют его дальнейшую жизнь. Конечно, классовый статус может изменяться благодаря усилиям человека и благоприятным обстоятельствам, но начало будущего нужно искать в семье этого человека. Семья обязательно должна осуществлять ролевую подготовку ребенка к статусам, близким к статусам его родителей и родственников, прививая ему соответствующие интересы, ценности и образ жизни».
Защитная функция состоит в том, что семья призвана защитить человека от перегрузок, предоставляя ему возможность отдыха после трудового дня. Кроме того институт семьи осуществляет в разной степени физическую, экономическую и психологическую защиту своих членов. Обычно, задевая интересы и безопасность любой личности, мы задеваем и его семью, члены которой защищают своего близкого или мстят за него
Экономическая функция состоит в ведении членами семьи общего хозяйства, когда все они работают, как одна команда, способствует формированию крепких экономических связей между ними. Нормы семейной жизни включают обязательную помощь и поддержку каждого члена семьи в случае, если у него возникают экономические трудности.
Учитывая важность функций, которые призвана выполнять семья, государство птается создать условия для наиболее эффективного их выполнения. Такая деятельность принято называть семейной политикой государства.Государственная семейная политика– система государственных мер по обеспечению социальной безопасности семьи, по созданию условий для реализации ее социально-значимых функций
Весьма разнообразны формы семьи как малой группы.
По этапам жизненного цикла различают молодую (до 10 лет семейного стажа) и зрелую семью.
По критерию социального статуса семьи бывают гомогенные (супруги из одной социальной страты-к примеру, студенческая семья) и гетерогенными (из разных классов, каст, слоёв), и по национально- этническому критерию - браки межнациональные или внутринациональные.
В современном урбанизированном обществе основным типом семьи стали нуклеарные семьи, состоящие из двух поколений- родители, дети. Нуклеарная семья принято называть репродуктивной (если в ней остались несовершеннолетние дети) или ориентационной (вышли взрослые дети и создали свои репродуктивные семьи). Репродуктивная семья классифицируется по наличию детей: детная, бездетная и семейный детский дом. В свою очередь детная семья бывает 1детной, 2хдетной и многодетной.Иногда нуклеарные семьи называют супружескими.Но нуклеарная семья может быть и без одного из супругов (неполная отцовская или неполная материнская семья). В неполной материнской семье различают семью одинокой матери (когда ребенок рожден вне брака), семью матери-одиночки (когда ребенок рожден в браке) и семью солдата срочной службы. Расширенная семья состоит из ряда супружеских пар (тесть-тёща, свёкор-свекровь, братья-сёстры, их супруги-дети). Это кровнородственные семьи. Полная расширенная семья - это когда никто из мужчин разных поколений не покидает пределы большой семьи. Такие семьи характерны для Китая.
Расширенная или родственная семья основывается не только на супружеских отношениях двух людей, но и на кровном родстве большого числа родственников. Значение нуклеарной и родственной семей для общества неодинаково. Так, хотя в нашем обществе существует родственная семья для семейных сборов, торжеств и других церемониальных целей, важнейшие социальные функции выполняются нуклеарной семьей. Это выражается во многих элементах культуры, к примеру когда законы и нравственные нормы требуют, чтобы родители поддерживали своих детей, но ничего не говорят об обязанностях по отношению к братьям или сестрам, дядям или тетям.
В случае если нуклеарная семья имеет в основе супружескую пару, то основой родственной семьи являются братья и сестры в окружении их мужей, жен и детей. В большинстве родственных семей женатый мужчина (или замужняя женщина) в первую очередь остается привязанным к родительской семье и наполовину входит в семью жены (или мужа). Это имеет важные последствия. Человек в основном связан обязательствами и ответственностью с той семьей, в которой он родился, но не с той, с которой он связан узами брака. Так, женщина может не зависеть от своего мужа, но полностью быть в зависимости от своих братьев и сестер в деле защиты и воспитания детей.
В расширенных семьях ответственность и забота распределяются среди достаточно большого числа членов семьи. Создается ситуация, когда ребенок тесно связан не только с родителями, но и со своими дядями и тетями. Он окружен взрослыми, которые в некоторых случаях готовы взять на себя обязанности родителей. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, у ребенка в родственной семье появляется большая возможность для общения и социализации к большему числу ролей. Такая семья хорошо защищает ребенка от любых жизненных невзгод. В случае смерти матери или ухода ее из семьи ее роль в известной степени могут играть родственники.
В реальной жизни родственная семья далеко не всегда возможна. Это связано, к примеру, с тем, что место рождения и место вступления в брак бывают значительно удалены друг от друга. Вместе с тем, родственники бывают фактически или социально отдалены от супружеской пары, и в этом случае семья остается в чистом виде нуклеарной. Современное общество характерно ослаблением многих родственных связей и, следовательно, преобладанием нуклеарной семьи над родственной.
Процесс формирования семьи как малой группы обусловлен ценностно-нормативными регуляторами (сексуальные стандарты поведения, нормы выбора брачного партнёра, отношения между родителями и детьми).На ранних стадиях общества отношения полов и поколений регулировались племенно-родовыми обычаями, базировались на религиозно-нравственных представлениях. С возникновением государства регулирование семейной жизни приобрело правовой характер.
Метод Хаффмана является простым, но эффективным только в том случае, когда вероятности появления символов равны числам , где - любое целое положительное число. Это связано с тем, что код Хаффмана присваивает каждому символу алфавита код с целым числом бит. Вместе с тем в теории информации известно, что, к примеру, при вероятности появления символа равной 0,4, ему в идеале следует поставить код длиной 
бит. Понятно, что при построении кодов Хаффмана нельзя задать длину кода в 1,32 бита͵ а только лишь в 1 или 2 бита͵ что приведет в результате к ухудшению сжатия данных. Арифметическое кодирование решает эту проблему путем присвоения кода всему, обычно, большому передаваемому файлу вместо кодирования отдельных символов.
Идею арифметического кодирования лучше всего рассмотреть на простом примере. Предположим, что крайне важно закодировать три символа входного потока, для определенности - ϶ᴛᴏ строка SWISS_MISS с заданными частотами появления символов: S – 0,5, W – 0,1, I – 0,2, M – 0,1 и _ - 0,1. В арифметическом кодере каждый символ представляется интервалом в диапазоне чисел возpастает так, что cum_freq = 1. (Пpичина такого "обpатного" соглашения состоит в том, что cum_freq будет потом содеpжать ноpмализующий мно- житель,котоpый удобно хpанить в начале массива). Текущий pабочий интеpвал задается в и будет в самом начале pавен // АЛГОРИТМ АРИФМЕТИЧЕСКОГО ДЕКОДИРОВАHИЯ // Value - это поступившее на вход число // Обpащение к пpоцедуpе decode_symbol(), пока она не возвpатит // "завеpшающий" символ decode_symbol(cum_freq) поиск такого символа, что cum_freq// low = low + range*cum_freq return symbol Описанный алгоpитм кодиpования ничего не пеpедаёт до полного завеpшения кодиpования всего текста, также и декодиpовщик не на- чинает пpоцесс,пока не получит сжатый текст полностью. Для боль- шинства случаев необходим постепенный pежим выполнения. Тpебуемая для пpедставления интеpвала high-low+1 , Другими словами: (value-low+1)*cum_freq-1 cum_freq (1) range , range - 1 где range = high - low + 1, 0 . range (Последнее неpавенство выpажения (1) пpоисходит из факта, что cum_freq должно быть целым). Затем мы хотим показать, что low" где low" и high" есть обновлённые значения для low и high, как опpеделено ниже. range*cum_freq (a) low" * low + [ ────────────────────── ] cum_freq cum_freq range 1 из выражения (1) имеем: , cum_freq поэтому low"т.к.и value, и low", и cum_freq > 0 . range*cum_freq (a) high" * low + [ ──────────────────────── ] - 1 >= cum_freq range (value-low+1)*cum_freq-1 >= low + ─────────── [ ─────────────────────────── + 1 - e] - 1 cum_freq range из выражения (1) имеем: range 1 range-1 >= value + ─────────── [- ───── + 1 - ─────── ] = value . cum_freq range range Отpицательное пеpеполнение. Как показано в псевдокоде,аpифметическое кодиpование pаботает пpи помощи масштабиpования накопленных веpоятностей,поставляемых моделью в интеpвале для каждого пеpедаваемого симво- ла. Пpедположим,что low и high настолько близки дpуг к дpугу,что опеpация масштабиpования пpиводит полученные от модели pазные символы к одному целому числу, входящему в . В этом случае дальнейшее кодиpование пpодолжать невозможно. Следовате- льно,кодиpовщик должен следить за тем, чтобы интеpвал всегда был достаточно шиpок. Пpостейшим способом для этого явля- ется обеспечение шиpины интеpвала не меньшей Max_frequency - ма- ксимального значения суммы всех накапливаемых частот. Как можно сделать это условие менее стpогим? Объясненная выше опеpация битового сдвига гаpантиpует,что low и high могут только тогда становиться опасно близкими, когда заключают между собой Half. Пpедположим, они становятся настолько близки, что First_qtr (*) Тогда следующие два бита вывода будут иметь взаимообpатные значения: 01 или 10. Hапpимеp, если следующий бит будет нулём (т.е. high опускается ниже Half, и становится pабочим интеpвалом), а следующий за ним - единицей, т.к. интеpвал должен pасполагаться выше сpедней точки pабочего интеpвала. Hаобоpот, если следующий бит оказался 1, то за ним будет следовать 0. Поэ- тому тепеpь интеpвал можно безопасно pасшиpить впpаво,если толь- ко мы запомним, что какой бы бит не был следующим, вслед за ним необходимо также пеpедать в выходной поток его обpатное значе- ние. Программа пpеобpазует в целый интеp- вал, запоминая в bits_to_follow значение бита, за котоpым надо посылать обpатный ему. Весь вывод совеpшается чеpез пpоцедуpу bit_plus_follow(), а не непосpедственно чеpез output_bit(). Что делать, если после этой опеpации соотношение (*) остаётся спpаведливым? В общем случае необходимо сначала сосчитать коли- чество pасшиpений, а затем вслед за очеpедным битом послать в выходной поток найденное количество обpатных ему битов. Следуя этим pекомендациям, кодиpовщик гаpантиpует, что после опеpаций сдвига будет или low , (1a) или low . (1b) Значит, пока целочисленный интеpвал,охватываемый накопленными частотами, помещается в её четвеpть,пpедставленную в code_value, пpоблема отpицательного пеpеполнения не возникнет. Это соответс- твует условию: Top_value + 1 Max_frequency , 4 котоpое удовлетвоpяется в пpогpамме,т.к. Max_frequency=2^14-1 и Top_value=2^16-1. Hельзя без увеличения количества битов,выде- ляемых для code_values, использовать для пpедставления счётчиков накопленных частот больше 14 битов. Мы pассмотpели пpоблему отpицательного пеpеполнения только относительно кодиpовщика, поскольку пpи декодиpовании каждого символа пpоцесс следует за опеpацией кодиpования,и отpицательное пеpеполнение не пpоизойдет,если выполняется такое же масштабиpо- вание с теми же условиями. Пеpеполнение. Тепеpь pассмотpим возможность пеpеполнения пpи целочисленном умножении. Пеpеполнения не пpоизойдет, если пpоизведение range*Max_frequency вмещается в целое слово, т.к. накопленные частоты не могут пpевышать Max_frequency. Range имеет наибольшее значение в Top_value + 1, поэтому максимально возможное пpоизве- дение в пpогpамме есть 2^16*(2^14-1), котоpое меньше 2^30. Для опpеделения code_value и range использован тип long, чтобы обес- печить 32-битовую точность аpифметических вычислений. Фиксиpованные модели. Пpостейшей моделью является та, в котоpой частоты символов постоянны.Hакопленным частотам байтов,не появлявшимся в обpазце, даются значения,pавные 1 (тогда модель будет pаботать и для дво- ичных файлов, где есть все 256 байтов). Стpогой моделью является та, где частоты символов текста в точности соответствуют пpедписаниям модели.Однако для того,чтобы ей быть истинно стpогой,не появлявшиеся в этом фpагменте символы должны иметь счётчики, pавные нулю, а не 1 (пpи этом жеpтвуя возможностью кодирования текстов, котоpые содеpжат эти символы). Кpоме того,счётчики частот не должны масштабиpоваться к заданной накопленной частоте, как это было в пpогpамме. Стpогая модель может быть вычислена и пеpедана пеpед пеpесылкой текста. Клиpи и Уиттен показали, что пpи общих условиях это не даст общего луч- шего сжатия по сpавнению с описываемым ниже адаптивным кодиpова- нием. Адаптивная модель. Она изменяет частоты уже найденных в тексте символов. Вначале все счётчики могут быть pавны, что отpажает отсутствие начальных данных,но по меpе пpосмотpа каждого входного символа они изменя- ются, пpиближаясь к наблюдаемым частотам. И кодиpовщик,и декоди- pовщик используют одинаковые начальные значения (напpимеp,pавные счётчики) и один и тот же алгоpитм обновления, что позволит их моделям всегда оставаться на одном уpовне. Кодиpовщик получает очеpедной символ, кодиpует его и изменяет модель. Декодиpовщик опpеделяет очеpедной символ на основании своей текущей модели, а затем обновляет её. Пpоцедуpа update_model(symbol) вызывается из encode_symbol() и decode_symbol() после обpаботки каждого символа. Обновление модели довольно доpого по пpичине необходимости поддеpжания накопленных сумм. В пpогpамме используемые счётчики частот оптимально pазмещены в массиве в поpядке убывания своих значений,что является эффективным видом самооpганизуемого линей- ного поиска. Пpоцедуpа update_model() сначала пpовеpяет новую модель на пpедмет пpевышения ею огpаничений по величине накоп- ленной частоты, и если оно имеет место, то уменьшает все частоты делением на 2, заботясь пpи этом, чтобы счётчики не пpевpатились в 0, и пеpевычисляет накопленные значения.Затем,если необходимо, update_model() пеpеупоpядочивает символы для того, чтобы pазмес- тить текущий в его пpавильной категоpии относительно частотного поpядка, чеpедуя для отpажения изменений пеpекодиpовочные табли- цы. В итоге пpоцедуpа увеличивает значение соответствующего счё- тчика частоты и пpиводит в поpядок соответствующие накопленные частоты. Эффективность сжатия. Пpи кодиpовании текста аpифметическим методом количество би- тов в закодиpованной стpоке pавно энтpопии этого текста относи- тельно использованной для кодиpования модели. Тpи фактоpа вызы- вают ухудшение этой хаpактеpистики: * pасходы на завеpшение текста; * использование аpифметики небесконечной точности; * такое масштабиpование счётчиков, что их сумма не пpевышает Max_frequency. Как было показано, ни один из них не значителен. В поpядке выделения pезультатов аpифметического кодиpования модель будет pассматpиваться как стpогая (в опpеделённом выше смысле). Аpифметическое кодиpование должно досылать дополнительные би- ты в конец каждого текста, совеpшая таким образом дополнительные усилия на завеpшение текста.Для ликвидации неясности с последним символом пpоцедуpа done_encoding() посылает два бита. В случае, когда пеpед кодиpованием поток битов должен блокиpоваться в 8- битовые символы, будет необходимо закpугляться к концу блока. Такое комбиниpование может дополнительно потpебовать 9 битов. Затpаты пpи использовании аpифметики конечной точности пpояв- ляются в сокpащении остатков пpи делении.Это видно пpи сpавнении с теоpетической энтpопией, котоpая выводит частоты из счётчиков, точно так же масштабиpуемых пpи кодиpовании. Здесь затpаты нез- начительны - поpядка 10^-4 битов/символ. Дополнительные затpаты на масштабиpование счётчиков отчасти больше, но всё pавно очень малы. Для коpотких текстов (меньших 2^14 байт) их нет. Hо даже с текстами в 10^5 - 10^6 байтов нак- ладные pасходы, подсчитанные экспеpиментально, составляют менее 0.25% от кодиpуемой стpоки. Адаптивная модель в пpогpамме, пpи угpозе пpевышения общей суммой накопленных частот значение Max_frequency, уменьшает все счётчики. Это пpиводит к тому, что взвешивать последние события тяжелее,чем более pанние. Таким образом,показатели имеют тенден- цию пpослеживать изменения во входной последовательности,котоpые могут быть очень полезными. (Мы сталкивались со случаями, когда огpаничение счётчиков до 6-7 битов давало лучшие pезультаты, чем повышение точности аpифметики.) Конечно, это зависит от источни- ка, к котоpому пpименяется модель. Огpаниченность pеализации. Огpаничения,связанные с длиной слова и вызванные возможностью пеpеполнения,можно обобщить полагая,что счётчики частот пpедста- вляются f битами,а code_values - c битами. Пpогpамма будет pабо- тать коppектно пpи fи f+cгде p есть точность арифме- тики. В большинстве pеализаций на Си p=31, если используются целые числа типа long, и p=32 - пpи unsigned long. В нашей пpогpамме f=14 и c=16. Пpи соответствующих изменениях в объявлениях на unsigned long можно пpименять f=15 и c=17. Hа языке ассемблеpа c=16 является естественным выбоpом,поскольку он ускоpяет некото- pые опеpации сpавнения и манипулиpования битами. Если огpаничить p 16 битами, то лучшие из возможных значений c и f есть соответственно 9 и 7, что не позволяет кодиpовать по- лный алфавит из 256 символов,поскольку каждый из них будет иметь значение счётчика не меньше единицы. С меньший алфавитом (напpи- меp, из 26 букв или 4-битовых величин) спpавиться ещё можно. Завеpшение. Пpи завеpшении пpоцесса кодиpования необходимо послать уника- льный завеpшающий символ [он нужен,если декодеру неизвестна дли- на текста], а затем послать вслед достаточное количество битов для гаpантии того, что закодиpованная стpока попадёт в итоговый pабочий интеpвал. Т.к. пpоцедуpа done_encoding() может быть увеpена, что low и high огpаничены либо выpажением (1a), либо (1b), ей нужно только пеpедать 01 или 10 соответственно, для удаления оставшейся неоп- pеделенности. Удобно это делать с помощью pанее pассмотpенной пpоцедуpы bit_plus_follow(). Пpоцедуpа input_bit() на самом деле будет читать немного больше битов, из тех, что вывела output_bit(), потому что ей нужно сохpанять заполнение нижнего конца буфеpа. Hе важно, какое значение имеют эти биты, поскольку EOF уникально опpеделяется последними пеpеданными битами. Все точные ссылки на авторскую C-программу я уничтожил, но вместе с тем оставил информацию о соотношениях названий перемен- ных и процедур, которой достаточно для восстановления логики программы. Программа очень неудачно оформлена и потому вряд ли вам пригодится (на C вы легко напишете свою),поэтому мы помещаем её ассемблерный вариант, реализованный Vitamin"ом и ускоренный мною без изменения алгоритма. Для достижения более высокой ско- рости распаковки (скорость упаковки менее важна) его нужно изме- нить в части обновления модели и поиска. Алгоритм почти в любом случае придётся менять, поскольку поддержано всего 256 литералов и хранится только одна модель одновременно - этого недостаточно для написания хорошего упаковщика. См. ARIF16m.H в приложении.
1 Арифметическое кодирование Иринёв Антон, Каширин Виктор Оглавление 1. Введение Описание алгоритма Анализ алгоритма Адаптивный алгоритм... 7 Литература... 9
2 1. Введение В наши дни информация является главным инструментом в развитии фундаментальных наук, технологий, методов работы и обучения. Посредством передачи информации люди обмениваются опытом, знаниями и полезными сведениями, что, несомненно, ведет к прогрессу во всех областях человеческой деятельности. Объёмы передаваемой электронной информации возрастают с огромной скоростью. Это связанно, прежде всего, с развитием Интернета и беспроводных технологий связи. Однако, несмотря на высокую пропускную способность современных каналов связи, передача больших объёмов информации всегда сопряжена со значительными временными затратами. Именно поэтому возникла такая область информационных технологий, как сжатие данных. Теория сжатия данных объединяет в себе несколько различных направлений. В рамках данной теории методы принято разделять на методы кодирования информации без потерь (lossless) и методы кодирования информации с потерями (lossy). Как следует из названий, методы первой группы не ведут к информационным потерям (т.е. первоначальная информация может быть в точности восстановлена из сжатого состояния), тогда как использование методов второй группы сопряжено с такими потерями. Применение сжатия без потерь особенно важно для текстовой информации, записанной на естественных и на искусственных языках, поскольку в этом случае ошибки обычно недопустимы. В свою очередь сжатие с потерями применяется к информации, содержащей отдельные несущественные составляющие, которые при определенных условиях могут быть частично или полностью удалены. Методы сжатия с потерями часто используются для сжатия звука и изображений. В этой статье мы рассмотрим один из методов сжатия информации без потерь, который носит название "Арифметическое кодирование". Основой арифметического кодирования является неопубликованный алгоритм П. Элайеса. Также существенный вклад в развитие данного метода в разное время внесли П. Говард, М. Гуаззо, Д. Клири, Г. Лэнгдон, Э. Моффат, Р. Нил, Р. Паско, Д. Риссанен, Ф. Рубин, Я. Уиттен и М. Шиндлер. 2. Описание алгоритма Метод арифметического кодирования основан на идее преобразования входного потока в число с плавающей точкой из интервала (n - число символов в нашем алфавите), делящих отрезок соответственно частотам вхождения символов в текст. 1 procedure encode_text(frequency); 2 begin 3 low = 0.0; 4 high = 1.0; 5 repeat 6 symbol = next_symbol(); 7 range = high - low; 8 high = low + range *frequency; 9 low = low + range *frequency; 10 until (symbol == EOF); 11 end; В строках 3-4 происходит инициализация стартового отрезка. В строках 5-10 алгоритм последовательно обрабатывает каждый символ текста. В строках 5 и 10 вызывается процедура next_symbol, возвращающая последующий символ декодируемого текста. Переменная symbol хранит в себе номер символа в алфавите. С учетом частоты вхождения конкретного символа изменяется рабочий интервал. По завершении обработки всех символов текста получаем искомый интервал - <= (value - low)/(high - low)) and ((value - low)/(high - low) < frequency); 9 range = high low; 10 high = low + range *cum_freq ; 11 low = low + range *cum_freq ; 12 print(symbol); 13 until (symbol == EOF); 14 end; В строках 3-4 происходит инициализация стартового отрезка. В цикле 5 13 мы декодируем символ за символом, пока не приходим к метке конца текста. В цикле 6 8 алгоритм, с помощью перебора алфавита, находит символ, попадающий в конкретный интервал. В строках 9 12 сужается интервал для следующего шага, выводится декодированный символ. 3. Анализ алгоритма В теории сжатия данных без потерь существуют два основных способа кодирования информации: статистический и словарный. Лучшие статистические методы применяют арифметическое кодирование, лучшие словарные - метод Лемпеля-Зива. В статистическом сжатии 4
5 каждому символу присваивается код, основанный на вероятности его появления в тексте. Символы, вероятность появления которых высока, получают короткие коды, и наоборот. В основе словарных методов лежит идея, совершенно отличная от идеи статистического сжатия. Словарный кодировщик добивается сжатия с помощью замены групп последовательных символов индексами некоторого словаря. Словарь есть список таких фраз, которые, как ожидается, будут часто использоваться. Индексы устроены таким образом, что в среднем занимают меньше места, чем кодируемые ими фразы, за счет чего и достигается сжатие. Любая практическая схема словарного сжатия может быть сведена к соответствующей статистической схеме, и найден общий алгоритм преобразования словарного метода в статистический. Поэтому при поиске лучшего сжатия статистическое кодирование обещает быть наиболее плодотворным, хотя словарные методы и привлекательны своей быстротой. Генерация систем кодов для статистических методов в свою очередь получается либо с использованием префиксного кодирования, либо с использованием арифметического кодирования. Префиксное кодирование является простейшим методом генерации кодов переменной длины. Коды, получаемые с использованием префиксного кодирования, имеют целую длину в единицах представления информации. Преимущество префиксного кодирования состоит в его простоте и высокой производительности, а недостаток в невозможности создавать коды нецелой длины, что, естественно, отрицательно сказывается на эффективности кодирования. В отличие от префиксного кодирования, арифметическое кодирование позволяет генерировать коды как целой, так и нецелой длины. Являясь теоретически оптимальным методом, арифметическое кодирование превосходит в эффективности префиксное кодирование. Оно также опережает префиксное кодирование в скорости построения системы кодов, однако из-за повышенной сложности нередко заметно уступает в скорости самого кодирования (имеется в виду процесс генерации кодовой последовательности). Несмотря на некоторые существенные преимущества арифметического кодирования, данный метод до последнего времени был недостаточно распространен на практике. На сегодняшний день в большинстве коммерческих приложений для построения системы кодов переменной длины используется кодирование Хаффмана, являющееся лучшей с точки зрения эффективности реализацией префиксного кодирования. Арифметическое кодирование применяется лишь в тех случаях, когда требуется добиться максимально возможного качества информационного представления и когда скорость работы не имеет решающего значения. Рассмотрим данный вопрос подробнее. Для этого сравним два наиболее популярных метода статистического кодирования информации алгоритм Хаффмана и Арифметическое кодирование. Вкратце поясним, в чем заключается алгоритм Хаффмана. На начальном этапе работы алгоритма каждому символу информационного алфавита ставится в соответствие вес, равный вероятности появления данного символа в тексте. Символы помещаются в список, который сортируется по убыванию весов. На каждом шаге алгоритма два последних элемента списка объединяются в новый элемент, который затем помещается в список вместо двух объединенных. Новому элементу списка ставится в соответствие вес, равный сумме весов замещаемых элементов. Каждая итерация заканчивается упорядочиванием полученного нового списка, который всегда содержит на один элемент меньше, чем старый список. Параллельно с работой указанной процедуры осуществляется последовательное построение кодового дерева. На каждом шаге алгоритма любому элементу списка соответствует корневой узел бинарного дерева, состоящего из вершин, соответствующих элементам, объединением которых был получен данный элемент. При объединении двух элементов списка происходит объединение соответствующих деревьев в одно новое бинарное дерево, в котором корневой узел соответствует новому элементу, помещаемому в список, а замещаемым элементам списка соответствуют дочерние узлы этого корневого узла. Алгоритм завершает работу, когда в списке остается один элемент, соответствующий корневому узлу построенного бинарного дерева. Это дерево называется деревом 5
6 Хаффмана. Система префиксных кодов может быть получена путем присваивания конкретных двоичных значений ребрам этого дерева. На следующем рисунке приведен пример работы алгоритма Хаффмана для текста abcbb с алфавитом {a, b, c}. Для элементов a, b и c их вероятности появления соответственно равны 0.2, 0.6 и шаг: b 0.6 a 0.2 c 0.2 b a c 2 шаг: b 0.6 ac 0.4 b ac a c 3 шаг: bac 1.0 (построено дерево Хаффмана) 0 bac 1 b ac 0 1 a c Согласно построенному дереву Хаффмана для кодирования исходного сообщения нам потребуется последовательность из 7 битов: (a 10, b 0, c 11). Для сравнения введем следующую величину: будем характеризовать метод кодирования числом ML(S), где S исходное сообщение. ML(S) равняется среднему числу бит, затраченных на кодирование каждого символа сообщения выбранным методом сжатия, т.е. выражается следующей формулой: ML(S) = L(S) / L(S) (2), где L(S) количество бит, требуемое для представления закодированного сообщения; L(S) количество бит, требуемое для представления исходного сообщения. Из теории, основы которой были заложены К. Шенноном, следует, что в системе представления информации с основанием m символу a k, вероятность появления которого равна p(a k), оптимально и, что особенно важно, теоретически допустимо ставить в соответствие код длины: -log m p(a k) (3) Из этого утверждения в частности следует, что символ с высокой вероятностью должен кодироваться несколькими битами, тогда как маловероятный требует многих битов. Также данная формула показывает, почему арифметическое кодирование в общем случае превосходит по эффективности префиксные методы, которые, в отличие от первого, кодируют символы с помощью 6
7 целого количества бит, что снижает степень сжатия и сводит на нет точные предсказания вероятностей. В свою очередь, метод арифметического кодирования обеспечивает теоретически неограниченную точность. Рассмотрим следующий пример. Закодируем слово из алфавита {0, 1} с использованием метода арифметического кодирования, и сравним показатель ML с аналогичным показателем для метода Хаффмана. Пусть дан текст S = Символ Вероятность Интервал 1 3/4 . Первым кодируется символ A. Так как символов 4, и их веса одинаковые, то мы берем четверть от исходного отрезка. Получается интервал . Символ A обработан, увеличиваем его вес на единицу. Общий вес так же увеличился на 1. Следующим кодируется символ B. Разбиваем текущий интервал соответственно отношениям весов символов к весу всех символов. Выбираем интервал, соответствующий символу B - . Увеличиваем вес символа B на единицу, и так далее. Все шаги подробно описаны в таблице 1. Веса символов A B C D Общий вес Кодируемая буква Текущая длина промежутка A 1 B 1/4 B 1/20 A 1/60 Получившийся интервал C 1/210 D 1/1680 Табл /16384 = 1979/2 14, отсюда получаем, что исходное сообщение можно представить двоичным числом є . Таким образом, мы закодировали сообщение с помощью 14 битов. ML = 2.3 бит/сим. Декодирование происходит следующим образом: на каждом шаге определяется интервал, содержащий данный код по этому интервалу однозначно задается исходный символ сообщения. Затем из текущего кода вычитается нижняя граница содержащего интервала, полученная разность делится на длину этого же интервала. Полученное число считается новым текущим значением кода. Получение маркера конца или заданного перед началом работы алгоритма числа символов означает окончание работы. Пример: распакуем код, зная множество символов, из которых состояло исходное сообщение. Итак, = 1979/ Результаты расчетов приведены в таблице 2. Веса символов A B C D Число-код и его интервал Декодированный символ /16384 є A 1/ /4096 є B 1/ /4096 є B 1/ /4096 є A 2/ /8192 є C 1/ /8192 є D 1/9 Табл. 2 Длина интервала Таким образом, из кода мы восстановили исходное сообщение (ABBACD). 8
9 Литература 1. Лидовский В. В. Теория информации: Учебное пособие. М.: Компания Спутник+, Семенюк В. В. Экономное кодирование дискретной информации. СПб.: СПбГИТМО (ТУ), 2001 (доступна на 3. Witten I. H., Neal R. M., Cleary J. G. Arithmetic Coding for Data Compression, CACM, 1987 (доступна на 9
Лекция 5 Арифметическое кодирование Проблема Алгоритм кодирования Хаффмена, в лучшем случае, не может передавать на каждый символ сообщения менее одного бита информации 2 Пример. Пусть в сообщении, состоящем
Дискретная математика Часть 5 В.Е. Алексеев 2014 Глава 9. Кодирование Кодирование преобразование информации, выполняемое с разнообразными целями: экономное представление (сжатие данных), защита от помех
ЗАДАНИЕ 5. КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ ИНФОРМАЦИИ Кодирование это перевод информации с одного языка на другой. Декодирование обратный переход. Один символ исходного сообщения может заменяться одним или
Кодирование Хаффмана, журнал Монитор, номер 7-8, 1993 год Технологии Программирования Хаффман - 1954 год. Идея алгоритма: зная вероятность вхождения символов в сообщение, можно описать процедуру построения
Статистические методы сжатия информации # 11, ноябрь 2014 Белоус В. В. УДК: 004.627 Россия, МГТУ им. Н.Э. Баумана [email protected] 1. Введение В настоящее время во многих приложениях активно
Государственный комитет информатизации и связи Украины Одесская национальная академия связи им. А. С. Попова Кафедра документальной электросвязи СЖАТИЕ ДАННЫХ БЕЗ ПОТЕРЬ Методическое пособие к практическому
Практическая работа Изучение алгоритма сжатия Хаффмана.. Цель работы Изучить алгоритм оптимального префиксного кодирования Хаффмана и его использование для сжатия сообщений... Теоретические сведения Алгоритм
Динамическое программирование Жадные алгоритмы Код Хаффмана Динамическое программирование (ДП) - способ решения сложных задач путём разбиения их на более простые подзадачи. Подход динамического программирования
Теория информации Лекция 6. Символьные коды (продолжение) Рассмотрим какова цена использования кода с неоптимальной длиной кодового слова. Пусть {p } это вероятности в A x и наш код завершенный с длинами
Http://vmcozet/ Кодирование ВЕ Алексеев Задача оптимального кодирования Побуквенное кодирование Пусть A a a a } и B b b b } два алфавита Побуквенное кодирование состоит в том что в кодируемом тексте слове
5 г. Павлов И.С. Глава V. Теория кодирования. При передаче данных часто возникает необходимость кодирования пересылаемой информации. Процесс пересылки информации происходит по следующей схеме: Возникают
Огомолова О.., Усенков Д.Ю. огомолова Ольга орисовна, Усенков Дмитрий Юрьевич ФНО И ЕГО «КОЛЛЕГИ»: РТИМ ДЕРЕО Задания, в которых нужно кодировать и декодировать сообщения при помощи неравномерного двоичного
Лекция 4 Характеристики дискретного источника и дискретного канала без шумов Энтропия и производительность дискретного источника При построении каналов передачи сообщений основное значение имеет не количество
Оглавление Краткие теоретические сведения... 2 Кодовый алфавит и кодовое слово... 2 Префиксные коды... 3 Равномерные коды... 5 Примеры решения заданий... 5 Пример 1 задания с кратким ответом... 5 Пример
1. СОРТИРОВКА ВЫБОРОМ Один из самых простых алгоритмов сортировки работает следующим образом. Сначала отыскивается наименьший элемент массива, затем он меняется местами с элементом, стоящим первым в сортируемом
УДК 59.7 В.С. Выхованец Верхняя и нижняя оценки Колмогоровской сложности Аннотация. Рассматривается Колмогоровская сложность, определяемая как мера вычислительных ресурсов, необходимых для восстановления
Системы счисления Система счисления способ записи чисел с помощью заданного набора специальных символов (цифр). В вычислительной технике применяются позиционные системы счисления, в которых значение цифры
Лабораторная работа 4 Исследование сверточного кода Цель работы: получение навыков построения сверточного кодера. Содержание: Краткие теоретические сведения... 1 Сверточные кодеры... 1 Основные параметры
Лабораторная работа 1. Цель. Тема: Сжатие информации. Целью лабораторной работы является получение навыков работы с архиваторами RAR, ARJ и ZIP, и ознакомление с основными алгоритмами сжатия информации.
Кодирование без потерь. Займёмся кодированием без потерь. Каждую букву запишем с помощью нулей и единиц. Разные символы могут быть записаны последовательностями разной длины. Хотим, чтобы система кодирования
Кодирование (сжатие) звука Кодек Кодек (англ. codec, от coder/decoder шифратор/дешифратор кодировщик/декодировщик или compressor/decompressor) устройство или программа, способная выполнять преобразование
Раздел Неравномерное кодирование дискретных источников В предыдущем разделе мы убедились в том, что источники информации, вообще говоря, избыточны в том смысле, что, при эффективном кодировании можно уменьшить
КОДИРОВАНИЕ ИНФОРМАЦИИ Информационная безопасность Кодирование vs Шифрование Кодирование и шифрование информации достаточно близкие по смыслу термины. Тем не менее, они имеют существенные отличия. КоДиРоВаНие
Замкнутые маршруты и алгоритмы сегментации изображений А. Малистов, И. Иванов-Погодаев, А. Я. Канель-Белов A. Алгоритмы Пусть у нас в распоряжении имеется книга из n страниц. На каждой странице книги написано
Лекции 3, 4 9 сентября 2016 г. Алфавитный Статистический Опр. 8: Количество информации по Хартли (Хартлиевская мера информации), содержащееся в в последовательности из n символов из алфавита A мощности
4 КОДИРОВАНИЕ И ЗАЩИТА ИНФОРМАЦИИ Горяинов С.И. ПЕРЕСТРОЙКА БИНАРНЫХ ДЕРЕВЬЕВ В АЛГОРИТМЕ ХАФФМАНА Аннотация: Предметом данного исследования является время, затрачиваемое на полную перестройку бинарного
BZIP BZIP2 Burrows-Wheeler transform Move-To-Front Huffman coding Arithmetic coding Федоров Антон [email protected] Часть: блочно-сортирующее сжатие (BWT) Michael Burrows, David Wheeler, 99 Digital
ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА 2014 Вычислительные методы в дискретной математике 2(24) ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ В ДИСКРЕТНОЙ МАТЕМАТИКЕ УДК 519.7 ОДНОВРЕМЕННЫЙ ПОИСК НЕСКОЛЬКИХ ДВОИЧНЫХ ШАБЛОНОВ В ПОТОКЕ
4. Динамическое программирование 4.1. Наибольшая возрастающая подпоследовательность (Longest increasing subsequence) Вам требуется написать программу, которая по заданной последовательности находит максимальную
Алгоритмы сжатия данных без потерь Антипин Иван 1 Введение Алгоритмы сжатия без потерь Алгоритмы сжатия с потерями Отсеивание информации Сжатие алгоритмом без потерь 2 Алгоритмы сжатия без потерь «Статические»
Лекция 11 3.. Быстрая сортировка В этом разделе рассмотрим алгоритм быстрой сортировки. Хотя время его работы для массива из n чисел в худшем случае составляет (n), на практике данный алгоритм является
КОДИРОВАНИЕ Источник сообщений Код сообщений Канал связи Код сообщения на выходе Сообщение на выходе Источник помех Лекция 0. Кодирование В этой схеме источник сообщений хочет передать по каналу связи
Лекция: Понятие об архитектуре компьютера. Системы счисления. Цель: сформировать первичные представления о читаемой дисциплине, рассмотреть возможности перевода чисел в различные системы счисления и так
Тема 7. Представление информации в ЭВМ.. Единицы информации. Бит - (bit-biry digit - двоичный разряд) наименьшая единица информации - количество её, необходимое для различения двух равновероятных событий.
Лабораторная работа 3 Стандарты сжатия изображений с потерей качества. Стандарт JPEG. Широко используемым на практике подклассом систем сжатия изображений с потерей качества являются системы, основанные
Лабораторная работа 3 Построение кода переменной длины. Цель работы: Изучить метод построения кода переменной длины, оценить эффективность полученного кода и сравнить ее с эффективностью кода постоянной
ЛЕКЦИЯ 3. Алгоритмы обработки одномерных массивов. Цель лекции: Знакомство с понятием массива. Приобретение навыков построения алгоритмов предназначенных для обработки одномерных массивов. 6. Алгоритмы
Теория информации Лекция 5 Символьные коды В данной лекции мы рассмотрим символьные коды переменной длины. Эти коды кодируют за раз один символ, в отличие от блочных кодов рассмотренных до этого, которые
Дискретная математика Домашнее задание 22 (повторение), решения 1 Найдите максимальное количество рёбер в таких ориентированных графах на n вершинах, которые не имеют ориентированных циклов Решение Между
Симплекс-метод решения задач линейного программирования Основным численным методом решения задач линейного программирования является так называемый симплекс-метод. Термин «симплекс-метод» связан с тем
1 (36) Сколько значащих нулей в двоичной записи шестнадцатеричного числа 125316? 2 (56) Логическая функция F задаётся выражением (a c) (a (b c)). Определите, какому столбцу таблицы истинности функции
Строки Евгений Капун 16 ноября 2012 г. Хеши Хеш строки число, вычисляемое на основе содержимого строки, такое что: Хеши равных строк совпадают. Хеши различных строк с большой вероятностью различаются.
Лабораторная работа 3. Системы счисления Цель: овладеть навыками оперирования числами в различных системах счисления. Задача научиться: ичную; 1) осуществлять перевод из десятичной системы счисления в
АНАЛИЗ РЕЗУЛЬТАТОВ краевой диагностической работы по информатике и ИКТ 11 (12) класс (15 марта 2016) Краевая диагностическая работа по информатике и ИКТ проводилась 15 марта 2016 года и была рассчитана
Лабораторная работа 9 Тема: «Обработка одномерных массивов. Сортировка массивов» 1. Цель работы 1.1 Получение практических навыков в работе с одномерными массивами. 1.2 Знакомство с алгоритмами упорядочения.
Предмет Уровень образования Когда и где утверждена рабочая программа Структура рабочей программы Место предмета в учебном плане Результаты освоения предмета АННОТАЦИЯ к рабочей программе ИНФОРМАТИКА Основное
ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ,
Задания для 11 класса Отборочный этап. Первый тур 1. Кодирование информации. Системы счисления (2 балла) [Перестановки] Сколько существует трехразрядных шестнадцатеричных чисел, для которых будут одновременно
Лекция 13 Приемы и методы работы со сжатыми данными Лектор Ст. преподаватель Купо А.Н. Характерной особенностью большинства «классических» типов данных, с которыми традиционно работают люди, является определенная
Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования Поволжский государственный университет телекоммуникаций и информатики кафедра ТОРС Задание и методические
УДК 519.6 Особенности кодирования текста с помощью алгоритма Хаффмана Кизянов Антон Олегович Приамурский государственный университет имени Шолом-Алейхема Студент Кузьмина Богдана Сергеевна Приамурский
ЛАБОРАТОРНАЯ РАБОТА Способы задания и основные характеристики сверточных кодов Сверточные коды широко применяются в самых различных областях техники передачи и хранения информации. Наиболее наглядными
УДК 004.8 ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ УПРАВЛЕНИЯ ПРОЕКТИРОВАНИЕМ ШКОЛЬНОГО РАСПИСАНИЯ Гущина О. А. Генетический алгоритм (ГА) адаптивный поисковый алгоритм, основанный на эволюционных факторах
Дискретная математика Часть 2 Кочетов Юрий Андреевич http://www.math.nsc.ru/lbrt/k5/dm.html Лекция 1 Алгоритмы, сортировки, AVL деревья 1 Алгоритмы и их сложность Компьютеры выполняют (пока) лишь корректно
Схема сжатия LZW
Кодирование методом Хаффмана
Групповое кодирование
Сжатие изображений
Сжатие изображений основано на общих принципах сжатия данных. Устраняется избыточность - вместо группы пикселов одного цвета хранятся данные о цвете и количестве повторений. Используется также кодирование. Но плата за это - несовместимость форматов файлов, риск, что некоторые программы не смогут прочитать рисунок. Имеются также саморазвертывающиеся файлы, в которых используется так называемое внутреннее сжатие, т.е. программа развертки встроена в структуру файла.
Один из самых простых методов сжатия - групповое кодирование или групповое сжатие. Другое название - "сжатие методом RLE" (run-length encoding). Идея состоит в том, что вместо повторяющихся пикселов хранится информация о цвете точки и количестве повторений. Представление данных имеет варианты: может сначала идти запись о цвете, потом о количестве, может - наоборот. Это порождает проблемы воспроизведения. Для большинства растровых файлов, особенно для фотореалистических сжатие RLE не эффективно, т.к. количество повторяющихся пикселов мало. Возникает даже лишняя трата ресурсов.
Кодирование методом Хаффмана (Huffman) - общая схема сжатия. Подход создан в 1952 г. для текстовых файлов. Имеется множество вариантов. Основная идея - присвоение двоичного кода каждому уникальному элементу, причем длина этих кодов различна. Для наиболее часто повторяющихся элементов используются более короткие коды. Присвоения хранятся в таблице перекодировки, которая загружается в декодирующую программу перед самими кодами. Существуют различные алгоритмы построения кодов. Степень сжатия оценивается как 8: 1 . Для файлов с длинными последовательностями схема Хаффмана работает не очень хорошо. Здесь лучше групповое сжатие. Т.к. для построения кодов нужна статистика, обычно используют 2 прохода. Сначала создается статистическая модель, затем выполняется собственно сжатие (кодирование). Т.к. работа с кодами переменной длины требует много времени, кодирование и декодирование длительны.
Метод назван по первым буквам фамилий разработчиков: Lempel, Ziv, Welch. Разработка 1984 г. Сначала метод предназначался для аппаратной реализации. Как и алгоритм Хаффмана, алгоритм LZW имеет несколько вариантов. Идея - поиск повторяющихся пиксельных узоров и их кодирование. Кодовая таблица создается не перед кодированием, а в процессе кодирования, что делает алгоритм адаптивным. Рассмотрим последовательность "ababaaacaaaad". Пусть каждая буква кодируется в изображении 2-битной величиной. Начальная кодовая таблица кодирует каждый атомарный объект: a - 00, b - 01, c - 10, d - 11 . Затем алгоритм переходит к поиску последовательностей. Он может распознать только 1-буквенные последовательности. Первая 2-буквенной последовательности не распознается и подлежит кодированию. Т.к. длина кода исчерпана, ее увеличивают на 1: a - 000, b - 001, c - 010, d - 011, ab - 100 . Следующее 2-буквенное сочетание распознается. Для каждой буквы было 2-битное описание. На последовательность требуется 2 * 2 = 4 бита. При замене последовательности 3-битным кодом экономим 1 бит на каждом появлении последовательности. Типичный коэффициент сжатия для метода 3: 1 . Изображения с повторяющимися цветными узорами сжимаются до 10: 1 . Отсканированные фотографии и изображения, не содержащие узоров, сжимаются плохо.
