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

Question

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

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

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

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

Спасибо!

Answer 1

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

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

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

---

Что касается «Как уникальный счет символов означает энтропию?» - на самом деле это не так. В большинстве проголосовавших ответы полностью упускают из виду.

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

Answer 2

Строка 'aaaaaaaaaaaaaaaaaaaaaaaaaaa' имеет очень низкую энтропию и является довольно бессмысленной.

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

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

Answer 3

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

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

А конкретно с английской информацией:

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

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

Answer 4

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

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

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

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

Опираясь на ответ Рекса М ... было бы более разумно искать строки, в которых «энтропия персонажа» выходила за пределы диапазона 1,0–1,5, как возможные «строки низкого качества».

Answer 5

Не совсем ответ на ваш вопрос, но в Википедии есть это объяснение энтропии :

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

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