Какое компьютерное определение энтропии?

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

Каково правильное определение информатики "энтропия"?

17 ответов

Решение

Энтропия может означать разные вещи:

вычисления

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

Теория информации

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

Энтропия в сжатии данных

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

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

Мое любимое определение с более практической направленностью содержится в главе 1 превосходной книги Эндрю Ханта и Дэвида Томаса "Прагматичный программист: от путника до мастера ":

Программная энтропия

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

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

...

...

Разбитое окно.

Одно разбитое окно, оставшееся не ремонтированным в течение какого-либо существенного промежутка времени, вселяет в жителей здания чувство покинутости - ощущение, что властям, которые не заботятся о здании. Так что другое окно разбивается. Люди начинают мусорить. Граффити появляется. Начинается серьезное структурное повреждение. В относительно короткий промежуток времени здание становится поврежденным, и владелец не хочет его ремонтировать, а чувство заброшенности становится реальностью.

"Теория разбитого окна" вдохновила полицейские управления в Нью-Йорке и других крупных городах на мелкие мелочи, чтобы не пускать большие мелочи. Это работает: держась за разбитые окна, граффити и другие мелкие нарушения снизили уровень серьезной преступности.

Совет 4

Не живи с разбитой Windows

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

Текст взят из: http://pragprog.com/the-pragmatic-programmer/extracts/software-entropy

Я всегда сталкивался с энтропией в смысле энтропии Шеннона.

От http://en.wikipedia.org/wiki/Information_entropy:

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


(источник: mit.edu)

из университета Мексики

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

Уравнение для энтропии в примере приложения для расчета вероятности:

это сумма по всем значениям rv вероятности этого значения, умноженная на log этого проба (т. е. p(x)logp(x)). Это уравнение может быть выведено из первых принципов свойств информации.

Вот отличное альтернативное объяснение энтропии в теории информации.

Энтропия является мерой неопределенности, связанной с прогнозированием.

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

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

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

Супер ПРОСТОЕ определение

Слово энтропия может быть определено в одном предложении:

"Количество информации, необходимое для описания системы".

Представьте для примера расширение вселенной: с самого начала вся материя была собрана за небольшую точку перед большим взрывом, поэтому мы могли бы описать систему так: "вся материя находится в одной точке". Хотя сегодня для описания системы (то есть Вселенной) требуется значительно больше информации, необходимо описать все положения планет, их движение, что на них и т. Д. В терминах теории информации определение также работает: Например: Чем больше букв вы добавляете к паролю (системе), тем больше информации требуется для описания пароля. Затем вы можете измерить его в разных единицах, например, битах или символах, например, "hello" = 5 символов, энтропия = 40 битов энтропии (если charsize равен 8 битам).

Отсюда также следует, что чем больше информации у вас есть, тем больше способов ее упорядочить. Если у вас 40 битов, есть 2^40 разных способов их размещения. Если мы говорим здесь пароли, то чем больше возможных вариантов информации (битов), тем больше времени потребуется для взлома (с помощью грубой силы или словарных атак).

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

Если ваш источник имеет два символа, скажем A а также Bи они одинаково вероятны, тогда каждый символ передает одинаковое количество информации (один бит). Источник с четырьмя одинаково вероятными символами передает два бита на символ.

Для более интересного примера, если ваш источник имеет три символа, A, B, а также Cгде первые два имеют в два раза большую вероятность, чем третье, то третье более удивительно, но также менее вероятно. Чистая энтропия для этого источника составляет 1,52, как рассчитывается ниже.

Вы вычисляете энтропию как "средний сюрприз", где "сюрприз" для каждого символа - это его вероятность, умноженная на отрицательный двоичный журнал вероятности:

                            binary
symbol  weight  probability   log    surprise
  A        2        0.4      -1.32    0.53
  B        2        0.4      -1.32    0.53
  C        1        0.2      -2.32    0.46
total      5        1.0               1.52

Используется отрицательный знак двоичного журнала (конечно), поскольку записи значений от 0 до 1 (исключая) являются отрицательными.

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

Теперь можно легко заключить значение энтропии в отношении файла как измерения того, насколько беспорядочными являются байты в файле. Существуют различные единицы измерения энтропии, такие как nat, shannon или hartley. Ну, самая распространенная единица измерения - это Шеннон. Диапазон значений, в которые должна входить энтропия файла согласно алгоритму Шеннона, составляет от 0 до 8. Таким образом, когда значение энтропии равно нулю, можно сказать, что результат определен. Напротив, когда значение энтропии равно 8, результат может быть самым непредсказуемым. Формула, данная Шенноном для измерения случайности в результате событий:

          Entropy = ∑ pi log(1/pi)

где я - событие с вероятностью пи.

Это уравнение всегда будет в диапазоне от 0 до 8.

Для получения дополнительной информации перейдите по ссылке: https://www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/

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

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

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

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

Или же

Энтропия языка - это мера информативности среднего символа в языке.

Рассмотрим честную монету;

Есть два символа, каждый с вероятностью 1/2, поэтому энтропия рассчитывается как

h =-(1/2*log1/2 +1/2*log1/2)=1

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

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

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

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

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

Как вычислить приблизительную энтропию битовой строки?

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

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

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

Это легко сделать из энтропии. На мой взгляд, это довольно простая и полезная концепция.

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

Подобно операции сравнения в середине алгоритма поиска, есть определенная вероятность P взятия одной ветви и 1-P взятия другой.

Предположим, что P равно 1/2, как в бинарном поиске. Затем, если вы берете эту ветвь, вы знаете на 1 бит больше, чем раньше, потому что log(2/1), основание 2, равно 1. С другой стороны, если вы берете другую ветку, вы также изучаете 1 бит.

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

1/2 раз 1 бит, плюс 1/2 раз 1 бит, это 1/2 бит плюс 1/2 бит или всего 1 бит энтропии. Это то, что вы можете ожидать усвоить в среднем из этого решения.

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

В первом тесте == вероятность ДА равна 1/1024, поэтому энтропия ДА при этом решении равна

1/1024 times log(1024/1)

или 1/1024 * 10 = около 1/100 бит.

Таким образом, если ответ ДА, вы изучите 10 битов, но вероятность этого составляет около 1 на тысячу.

С другой стороны, НЕТ гораздо более вероятно. Это энтропия

1023/1024 * log(1024/1023)

или примерно 1 раз примерно ноль = около нуля.

Сложите их вместе, и в среднем вы узнаете примерно 1/100 от этого решения.

Вот почему линейный поиск идет медленно. Энтропия (сколько вы можете ожидать узнать) при каждом решении слишком мала, так как вам нужно будет выучить 10 битов, чтобы найти запись в таблице.

Я слышал, что люди неправильно используют термодинамические определения энтропии по отношению к CS.

Например, энтропия определенно увеличивается в этой системе.

Когда это означает, что этот код становится все хуже и хуже!

Другие вопросы по тегам