Как энтропия строки английского текста означает низкое качество?

Джефф Этвуд недавно написал твиттерную ссылку на сообщение CodeReview, где он хотел узнать, может ли сообщество улучшить его "расчет энтропии строки" фрагмента кода. Он объяснил: "Мы вычисляем энтропию строки в нескольких местах в Qaru в качестве знака низкого качества".

Суть его метода заключалась в том, что если вы подсчитаете количество уникальных символов в строке, это означает энтропию (код, взятый из PieterG answer):

int uniqueCharacterCount = string.Distinct().Count();

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

Спасибо!

Ответ 1

String "aaaaaaaaaaaaaaaaaaaaaaaaaaa" имеет очень низкую энтропию и совершенно бессмысленна.

String 'blah blah blah blah blah blah blah blah' имеет немного более высокую энтропию, но по-прежнему довольно глупый и может быть часть атаки.

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

Ответ 2

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

Это всего лишь один из нескольких алгоритмов, используемых для поиска возможных низкокачественных сообщений, отображаемых на вкладке низкого качества сообщений (требуется 10k rep) инструментов модератора. Фактическим людям по-прежнему нужно смотреть на сообщение.

Идея состоит в том, чтобы улавливать сообщения типа ~~~~~~No.~~~~~~ или FUUUUUUUU------, чтобы не улавливать все сообщения низкого качества.

Что касается "Как уникальное количество символов означает энтропию?" - На самом деле это не так. Самые верные ответы полностью упускают точку.

См. https://codereview.stackexchange.com/questions/868#878 и https://codereview.stackexchange.com/questions/868#926

Ответ 3

Посмотрите на запись в Википедии Энтропия (теория информации):

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

И особенно с английской информацией:

Скорость энтропии английского текста составляет от 1,0 до 1,5 бит на букву или от 0,6 до 1,3 бит на букву, согласно оценкам Шеннона на основе человеческих экспериментов.

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

Ответ 4

Энтропия Шеннона H (P) является свойством распределения вероятностей P случайной величины X.

В случае строки рудиментарный способ лечения - как мешок символов. В этом случае частотный счетчик представляет собой приближение распределения вероятностей P, случайно выбранного символа в строке.

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

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

Основываясь на Rex M answer... было бы разумнее искать строки, где "энтропия символов" падала вне диапазона 1.0 - 1.5, насколько это возможно, "строки низкого качества".

Ответ 5

Не точно ответ на ваш вопрос, но, Wikipedia это объяснение Энтропии:

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

Английский текст имеет довольно низкую энтропию. Другими словами, это довольно предсказуемо. Даже если мы не знаем точно, что будет дальше, мы можем быть справедливыми что, например, будет намного больше, чем z, или что комбинация "qu" будет намного более распространена, чем любая другая комбинация с "q" в нем, а комбинация "th" будет более распространена, чем любая из них. Несжатый, английский текст имеет примерно один бит энтропии для каждый бит (восемь бит) сообщения.