Как найти количество информации в файле - Исправление недочетов и поиск решений вместе с Examum.ru

Мы ежедневно работаем с информацией из разных источников. При этом каждый из нас имеет некоторые интуитивные представления о том, что означает, что один источник является для нас более информативным, чем другой. Однако далеко не всегда понятно, как это правильно определить формально. Не всегда большое количество текста означает большое количество информации. Например, среди СМИ распространена практика, когда короткое сообщение из ленты информационного агентства переписывают в большую новость, но при этом не добавляют никакой «новой информации». Или другой пример: рассмотрим текстовый файл с романом Л.Н. Толстого «Война и мир» в кодировке UTF-8. Его размер — 3.2 Мб. Сколько информации содержится в этом файле? Изменится ли это количество, если файл перекодировать в другую кодировку? А если заархивировать? Сколько информации вы получите, если прочитаете этот файл? А если прочитаете его второй раз?

По мотивам открытой лекции для Computer Science центра рассказываю о том, как можно математически подойти к определению понятия «количество информации».

В классической статье А.Н. Колмогорова «Три подхода к определению понятия количества информации» (1965) рассматривают три способа это сделать:

комбинаторный (информация по Хартли),
вероятностный (энтропия Шеннона),
алгоритмический (колмогоровская сложность).

Мы будем следовать этому плану.

Комбинаторный подход: информация по Хартли

Мы начнём самого простого и естественного подхода, предложенного Хартли в 1928 году.

Пусть задано некоторое конечное множество . Количеством информации в будем называть .

Можно интерпретировать это определение следующим образом: нам нужно chi(A) битов для описания элемента из .

Почему мы используем биты? Можно использовать и другие единицы измерения, например, триты или байты, но тогда нужно изменить основание логарифма на 3 или 256, соответственно. В дальшейшем все логарифмы будут по основанию 2.

Этого определения уже достаточно для того, чтобы измерить количество информации в некотором сообщении. Пусть про xin A стало известно, что xin B . Теперь нам достаточно битов для описания , таким образом нам сообщили битов информации.

Пример

Загадано целое число от до . Нам сообщили, что делится на . Сколько информации нам сообщили?

Воспользуемся рассуждением выше.

$log_2 1000 - log_2 166 = log_2 frac{1000}{166} approx 2.59 text{битов.}$

(Тот факт, что некоторое сообщение может содержать нецелое количество битов, может показаться немного неожиданным.)

Можно ещё сказать, что сообщение, уменшающее пространство поиска в alpha раз приносит битов информации. В данном примере пространство поиска уменьшилось в 1000/166 раз.

Интересно, что одного этого определения уже достаточно для того, чтобы решать довольно нетривиальные задачи.

Применение: цена информации

Загадано целое число от до . Разрешается задавать любые вопросы на ДА/НЕТ. Если ответ на вопрос «ДА», то мы должны заплатить рубль, если ответ «НЕТ» — два рубля. Сколько нужно заплатить для отгадывания числа ?

Любой вопрос можно сформулировать как вопрос о принадлежности некоторому множеству, поэтому мы будем считать, что все вопросы имеют вид « xin T ?» для некоторого множества .

Каким образом нужно задавать вопросы? Нам бы хотелось, чтобы вне зависимости от ответа цена за бит информации была постоянной. Другими словами, в случае ответа «НЕТ» и заплатив два рубля мы должны узнать в два больше информации, чем при ответе «ДА». Давайте запишем это формально.

Потребуем, чтобы

Пусть , тогда . Подставляем и получаем, что

Это эквивалентно квадратному уравнению Положительный корень этого уравнения . Таким образом, при любом ответе мы заплатим рублей за бит информации, а в сумме мы заплатим примерно clog n рублей (с точностью до округления).

Осталось понять, как выбирать такие множества . Будем выбирать в качестве непрерывные отрезки прямой. Пусть нам известно, что принадлежит отрезку [a,b] (изначально это отрезок [1,n] ). В следующего множества возмём отрезок , где. Тогда за каждый заплаченный рубль текущий отрезок будет уменьшаться в раз. Когда длина отрезка станет меньше единицы, мы однозначно определим . Поэтому цена отгадывания не будет превосходить

Приведённое рассуждение доказывает только верхнюю оценку. Можно доказать и нижнюю оценку: для любого способа задавать вопросы будет такое число , для отгадывания которого придётся заплатить не менее рублей.

Вероятностный подход: энтропия Шеннона

Вероятностный подход, предложенный Клодом Шенноном в 1948 году, обобщает определение Хартли на случай, когда не все элементы множества являются равнозначными. Вместо множества в этом подходе мы будем рассматривать вероятностное распределение на множестве и оценивать среднее по распределению количество информации, которое содержит случайная величина.

Пусть задана случайная величина , принимающая различных значений с вероятностями . Энтропия Шеннона случайной величины определяется как

$H(X) = sum_{i=1}^k p_icdotlogfrac1p_i.$

(По непрерывности тут нужно доопределить $0cdot logfrac10 = 0$ .)

Энтропия Шеннона оценивает среднее количество информации (математическое ожидание), которое содержится в значениях случайной величины.

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

Я попробую объяснить происхождение этой формулы как обобщение информации по Хартли. Нам бы хотелось, чтобы это определение согласовывалось с определением Хартли, т.е. должны выполняться следующие «граничные условия»:

Будем искать в виде математического ожидания количества информации, которую мы получаем от каждого возможного значения .

$H(X) = sum_i p_icdot text{(информация в событии $X=a_i$)}.$

Как оценить, сколько информации содержится в событии X = a_i ? Пусть — всё пространство элементарных исходов. Тогда событие X = a_i соответствует множеству элементарных исходов меры p_i . Если произошло событие X = a_i , то размер множества согласованных с этим событием элементарных исходов уменьшается с |U| до , т.е. событие X = a_i сообщает нам битов информации. Тут мы пользуемся тем, что количество информации в сообщении, которое уменьшает размер пространство поиска в 1/p_i раз приносит битов информации.

Примеры

Свойства энтропии Шеннона

Для случайной величины , принимающей значений с вероятностями , выполняются следующие соотношения.

.
распределение вырождено.
.
распределение равномерно.

Чем распределение ближе к равномерному, тем больше энтропия Шеннона.

Энтропия пары

Понятие энтропии Шеннона можно обобщить для пары случайных величин. Аналогично это обощается для тройки, четвёрки и т.д.

Пусть совместно распределённые случайные величины и принимают значения и , соответственно. Энтропия пары случайных величин и определяется следующим соотношением:

$H(X,Y) = sum_{i=1}^ksum_{j=1}^mPr[X = a_i, Y=b_j]cdot logfrac{1}{Pr[X = a_i, Y = b_j]}.$

Примеры

Рассмотрим эксперимент с выбрасыванием двух игральных кубиков — синего и красного.

Свойства энтропии Шеннона пары случайных величин

Для энтропии пары выполняются следующие свойства.

Условная энтропия Шеннона

Теперь давайте научимся вычислять условную энтропию одной случайной величины относительно другой.

Условная энтропия относительно определяется следующим соотношением:

Примеры

Рассмотрим снова примеры про два игральных кубика.

Свойства условной энтропии

Условная энтропия обладает следующими свойствами

Взаимная информация

Ещё одна информационная величина, которую мы введём в этом разделе — это взаимная информация двух случайных величин.

Информация в о величине (взаимная информация случайных величин и ) определяется следующим соотношением

Примеры

И снова обратимся к примерам с двумя игральными кубиками.

Свойства взаимной информации

Выполняются следующие соотношения.

. Т.е. определение взаимной информации симметрично и его можно переписать так:

Или так: .
и .
.
.

Все информационные величины, которые мы определили к этому моменту можно проиллюстрировать при помощи кругов Эйлера.

Мы пойдём дальше и рассмотрим информационную величину, зависящую от трёх случайных величин.

Пусть , и совместно распределены. Информация в о при условии определяется следующим соотношением:

Свойства такие же как и обычной взаимной информации, нужно только добавить соответствующее условие ко всем членам.

Всё, что мы успели определить можно удобно проиллюстрировать при помощи трёх кругов Эйлера.

Из этой иллюстрации можно вывести все определения и соотношения на информационные величины.

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

Рассмотрим треугольник в пересечении всех трёх кругов H(X) , H(Y) и H(Z) . Этот треугольник соответствуют взаимной информации трёх случайных величин . Проблема с этой информационной величиной заключается в том, что ей не удаётся придать какой-то «физический» смысл. Более того, в отличие от всех остальных величин на картинке может быть отрицательной!

Рассмотрим пример трёх случайных величин равномерно распределённых на {0,1} . Пусть и будут независимы, а . Легко проверить, что . При этом . В то же время . Получается следующая картинка.

Мы знаем, что . При этом . Получается, что a=b=c=1 , а d=-1 , т.е. для таких случайных величин.

Применение энтропии Шеннона: кодирование

В этом разделе мы обсудим, как энтропия Шеннона возникает в теории кодирования. Будем рассматривать коды, которые кодируют каждый символ по отдельности.

Пусть задан алфавит Sigma . Код — это отображение из Sigma в ${0,1}^*$ . Код называется однозначно декодируемым, если любое сообщение, полученное применением к символам некоторого текста, декодируется однозначно.

Код называется префиксным (prefix-free), если нет двух символов alpha и beta таких, что является префиксом C(beta) .

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

Теорема [Шеннон]. Для любого однозначно декодируемого кода существует префиксный код с теми же длинами кодов символов.

Таким образом для изучения однозначно декодируемых кодов достаточно рассматривать только префиксные коды.

Задача об оптимальном кодировании.
Дан текст . Нужно найти такой код , что

$sum_{i=1}^n |C(a_i)| to min.$

Пусть $Sigma = {alpha_1,alpha_2,dotsc,alpha_k}$ . Обозначим через f_i частоту, с которой символ alpha_i встречается в . Тогда выражение выше можно переписать как

$nsum_{i=1}^k f_icdot |C(alpha_i)| to min.$

Следующая теорема могла встречаться вам в курсе алгоритмов.

Теорема [Хаффман]. Код Хаффмана, построенный по , является оптимальным префиксным кодом.

Алгоритм Хаффмана по набору частот эффективно строит оптимальный код для задачи оптимального кодирования.

Связь с энтропией

Имеют место две следующие оценки.

Теорема [Шеннон]. Для любого однозначно декодируемого кода выполняется

$sum_{i=1}^k f_icdot|C(alpha_i)|ge sum_{i=1}^n f_icdot logfrac1{f_i}.$

Теорема [Шеннон]. Для любых значений ${f_1,f_2,dotsc,f_k}$ существует префиксный код , такой что

$sum_{i=1}^n f_icdot|C(alpha_i)|le sum_{i=1}^n f_icdot logfrac1{f_i} + 1.$

Рассмотрим случайную величину , равномерно распределённую на символах текста . Получим, что $H(X) = f_icdot logfrac1{f_i}$ . Таким образом, эти две теоремы задают оценку на среднюю длину кода символа при оптимальном кодировании, т.е. и для кодирования Хаффмана.

$H(X) le sum_{i=1}^n f_icdot|C(alpha_i)|le H(X) + 1.$

Следовательно, длину кода Хаффмана текста можно оценить, как

Применение энтропии Шеннона: шифрования с закрытым ключом

Рассмотрим простейшую схему шифрования с закрытым ключом. Шифрование сообщения с ключом шифрования выполняется при помощи алгоритма шифрования . В результате получается шифрограмма . Зная получатель шифрограммы восстанавливает исходное сообщение : .

Мы будем анализировать эту схему с помощью аппарата энтропии Шеннона. Пусть и являются случайными величинами. Противник не знает и , но знает , которая так же является случайной величиной.

Для совершенной схемы шифрования (perfect secrecy) выполняются следующие соотношения:

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

Теорема [Шеннон]. , даже если условие нарушается (т.е. алгоритм использует случайные биты).

Эта теорема утверждает, что для совершенной схемы шифрования длина ключа должна быть не менее длины сообщения. Другими словами, если вы хотите зашифровать и передать своему знакомому файл размера 1Гб, то для этого вы заранее должны встретиться и обменяться закрытым ключом размера не менее 1Гб. И конечно, этот ключ можно использовать только однажды. Таким образом, самая оптимальная совершенная схема шифрования — это «одноразовый блокнот», в котором длина ключа совпадает с длиной сообщения.

Если же вы используете ключ, который короче пересылаемого сообщения, то шифрограмма раскрывает некоторую информацию о зашифрованном сообщении. Причём количество этой информации можно оценить, как разницу между энтропией сообщения и энтропией ключа. Если вы используете пароль из 10 символов при пересылке файла размера 1Гб, то вы разглашаете примерно 1Гб – 10 байт.

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

Современная криптография строится на предположении об ограниченности вычислительных возможностей противника. Тут есть свои проблемы, а именно отсутствие математического доказательства криптографической стойкости (все доказательства строятся на различных предположениях), так что может оказаться, что вся эта криптография бесполезна (подробнее можно почитать в статье о мирах Рассела Импальяццо, которая переведена на хабре), но это уже совсем другая история.

Доказательство. Нарисуем картинку для трёх случайных величин и отметим то, что нам известно.

.
, следовательно , а значит .
(по свойству взаимной информации), следовательно , а значит .
. Таким образом,

В доказательстве мы действительно не воспользовались тем, что .

Алгоритмический подход: колмогоровская сложность

Подход Шеннона хорош для случайных величин, но если мы попробуем применить его к текстам, то выходит, что количество информации в тексте зависит только от частот символов, но не зависит от их порядка. При таком подходе получается, что в «Войне и мире» и в тексте, который получается сортировкой всех знаков в «Войне и мире», содержится одинаковое количество информации. Колмогоров предложил подход, позволяющий измерять количество информации в конкретных объектах (строках), а не в случайных величинах.

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

Нам потребуется зафиксировать способ описания битовой строки. Чтобы не углубляться в рассуждения про машины Тьюринга, мы будем описывать строки на языках программирования. Нужно только сделать оговорку, что программы на этих языках будут запускаться на компьютере с неограниченным объёмом оперативной памяти (иначе мы получили бы более слабую вычислительную модель, чем машина Тьюринга).

Сложностью K_F(x) строки относительно языка программирования называется длина кратчайшей программы, которая выводит .

Таким образом сложность «Войны и мира» относительноя языка Python — это длина кратчайшей программы на Python, которая печатает текст «Войны и мира». Естественным образом сложность отсортированной версии «Войны и мира» относительно языка Python получится значительно меньше, т.к. её можно предварительно закодировать при помощи RLE.

Сравнение языков программирования

Дальше нам потребуется научиться любимой забаве всех программистов — сравнению языков программирования.

Будем говорить, что язык не хуже языка программирования и обозначать Fprec G , если существует константа c_G такая, что для для всех $xin{0,1}^*$ выполняется

Исходя из этого определения получается, что язык Python не хуже (!) этого вашего Haskell! И я это докажу. В качестве константы $c_text{Haskell}$ мы возьмём длину реализации интепретатора Haskell на Python. Таким образом, любая программа на Haskell переделывается в программу на Python просто дописыванием к ней интерпретатора Haskell на Python.

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

Теорема [Соломонова-Колмогорова]. Существует способ описания (язык программирования) такой, что для любого другого способа описания выполняется Uprec F .

И да, некоторые уже наверное догадались, что — это JavaScript. Или любой другой Тьюринг полный язык программирования.

Это приводит нас к следующему определению, предложенному Колмогоровым в 1965 году.

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

Важно понимать, что при разных выборах оптимального языка программирования колмогоровская сложность будет отличаться, но только на константу. Для любых двух оптимальных языков программирования F_1 и F_2 выполняется и , т.е. существует такая константа , что $|K_{F_1} - K_{F_2}| le c.$ Это объясняет, почему в этой науке аддитивные константы принято игнорировать.

При этом для конкретной строки и конкретного выбора колмогоровская сложность определена однозначно.

Свойства колмогоровской сложности

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

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

Примеры

Несжимаемые строки

Важнейшее свойство колмогоровской сложности заключается в существовании сложных (несжимаемых строк). Проверьте себя и попробуйте объяснить, почему не бывает идеальных архиваторов, которые умели бы сжимать любые файлы хотя бы на 1 байт, и при этом позволяли бы однозначно разархивировать результат.

В терминах колмогоровской сложности это можно сформулировать так.

Вопрос. Существует ли такая длина строки , что для любой строки $xin{0,1}^n$ колмогоровская сложность меньше ?

Следующая теорема даёт отрицательный ответ на этот вопрос.

Теорема. Для любого существует $xin{0,1}^n$ такой, что .

Доказательство. Битовых строк длины всего 2^n . Число строк сложности меньше не превосходит число программ длины меньше , т.е. таких программ не больше чем

$1+2+dotsb +2^{n-1} = 2^n - 1 < 2^n.$

Таким образом, для какой-то строки гарантированно не хватит программы.

Верна и более сильная теорема.

Теорема. Существует c > 0 такое, что для 99% слов длины верно

Другими словами, почти все строки длины имеют почти максимальную сложность.

Колмогоровская сложность: вычислимость

В этом разделе мы поговорим про вычислимость колмогоровской сложности. Я не буду давать формально определение вычислимости, а буду опираться на интуитивные предствления читателей.

Теорема. Не существует программы, которая по двоичной записи числа выводит строку , такую что .

Эта теорема говорит о том, что не существует программы-генератора, которая умела бы генерировать сложные строки по запросу.

Доказательство. Проведём доказетельство от противного. Пусть такая программа существует и . Тогда с одной стороны сложность не меньше , а с другой стороны мы можем описать при помощи log n битов и кода программы.

Это приводит нас к противоречию, т.к. при достаточно больших значениях неизбежно станет больше, чем .

Как следствие мы получаем невычислимость колмогоровской сложности.

Следствие. Отображение не является вычислимым.

Опять же, предположим, что это нет так и существует программа , которая по строку вычисляет её колмогоровскую сложность. Тогда на основе программы можно реализовать программу из теоремы выше: она будет перебирать все строки длины не более и находить лексикографически первую, для которой сложность будет не меньше . А мы уже доказали, что такой программы не существует.

Связь с энтропией Шеннона

Теорема. Пусть длины содержит pcdot n единиц и нулей, тогда

$K(x)le left(pcdotlogfrac1p + (1-p)cdotlogfrac{1}{1-p}right)cdot n + O(log n).$

Я надеюсь, что вы уже узнали энтропию Шеннона для случайной величины с двумя значениями с вероятностями и 1-p .

Для колмогоровской сложности можно проделать весь путь, который мы проделали для энтропии Шеннона: определить условную колмогоровскую сложность, сложность пары строк, взаимную информацию и условную взаимную информацию и т.д. При этом формулы будут повторять формулы для энтропии Шеннона с точностью до . Однако это тема для отдельной статьи.

Применение колмогоровской сложности: бесконечность множества простых чисел

Начнём с довольно игрушечного применения. С помощью колмогоровской сложности мы докажем следующую теорему, знакомую нам со школы.

Теорема. Простых чисел бесконечно много.

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

Доказательство. Проведём доказательство от обратного. Пусть существует всего простых чисел: . Тогда любое натуральное раскладывается на степени простых:

$x = p_1^{k_1}cdot p_2^{k_2}cdotdotsmcdot p_m^{k_m},$

т.е. определяется набором степеней . Каждое , т.е. задаётся битами. Поэтому любое можно задать при помощи битов (помним, что — это константа).

Теперь воспользуемся теоремой о существовании несжимаемых строк. Как следствие, мы можем заключить, что существуют -битовые числа сложности не менее (можно взять сложную строку и приписать в начало единицу). Получается, что сложное число можно задать при помощи небольшого числа битов.

Противоречие.

Применение колмогоровской сложности: алгоритмическая случайность

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

Пусть в лаборатории живёт обезьянка, которую научили печатать на печатной машинке так, что каждую кнопку она нажимает с одинаковой вероятность. Вам предлагается посмотреть на лист печатного текста и сказать, верите ли вы, что его напечатала эта обезьянка. Вы смотрите на лист и видите, что это первая страница «Гамлета» Шекспира. Поверите ли вы? Очевидно, что нет. Хорошо, а если это не Шекспир, а, скажем, текст детектива Дарьи Донцовой? Скорей всего тоже не поверите. А если просто какой-то набор русских слов? Опять же, очень сомневаюсь, что вы поверите.

Внимание, вопрос. А как объяснить, почему вы не верите? Давайте для простоты считать, что на странице помещается 2000 знаков и всего на машинке есть 80 знаков. Вы можете резонно заметить, что вероятность того, что обезьянка случайным образом породила текст «Гамлета» порядка $1/80^{2000}$ , что астрономически мало. Это верно.

Теперь предположим, что вам показали текст, который вас устроил (он с вашей точки зрения будет похож на «случайный»). Но ведь вероятность его появления тоже будет порядка $1/80^{2000}$ . Как же вы определяете, что один текст выглядит «случайным», а другой — не выглядит?

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

Это обобщается на случай бесконечных последовательностей. Пусть . Как определить понятие случайной последовательности?

(неформальное определение)
Последовательность случайна по Мартину–Лёфу, если каждый её префикс является несжимаемым.

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

Свойства случайных последовательностей

Почти все последовательности являются случайными по Мартину–Лёфу, а мера неслучайных равна .
Всякая случайная по Мартину-Лёфу последовательность невычислима.
Если случайная по Мартин-Лёфу, то

$lim_{ntoinfty} frac{text{число единиц в префиксе длины n}}{n} = frac12.$

Заключение

Если вам интересно изучить эту тему подробнее, то я рекомендую обратиться к следующим источникам.

Верещагин Н.К., Щепин Е.В. Информация, кодирование и предсказание. МЦНМО. (нет в свободном доступе, но pdf продаётся за копейки)
В.А. Успенский, А.Х. Шень, Н.К. Верещагин. Колмогоровская сложность и алгоритмическая случайность.
Курс «Введение в теорию информации» А.Е. Ромащенко в Computer Science клубе.

Если вам интересны подобные материалы, подписывайтесь в соцсетях на CS клуб и CS центр, а так же на наши каналы на youtube: CS клуб, CS центр.

Источник

Как найти информационный объем

В курсе информатики визуальный, текстовый, графический и другие виды информации представлены в двоичном коде. Это «машинный язык» — последовательность нулей и единиц. Информационный объем позволяет сравнивать количество двоичной информации, входящей в состав разных носителей. Для примера можно рассмотреть, как вычисляются объемы текста и графики.

Инструкция

Для вычисления информационного объема текста, из которого состоит книга, определите начальные данные. Вы должны знать количество страниц в книге, среднее количество строк текста на каждой странице и число символов с пробелами в каждой строке текста. Пусть книга содержит 150 страниц, по 40 строк на странице, по 60 символов в строке.

Найдите количество символов в книге: перемножьте данные первого шага. 150 страниц * 40 строк * 60 символов = 360 тыс. символов в книге.

Определите информационный объем книги, исходя из того, что один символ весит один байт. 360 тысяч символов * 1 байт = 360 тысяч байт.

Перейдите к более крупным единицам измерения: 1 Кб (килобайт) = 1024 байт, 1 Мб (мегабайт) = 1024 Кб. Тогда 360 тысяч байт / 1024 = 351,56 Кб или 351,56 Кб / 1024 = 0,34 Мб.

Чтобы найти информационный объем графического файла, также определите начальные данные. Пусть изображение 10×10 см получено с помощью сканера. Надо знать разрешающую способность устройства — для примера, 600 dpi — и глубину цвета. Последнее значение, так же для примера, можно взять 32 бита.

Выразите разрешающую способность сканера в точках на см. 600 dpi = 600 точек на дюйм. 1 дюйм = 2,54 см. Тогда 600 / 2,54 = 236 точек на см.

Найдите размер изображения в точках. 10 см = 10 * 236 точек на см = 2360 точек. Тогда размер картинки = 10×10 см = 2360×2360 точек.

Вычислите общее количество точек, из которых состоит изображение. 2360 * 2360 = 5569600 штук.

Рассчитайте информационный объем полученного графического файла. Для этого умножьте глубину цвета на результат восьмого шага. 32 бита * 5569600 штук = 178227200 бит.

Перейдите к более крупным единицам измерения: 1 байт = 8 бит, 1 Кб (килобайт) = 1024 байта и т.д. 178227200 бит / 8 = 22278400 байт, или 22278400 байт / 1024 = 21756 Кб, или 21756 Кб / 1024 = 21 Мб. Из-за округления результаты получаются примерными.

Источники:

Нахождение информационного объема графического файла
определите информационный объём

Войти на сайт

или

Забыли пароль?
Еще не зарегистрированы?

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Источник

Вопрос о том, как грамотно определить размер файла, может встать перед каждым пользователем. Для этого не обязательно быть программистом или системным администратором. Определение размеров документации в электронном виде – базовая операция. С ней должен познакомиться каждый ПК-пользователь.

В данной статье будет рассказано о том, как определять «габариты» файла. Предстоит разобраться не только в азах соответствующего процесса, но и в действующих единицах измерения.

Размер документа – это…

Размер файла – объем пространства, которое занимает соответствующая электронная документация на устройстве. А именно – в его памяти.

Зависит размер файла или папки от количества информации, которая находится внутри. Узнать подобные данные удается несколькими методами. Каждый пользователь ПК может выбрать оптимальное для себя решение.

Единицы измерения

Можно выразить размеры файла в байтах. Это – классическая единица измерения. Она является наименьшей единицей электронных сведений.

Основная масса материалов на компьютере измеряется в килобайтах, а не в байтах. Узнать объем документа, файла или папки предлагается при помощи МБ (мегабайтов) и ГБ (гигабайты). Современные компьютеры также работают с ТБ (терабайтами).

Здесь рекомендуется запомнить следующее:

1 байт – 8 бит;
единица в килобайтах – это 1024 в байтах;
1 Мб – 1024 Кб;
1 ГБ – 1024 Мб;
1 ТБ – 1024 ГБ.

Эти же единицы измерения применяются для обозначения имеющегося пространства на устройстве. Не только занятого, но и свободного.

Варианты определения

Посмотреть (узнать) объем занятого электронными материалами сведения можно различными способами. Далее будут рассмотрены такие приемы:

как узнать объем единственного файлика;
работа с группами документов;
сколько места занимает папка;
объем носителя информации.

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

Единственный документ

Сначала стоит выяснить, как узнать размер заданного файла. Это – элементарная операция. Определяется объем системой автоматически.

Чтобы справиться с задачей, нужно:

Перейти на устройстве к файлу, с которым планируется дальнейшая работа.
Выделить его. Для этого – кликнуть ЛКМ по характерной иконке.
Нажать ПКМ. Откроется большое меню.
Переключиться в раздел «Свойства».
Во вкладке «Общее» посмотреть интересующую информацию. Она будет выражена в байтах и килобайтах. Если документация объемная – мегабайтах и гигабайтах.

Определить занятый объем на устройстве можно иначе. Для этого достаточно выделить документацию и навести на нее курсор. Немного подождать. На экране появится одно маленькое всплывающее окно – там прописываются основные сведения об интересующем компоненте в операционной системе.

Работа с папками

С тем, как определить размер файла, разобраться удалось. Остаются другие вопросы – это работа с папками и группами электронных материалов.

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

Группы

Работа с файлами и папками – базовые навыки, которыми должен обладать каждый пользователь. Можно с легкостью выяснить, какой размер имеют несколько документов. Чтобы добиться соответствующего результата, предстоит:

Выделить группу файлов или папок. Можно – все вместе. Главное, чтобы под выделение попадали элементы, которые планируется оценить. Сделать это удается при помощи курсора и зажатой клавиши Ctrl на клавиатуре. Альтернативное решение – «обрисовка» границ выделения на экране ЛКМ.
При выделенных компонентах щелкнуть ПКМ и перейти в «Свойства».
Посмотреть в разделе «Общие» интересующие сведения.

Также можно после выделения группы элементов на устройстве навести курсор на «обозначенную» область и немного подождать. Информация появится в небольшом всплывающем окне.

Пространство на носителе

Операция, с которой тоже должен познакомиться каждый пользователь. Все носители информации имеют определенное количество свободного/занятого места. Чтобы посмотреть подобные данные, необходимо:

Вставить носитель информации в компьютер.
Перейти в «Мой Компьютер». Здесь уже часто отображаются интересующие сведения. Если нет – стоит перейти к следующему шагу.
Выделить интересующий носитель данных курсором мыши и нажать ПКМ.
Перейти в «Свойства».

Возникнет диалоговое окно, в котором находится соответствующая информация. Здесь «Емкость» — это общий размер носителя, «Занято» — общий размер файлов и папок, приложений на устройстве, «Свободно» — оставшееся пространство.

Ограничения при передаче

Иногда при переносе информации приходится сталкиваться с ограничениями по объему. Это может быть связано с:

недостатком памяти;
ограничениями системы (пример – файлообменник, не позволяющий загружать слишком больше файлы);
оптимизацией веб-сервиса.

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

Способы уменьшения объема

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

Чтобы «сжать» элементы в операционной системе предлагается использовать:

Архивирование. Пример – перевод в zip и rar.
Переходы к «старым форматам». Так docx занимает больше места, чем doc.
Грамотное использование графических документов. Их предварительно сжимают перед вставкой в файл или выкладыванием на сайт.
Перевод в другой формат. Данный процесс называется конвертированием. Часто приводит к потере качества.

Если речь идет о хранении видео, стоит отдать предпочтение MP4, а для аудио – MP3.

Хотите освоить современную IT-специальность? Огромный выбор курсов по востребованным IT-направлениям есть в Otus!

Источник

Определение
Единица измерения
Как определить размер файла?
Как определить размер группы файлов?
Ограничения в размере файла при передаче
Как уменьшить размер файла?

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

Определение

Размером файла называется объем пространства, которое он занимает на жестком диске, портативном носителе или в облачном хранилище. Этот показатель напрямую зависит от количества информации, содержащейся в файле.

Единица измерения

Размер файла измеряется в байтах (Б или b), и это является самым маленьким количеством данных. Обычно папка или иной вид информации (изображение, песня, электронная книга) имеет выражение веса в килобайтах (КБ или kb). Один килобайт эквивалентен 1024 байтам.

Более крупными единицами измерения являются мегабайты (МБ или mb) и гигабайты (ГБ или gb), равные 1024 килобайтам и 1024 мегабайтам соответственно. Из используемых в повседневной работе с ПК, наибольшей единицей выражения веса файла является терабайт (ТБ или tb), который эквивалентен 1024 гигабайтам.

В этих же единицах измерения определяется все пространство памяти на ПК, различных гаджетах и портативных носителях (флеш-карта, внешний жесткий диск и т.д.). И предельное количество файлов, которое можно загрузить в устройство, зависит от количества свободного пространства.

Как определить размер файла?

1. Наведите курсор мыши на файл и щелкните по нему правой кнопкой.

2. В появившемся контекстном меню выберите пункт «свойства» и щелкните на него.

3. Нужные данные можно увидеть в поле «размер».

Как определить размер группы файлов?

Если требуется определить суммарный размер нескольких файлов, нужно поступить так:

1. Выделите элементы, вес которых нужно определить. Это можно сделать, щелкнув по файлу левой кнопкой мыши и растянув появившуюся рамку на все папки. При этом следует удерживать кнопку мышки. Также можно выделить элементы, кликнув по одному из них, а затем, нажав клавишу Ctrl, щелкнуть поочередно по всем остальным.

2. Поставить курсор на один из выделенных элементов и кликнуть по нему правой кнопке мыши.

3. В появившемся контекстном меню выберите пункт «Свойства» и кликните по нему.

4. В пункте «размер» будет обобщённая информация о размере всех выбранных элементов.

Для поиска файлов большого размера с целью последующего удаления ненужных данных можно воспользоваться известной утилитой CCleaner. Кроме очистки ПК, она может отображать размер элементов. Для этого нужно выбрать пункт «Сервис» — «Анализ дисков». Впоследствии будет приведена диаграмма занимаемой памяти с подробной таблицей размера файлов различных типов.

Ограничения в размере файла при передаче

Загружая файлы или передавая их с одного носителя на другой, пользователь иногда встречается с ограничениями. Они могут быть связаны с тем, что:

Наблюдается недостаток места в памяти;
Требуется закачать файл на веб-ресурс (файлообменник или, к примеру, сайт по поиску работы), который выставил ограничения;
Проводится оптимизация сайта для убыстрения загрузки у пользователей с низкой скоростью передачи данных.

Как уменьшить размер файла?

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

Документ. Если нужно быстро прикрепить или передать документ, то будет целесообразно снизить его вес. Для этого можно:

Сохранить в формате docx, по сравнению с doc, он занимает меньше места. Разница ощутимая. Чтобы сделать это, следует открыть документ, выбрать пункт меню «Файл», затем «Преобразовать»;
Корректно работать с картинками. А значит, не просто их копировать в текстовый документ, а вставлять через пункт «Вставить рисунок». Чтобы существенно уменьшить размер, следует вкладывать отредактированные картинки с меньшим весом. Также можно при сохранении воспользоваться кнопкой «Сервис» и задать единый размер для всех картинок в документе посредством пункта меню «Сжать рисунки»;
Много места могут занимать и шрифты, которые не установлены в ПК. Чтобы избавиться от них, следует убрать галочку в пункте меню «внедрить шрифты в файл» (путь «Файл» -> «Параметры» -> «Сохранение»).

PDF. Файл PDF является универсальным, так как определяется большинством ОС. Они безопасны, и зачастую в этом формате сохраняют сканированные документы. Но их пересылка может быть затруднительна из-за их немалого размера.

Их можно сделать чуть легче с помощью Adobe Acrobat Reader, для этого достаточно кликнуть на «Уменьшить размер файла». Для пересылки подойдет и архивация. Чтобы ощутимо уменьшить вес, можно воспользоваться онлайн-сервисами, например, Smallpdf — ресурс для автоматического сжатия файла PDF. Сайт удобен тем, что не требует никаких дополнительных манипуляций, достаточно загрузить элемент, а затем уже скачать уменьшенный аналог. Также им можно сразу же поделиться по электронной почте, загрузить в облако. Весь процесс занимает минимум времени.

PDF Creator — бесплатная утилита, способная легко конвертировать документы в данный формат, а также уменьшить размер готового файла. Чтобы сделать легче документ PDF, следует открыть его в программе, а затем нажать на «Печать» — «Свойства» — «Бумага/качество» — «Дополнительно». Здесь нужно задать для DPI более низкое значение, это уменьшит разрешение и, как следствие, размер.

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

Есть специальные программы для упаковки файлов и папок большого размера. Наиболее известные для Windows — 7-Zip (бесплатный архиватор) и WinRAR (платная программа с хорошей производительностью). Чтобы архивировать файлы на ПК с установленной утилитой достаточно кликнуть на объект правой кнопкой мыши и перейти в пункт «Добавить в архив» и выбрать логотип программы.

Этот способ экономии памяти не несет за собой потери качества изображений и иных файлов, а также позволит записать их на портативный носитель или передать через электронную почту. Чтобы получателю распаковать архив, нужно будет использовать ту же утилиту.

Фотографии. Фото и иные изображения могут иметь действительно большой размер. Для уменьшения подобных файлов формата JPG (одного из наиболее распространенных), чаще всего, используется сжатие. Сделать это можно с помощью утилит:

Paint и Paint.NET— стандартная программа коррекции изображения. С ее помощью можно сделать меньше разрешение, что в разы снизит вес. Для этого следует выбрать пункт меню «Изменить размер», кликнув мышкой. В появившемся окне задается более низкое значение одного из параметров. Это влечет за собой автоматическое изменение остальных параметров, в соответствии с пропорциями фото;
Photoshop — редактор цифровых изображений для профессионалов. Здесь, для уменьшения веса фото, с сопутствующим снижением качества следует выбрать пункт меню File, затем Save for Web. Далее откроется окошко, в котором будет представлено исходное изображение и сохраненное для веб, под каждым пишет вес.

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

Аудио. Формат аудиофайлов .mp3, .aac означает, что файл уже сжат. Дальнейшие манипуляции приведут к потере качества. Звуковые файлы формата .wav, .aiff можно немного отредактировать, чтобы уменьшить размер.

Для этого их можно сохранить в виде .mp3 или .flac файла, попутно следует задать меньший битрейт. Это повлечет некоторую потерю качества. К примеру, 128 Кбит/сек. — звук FM-радио, 320 Кбит/сек. — звучание диска CD. Чтобы внести подобные изменения, потребуется утилита, подойдет любой бесплатный аудиоредактор.

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

С помощью утилиты можно обрезать видео, убрать лишнее и, заодно, снизить вес. Это делается просто — отмечается участок или несколько, которые можно убрать, и вырезается. Еще один способ — конвертировать видео в более компактный формат, выбрать нужный кодек и контейнер. Наиболее экономным будет MP4 (DiVX, MPEG2 тоже могут стать оптимальным решением). Также можно повлиять на качество и разрешение видео, задать битрейт. Некоторые программы позволяют установить и вес конечного файла. Если параметры не менять кардинально, то потеря качества не будет столь ощутима, но место, занимаемое на жестком диске уменьшится.

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

Источник

Задачи на определение информационного объема текста

Проверяется умение оценивать количественные параметры информационных объектов.

Теоретический материал:

N = 2ⁱ, где N – мощность алфавита (количество символов в используемом
алфавите),

i – информационный объем одного символа (информационный
вес символа), бит

I = K*i, где I – информационный объем текстового документа (файла),

K – количество символов в тексте

Задача 1.

Считаем количество символов в заданном тексте (перед и после тире – пробел, после знаков препинания, кроме последнего – пробел, пробел – это тоже символ). В результате получаем – 52 символа в тексте.

Дано:

i = 16 бит

K = 52

I — ?

Решение:

I = K*i

I = 52*16бит = 832бит (такой ответ есть — 2)

Ответ: 2

Задача 2.