Каково определение энтропии в информатике?
https://stackoverflow.com/questions/510412
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Недавно я начал читать курс по сжатию данных в своем университете.Однако я нахожу использование термина "энтропия" применительно к информатике довольно двусмысленным.Насколько я могу судить, это примерно переводится как "случайность" системы или структуры.
Каково правильное определение термина "энтропия" в информатике?
Решение
Энтропия может означать разные вещи:
В вычислительной технике энтропия - это случайность, собираемая операционной системой или приложением для использования в криптографии или других целях, которые требуют случайных данных.Эта случайность часто собирается с помощью аппаратных источников, либо уже существующих, таких как движения мыши, либо специально созданных генераторов случайности.
В теории информации энтропия является мерой неопределенности, связанной со случайной величиной.Термин сам по себе в этом контексте обычно относится к энтропии Шеннона, которая определяет количественно, в смысле ожидаемого значения, информацию , содержащуюся в сообщении, обычно в единицах измерения, таких как биты.Эквивалентно, Энтропия Шеннона является мерой среднего информационного содержания, которое отсутствует, когда не известно значение случайной величины
Энтропия при сжатии данных
Энтропия при сжатии данных может обозначать случайность данных, которые вы вводите в алгоритм сжатия.Чем больше энтропия, тем меньше степень сжатия.Это означает, что чем более случайным является текст, тем меньше вы можете его сжать.
Энтропия Шеннона представляет собой абсолютного ограничения на максимальную сжатие без потерь из каких-либо коммуникации:рассматривая сообщения как закодированные как последовательность независимых и одинаково распределенных случайных величин, исходное кодирование Шеннона теорема показывает, что в пределе средняя длина кратчайшего возможного представления для кодирования сообщения в заданном алфавите - это их энтропия, деленная на логарифм количества символов в целевом алфавит.
Другие советы
Мое любимое определение, более практичное, приведено в главе 1 этой замечательной книги Прагматичный Программист:От Подмастерья до Мастера авторы : Эндрю Хант и Дэвид Томас:
Программная Энтропия
В то время как разработка программного обеспечения защищена почти от всех физических законов, энтропия сильно бьет по нам.Энтропия - это термин из физики, который относится к количеству "беспорядка" в системе.К сожалению, законы термодинамики гарантируют что энтропия во Вселенной стремится к максимуму.Когда беспорядок нарастает в программном обеспечении, программисты называют это "программной гнилью".
Существует множество факторов, которые могут способствовать гниению программного обеспечения.Наиболее Важным из них, по-видимому, является психология, или культура, при работе над проектом.Даже если вы команда из одного человека, психология вашего проекта может быть очень деликатной вещью.Несмотря на наилучшим образом продуманные планы и лучших людей, проект все еще может разрушаться и приходить в упадок в течение всего срока его службы.Тем не менее, есть другие проекты, которые, несмотря на огромные трудности и постоянные неудачи, успешно борются с природной тенденцией к беспорядку и им удается добиться довольно хороших результатов.
...
...
Разбитое окно.
Одно разбитое окно, которое не ремонтировалось в течение сколько-нибудь значительного периода времени, вселяет в обитателей здания чувство заброшенности — ощущение, что власть имущие не заботьтесь о здании.Итак, разбивается еще одно окно.Люди начинают мусорить.Появляется граффити.Серьезные начинаются структурные повреждения.За относительно короткий промежуток времени здание повреждается вопреки желанию владельца отремонтировать его, и чувство заброшенности становится реальностью.
"Теория разбитого окна" вдохновила полицейские управления Нью-Йорка и других крупных городов на то, чтобы расправиться с мелкими делами, чтобы не допустить крупных.Это работает:наблюдение за разбитыми окнами, граффити и другими мелкими правонарушениями снизило уровень серьезных преступлений.
Совет 4
Не Живите с Разбитыми Окнами
Не оставляйте "разбитые окна" (плохой дизайн, неправильные решения или плохой код) без ремонта.Фиксируйте все, что только есть так как он обнаружен.Если недостаточно времени для правильной починки, затем заколотите его досками.Возможно, вы сможете закомментировать код-нарушитель, или отобразить сообщение "Не реализовано", или заменить фиктивные данные.Примите какие-либо меры, чтобы предотвратить дальнейший ущерб и показать, что вы владеете ситуацией .
Текст взят из: http://pragprog.com/the-pragmatic-programmer/extracts/software-entropy
(источник: mit.edu)
Информационно-теоретическое понятие Энтропии является обобщением физического понятия.Существует много способов описать энтропию.Это мера случайности случайной величины.Это также показатель объема информации, которую содержит случайная величина или случайный процесс .Это также нижняя граница объема, в котором может быть сжато сообщение .И, наконец, это среднее количество вопросов "да / нет" , которые необходимо задать о случайном объекте, чтобы определить его ценность.
Уравнение для энтропии в примере приложения для вычисления вероятности:
это сумма по всем значениям rv вероятности этого значения, умноженной на логарифм этой вероятности (т.е.p(x)logp(x)).Это уравнение может быть выведено из первых принципов свойств информации.
Я всегда сталкивался с энтропией в смысле энтропии Шеннона.
От http://en.wikipedia.org/wiki/Information_entropy:
В теории информации энтропия - это мера неопределенности, связанная со случайной величиной.Сам по себе термин в данном контексте обычно относится к энтропии Шеннона, которая количественно определяет, в смысле ожидаемого значения, информацию, содержащуюся в сообщении, обычно в единицах измерения, таких как биты.Эквивалентно, энтропия Шеннона является мерой среднего информационного содержания, которого не хватает, когда человек не знает значения случайной величины.
С точки зрения сжатия и теории информации, энтропия источника - это среднее количество информации (в битах), которое могут передать символы из источника.Неофициально говоря, чем более маловероятен символ, тем больше удивления вызывает его появление.
Если в вашем источнике есть два символа, скажем 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 (исключительные) отрицательны.
Вот отличное альтернативное объяснение для энтропия в теории информации.
Энтропия - это мера неопределенность, участвующих в принятии предсказание.
Мы также можем описать энтропию как удивленный мы были бы рады, если бы получили результат после того, как сделали наш первоначальный прогноз.
Допустим, у нас есть изогнутая монета, которая дает нам орел в 99% случаев и хвост в 1% случаев.Поскольку вероятность получения хвоста составляет всего один процент, мы были бы очень удивлены, если бы действительно получили хвост.С другой стороны, не будет слишком удивительно, если мы получим голову, поскольку у нас уже есть 99-процентный шанс получить голову.
давайте предположим, что у нас есть функция, вызываемая Surprise(x) это дало бы нам определенную степень неожиданности для каждого результата;затем мы можем усреднить степень неожиданности по распределению вероятностей.Эта средняя степень удивления также может быть использована в качестве показателя нашей неуверенности.Эта неопределенность называется энтропия.
Очень ПРОСТОЕ определение
Слово энтропия может быть определено в одном предложении:
"Объем информации, необходимый для описания системы".
Представьте себе, например, расширение вселенной:С самого начала, до большого взрыва, вся материя была собрана в маленькой точке, поэтому мы могли бы описать систему словами "вся материя находится в одной точке". Хотя сегодня для описания системы (то есть Вселенной) требуется значительно больше информации, потребовалось бы описать все положения планет, их движение, то, что находится на них и т.д..С точки зрения теории информации это определение также работает:Например,:Чем больше букв вы добавляете к паролю (системе), тем больше информации требуется для описания пароля.Затем вы можете измерить его в разных единицах измерения, например, битах или символах, например
"hello" = 5 символов энтропии = 40 бит энтропии (если charsize равен 8 битам).
Из этого также следует, что чем больше у вас информации, тем больше способов вы можете упорядочить эту информацию.Если у вас есть 40 битов, существует 2 ^ 40 различных способов их расположения.Если мы говорим здесь о паролях, то чем больше возможных комбинаций информации (битов), тем больше времени потребуется для взлома (с помощью грубой силы или атак по словарю).
Проще говоря, энтропия определяет случайность.Это больше похоже на то, насколько непредсказуемо что-то происходит.Более техническими словами: “В вычислительной технике энтропия - это случайность, собираемая операционной системой или приложением для использования в криптографии или других целях, требующих случайных данных.Эта случайность часто собирается из аппаратных источников, либо из уже существующих, таких как движения мыши, либо из специально предоставленных генераторов случайности ”. согласно определению википедии.
Теперь можно легко сделать вывод о значении энтропии по отношению к файлу как об измерении того, насколько неупорядоченными являются байты в файле.Существуют различные единицы измерения, используемые для определения энтропии, такие как нат, Шеннон или хартли.Ну, самая распространенная используемая единица измерения - Шеннон.Диапазон значений энтропии файла, который должен быть получен в соответствии с алгоритмом Шеннона, составляет от 0 до 8.Итак, когда значение энтропии равно нулю, можно сказать, что результат определен.Напротив, когда значение энтропии равно 8, результат наиболее непредсказуем, какой только может быть.Формула , приведенная Шенноном для измерения случайности в исходе событий , выглядит следующим образом:
Entropy = ∑ pi log(1/pi)
где i является ли событие вероятностным число пи.
Это уравнение всегда приводит к значению от 0 до 8.
Для получения дополнительной информации перейдите по ссылке: https://www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/
энтропия относится к степени, в которой программное обеспечение периодически видоизменяется в соответствии с требованиями заказчика, следовательно, затраты на его видоизменение в соответствии с требованиями заказчика становятся максимальными.
Энтропия также подобна хэш-коду для исследователей вирусов.Если вы получите меньшую энтропию, это будет означать, что это, скорее всего, зашифрованный или сжатый код, который потенциально может быть вирусом.
Стандартный двоичный файл будет иметь более высокую энтропию, чем сжатый или зашифрованный.
Энтропия обычно имеет много значений в информатике.Это зависит от контекста.В безопасности энтропия означает, сколько случайности вы вкладываете, например, когда вы генерируете закрытый ключ, многие приложения просят вас подвигать мышью, чтобы сгенерировать энтропию.Это генерирует энтропию, беря "человеческий" элемент случайности и добавляя его в процесс хеширования при генерации ключа.
Теперь существует также определение энтропии для программной инженерии.Это определение представляет устаревший код или код, который писали многие разработчики.Обычно используется в отношении того, когда приближается время для рефакторинга вашего программного проекта."Код для этого проекта содержит огромное количество энтропии, потому что многие из тех, кто его поддерживал, в настоящее время не участвуют в проекте".
Вот третий пример использования, который я тоже запомнил.В разделе о моделируемом отжиге (что касается информатики) энтропия описывается как степень распада, произошедшая во время оценки алгоритма.
Однако я полагаю, чтобы ответить на ваш вопрос, что конкретного определения слова "энтропия" не существует, за исключением тех, которые вы можете найти в словаре.То, как информатика склонна применять этот термин, зависит от контекста используемого термина и от того, к чему он применяется.
Из энтропии легко сделать большое дело.На мой взгляд, это довольно простая и полезная концепция.
По сути, это количественная оценка того, что в среднем вы узнаете из события, такого как подбрасывание монетки, выполнение инструкции перехода или индексация массива.
Подобно операции сравнения в середине поискового алгоритма, существует определенная вероятность того, что 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 бит, чтобы найти запись в таблице.
Энтропия в информатике обычно относится к тому, насколько случайна последовательность битов.Следующий вопрос касается того, как сделать это точным:
Простыми словами , если вы знаете вероятности символов в языке , можно вычислить среднее информационное содержание символа в этом языке .
Или
Энтропия языка - это мера информационного содержания среднего символа в языке
Считайте, что это честная монета ;
Есть два символа, каждый с вероятностью 1/2 таким образом, энтропия вычисляется как
h =-(1/2*log1/2 +1/2* log1/2) =1
Я слышал, что люди неправильно используют термодинамические определения энтропии по отношению к CS.
Например.Энтропия в этой системе определенно увеличивается.
Когда они имеют в виду, что этот код становится все хуже и хуже!
