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

Не будет ли это тоже работать?

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

вернет 2

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

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

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

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

Чтобы начать, распределение. Сравнение одинаковых символов в точности аналогично, но обобщение заключается в создании таблицы частот и проверке распределения.

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

Но как насчет «abcdefg»? Здесь нет повторений, но это не случайно. Итак, вы хотите здесь взять первую производную и проверить распределение первой производной.

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

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

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

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

Я также придумал это на основе энтропии Шеннона .

  

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

Это более «формальный» расчет энтропии, чем просто подсчет букв:

/// <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
"hello world" = 2.85
"123123123123" = 1,58
"aaaa" = 0

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

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;
}

Как и ответ 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 name = "lltt";   int uniqueCharacterCount = name.Distinct (). Count ();   вернется 2
  Энтропия: 2,838

     

Потяните источник поиска энтропии из любого алгорифма сжатия, то есть Хаффмана   Энтропия: 2.641

     

float CharacterEntropy (const char * str) {     std :: vector counts (256);     for (const char * i = str; * i; ++ i)     ++ подсчитывает [static_cast (* я)];     unsigned int total = 0;     для (без знака i = 0; i <256; ++ i)       total + = counts [i];     float total_float = static_cast (всего);     float ret = 0.0;     for (unsigned i = 0; i <256; ++ i) {       float p = static_cast (count [i]) /total_float;       ret - = p * logf (p);     }     return p * M_LN2;   }
  Энтропия: 2.866

     

~~~~~~ No. ~~~~~~
  Энтропия: 0,720

     

asdasdasdasdasdasd
  Энтропия: 1.099

     

АБВГДЕЖЗИКЛМНОПРСТУФХЧШЭЮЯ
  Энтропия: 3,258

     

Fuuuuuuu -------
  Энтропия: 0,872

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

1. Я не понимаю смысла в bool. Вы никогда не показываете, что он установлен на false, поэтому мы можем использовать List<T>.
2. Учитывая, что вы хотите только уникальные элементы, мы можем просто использовать HashSet<T>.

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

/// <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();
}

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

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

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

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

Ключевые понятия этого алгоритма:

• При первом знаком символе максимальное значение добавляется к ненормализованной сумме энтропии. «Максимальное значение» - это длина строки.
• Если символ встречается снова, то мы подсчитываем количество позиций между этим вхождением и последним вложением, затем мы вычитаем общее количество раз, когда этот символ появился в строке. Затем мы добавляем это значение к ненормированной сумме энтропии.

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

  public static int Entropy(this string s)
  {
      int entropy = 0;
  
      var mapOfIndexByChar = new Dictionary<char, CharEntropyInfo>();
  
      int index = 0;
      foreach (char c in s)
      {
          CharEntropyInfo charEntropyInfo;
          if (mapOfIndexByChar.TryGetValue(c, out charEntropyInfo))
          {
              // If this character has occurred previously, then only add the number of characters from
              // the last occurrence to this occurrence, and subtract the number of previous occurrences.
              // Many repeated characters can actually result in the entropy total being negative.
              entropy += ((index - charEntropyInfo.LastIndex) - charEntropyInfo.Occurrences);
  
              // update the last index and number of occurrences of this character
              mapOfIndexByChar[c] = new CharEntropyInfo(index, charEntropyInfo.Occurrences + 1);
          }
          else
          {
              // each newly found character adds the maximum possible value to the entropy total
              entropy += s.Length;
  
              // record the first index of this character
              mapOfIndexByChar.Add(c, new CharEntropyInfo(index, 1));
          }
      }
  
      // divide the entropy total by the length of the string to "normalize" the result
      return entropy / s.Length;
  }
  
  struct CharEntropyInfo
  {
      int _LastIndex;
      int _Occurrences;
  
      public int LastIndex
      {
          get { return _LastIndex; }
      }
      public int Occurrences
      {
          get { return _Occurrences; }
      }
  
      public CharEntropyInfo(int lastIndex, int occurrences)
      {
          _LastIndex = lastIndex;
          _Occurrences = occurrences;
      }
  }
  

Быстрый тест:

        var inputs = new[]{
            "Hi there!",
            "Hi there, bob!",
            "ababababababababababababab",
            @"We're calculating entropy of a string a few places in Stack Overflow as a signifier of low quality.

I whipped up this simple method which counts unique characters in a string, but it is quite literally the first thing that popped into my head. It's the ""dumbest thing that works""."
        };

        foreach (string s in inputs)
        {
            System.Console.WriteLine("{1}: \"{0}\"", s, s.Entropy());
        }

Результирующие значения энтропии:

• 7: «Привет!»
• 10: «Привет, Боб!»
• -4: "ababababababababababababab"
• 25: «Мы вычисляем энтропию строки ...»

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

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

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

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

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