Вычисление энтропии строку


Мы вычислении энтропии строку несколько мест в переполнения стека в качестве означающего низкого качества.

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

/// <summary>
/// returns the # of unique characters in a string as a rough 
/// measurement of entropy
/// </summary>
public static int Entropy(this string s)
{
  var d = new Dictionary<char, bool>();
  foreach (char c in s)
      if (!d.ContainsKey(c)) d.Add(c, true);
  return d.Count();
}

Существует ли лучше / более элегантный и более точный способ вычисления энтропии строки?

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



34553
216
задан 20 февраля 2011 в 09:02 Источник Поделиться
Комментарии
12 ответов

Не эта работа?

string name = "lltt";
int uniqueCharacterCount = name.Distinct().Count();

вернется 2

209
ответ дан 20 февраля 2011 в 09:02 Источник Поделиться

public static int Entropy(this string s)
{
HashSet<char> chars = new HashSet<char>(s);
return chars.Count;
}

89
ответ дан 20 февраля 2011 в 09:02 Источник Поделиться

Я тоже придумала, основываясь на энтропии Шеннона.


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

Это более "формального" расчет энтропии, чем просто подсчет букв:

/// <summary>
/// returns bits of entropy represented in a given string, per
/// http://en.wikipedia.org/wiki/Entropy_(information_theory)
/// </summary>
public static double ShannonEntropy(string s)
{
var map = new Dictionary<char, int>();
foreach (char c in s)
{
if (!map.ContainsKey(c))
map.Add(c, 1);
else
map[c] += 1;
}

double result = 0.0;
int len = s.Length;
foreach (var item in map)
{
var frequency = (double)item.Value / len;
result -= frequency * (Math.Log(frequency) / Math.Log(2));
}

return result;
}

Результаты:


"abcdefghijklmnop" = 4.00
"Здравствуй, Мир!" = 3.18
"Привет мир" = 2.85
"123123123123" = 1.58
"аааа" = 0

74
ответ дан 21 февраля 2011 в 09:02 Источник Поделиться

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

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

Короткие строки

Для начала, распределения. Сравнивать персонажей, что же именно это в некотором роде, но обобщение-построение таблицы частот и проверить распределение.

Дана строка длины n, сколько символов следует ожидать в среднем, учитывая мою модель (это может быть английская распределения, или распределения природного)?

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

это так же банально, как вычитания второго Чара из первого, третий из второго, так что в нашем примере строка это превращается в: "abcdefg" => 1,1,1,1,1,1

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

Длинные строки

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

73
ответ дан 20 февраля 2011 в 09:02 Источник Поделиться

Как насчет собственно вычисления энтропии? Кроме того, не ясно, что персонаж-уровень энтропии поможет, но здесь идет. Это на моем родном языке C++, но, конечно, вы можете преобразовать это в Java с использованием массива вместо std::вектор.

float CharacterEntropy(const char *str) {
std::vector<unsigned> counts(256);
for (const char *i = str; *i; ++i)
++counts[static_cast<unsigned char>(*i)];
unsigned int total = 0;
for (unsigned i = 0; i < 256; ++i)
total += counts[i];
float total_float = static_cast<float>(total);
float ret = 0.0;
for (unsigned i = 0; i < 256; ++i) {
float p = static_cast<float>(counts[i]) / total_float;
ret -= p * logf(p);
}
return p * M_LN2;
}

23
ответ дан 21 февраля 2011 в 12:02 Источник Поделиться

Похожие на zngu ответ, я думаю, лучше, чем просто подсчет количества символов расчете персонаж-энтропия сообщения:

public double CalculateEntropy(string entropyString)
{
Dictionary<char, int> characterCounts = new Dictionary<char, int>();
foreach(char c in entropyString.ToLower())
{
if(c == ' ') continue;
int currentCount;
characterCounts.TryGetValue(c, out currentCount);
characterCounts[c] = currentCount + 1;
}

IEnumerable<double> characterEntropies =
from c in characterCounts.Keys
let frequency = (double)characterCounts[c]/entropyString.Length
select -1*frequency*Math.Log(frequency);

return characterEntropies.Sum();
}

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

Вот некоторые тесты:

private void CalculateEntropyTest(object sender, EventArgs e)
{
string[] testStrings = {
"Hello world!",
"This is a typical english sentence containing all the letters of the english language - The quick brown fox jumped over the lazy dogs",
String.Join("", "This is a typical english sentence containing all the letters of the english language - The quick brown fox jumped over the lazy dogs".ToCharArray().OrderBy(o => o).Select(o => o.ToString()).ToArray()),
"Won't this work too?\nstring name = \"lltt\";\nint uniqueCharacterCount = name.Distinct().Count();\nwill return 2",
"Pull the entropy finding source from any compression algotithm, i.e. Huffman",
"float CharacterEntropy(const char *str) {\n std::vector<unsigned> counts(256);\n for (const char *i = str; *i; ++i)\n ++counts[static_cast<unsigned char>(*i)];\n unsigned int total = 0;\n for (unsigned i = 0; i < 256; ++i)\n total += counts[i];\n float total_float = static_cast<float>(total);\n float ret = 0.0;\n for (unsigned i = 0; i < 256; ++i) {\n float p = static_cast<float>(counts[i]) / total_float;\n ret -= p * logf(p);\n }\n return p * M_LN2;\n}",
"~~~~~~No.~~~~~~",
"asdasdasdasdasdasd",
"abcdefghijklmnopqrstuvwxyz",
"Fuuuuuuu-------",
};
foreach(string str in testStrings)
{
Console.WriteLine("{0}\nEntropy: {1:0.000}\n", str, CalculateEntropy(str));
}
}


Результаты:
Всем привет!
Энтропия: 1.888

Это типичное английское предложение, содержащее все буквы английского языка - быстрая коричневая лиса перепрыгнула через ленивую собак
Энтропия: 2.593

-TTaaaaaaabccccddeeeeeeeeeeeeeeffgggggghhhhhhhiiiiiiiijk
lllllllmnnnnnnnnnooooooppqrrrsssssssttttttttuuuvwxyyz
Энтропия: 2.593

Не эта работа?
имя string = "lltt";
инт uniqueCharacterCount = имя.Различны().Граф();
вернется 2
Энтропия: 2.838

Тянуть энтропия найти источник, из любой algotithm сжатия, т. е. Хаффман
Энтропия: 2.641

поплавок CharacterEntropy(константный тип char *, ул.) {
СТД::вектор отсчетов(256);
для (константный тип char *я = стр; *я; ++я)
++графов[static_cast (в*я)];
беззнаковый инт итого = 0;
для (Без знака Я = 0; я < 256; ++я)
итого += графов[я];
поплавок total_float = static_cast(в общей сложности);
поплавок рэт = 0.0;
для (Без знака Я = 0; я < 256; ++я) {
поплавок п = static_cast(в графы[я]) / total_float;
рет -= Р * ЛЗОС(п);
}
возвратить Р * M_LN2;
}
Энтропия: 2.866

~~~~~~Нет.~~~~~~
Энтропия: 0.720

asdasdasdasdasdasd
Энтропия: 1.099

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

Фууууууу-------
Энтропия: 0.892


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

21
ответ дан 22 февраля 2011 в 06:02 Источник Поделиться


  1. Я не понимаю смысл типа bool. Вы никогда не появляются, чтобы установить его в false, поэтому мы можем использовать список вместо.

  2. Учитывая, что вы хотите просто уникальные вещи, мы можем просто использовать для поиска HashSet вместо.

Не проверял, но этот метод должен быть эквивалентным и быстрее:

/// <summary>
/// returns the # of unique characters in a string as a rough
/// measurement of entropy
/// </summary>
public static int Entropy(this string s)
{
var hs = new HashSet<char>();
foreach (char c in s)
hs.Add(c);
return hs.Count();
}

15
ответ дан 20 февраля 2011 в 09:02 Источник Поделиться

Почему не разделить количество уникальных символов в заданной строке на общее количество символов в этой строке. Что бы дать более точную оценку энтропии.

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

12
ответ дан 20 февраля 2011 в 09:02 Источник Поделиться

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

10
ответ дан 20 февраля 2011 в 10:02 Источник Поделиться

Вы, наверное, можете расширить это что-то вроде Би-грамм и три грамма, чтобы получить что-то вроде "sdsdsdsdsdsdsdsdsdsd" (хотя в случае с тобой бы также поймать). Бы байесовский подход, как спам-фильтры не подходят для что-то вроде того, что вы пытаетесь достичь?

9
ответ дан 20 февраля 2011 в 09:02 Источник Поделиться

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

8
ответ дан 20 февраля 2011 в 09:02 Источник Поделиться

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

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

Кроме того, вы могли бы поймать неанглийские посты таким образом. (Если вы идете этим путем, то я рекомендую вам исключать фрагменты кода из графа...)

6
ответ дан 20 февраля 2011 в 10:02 Источник Поделиться