Berechnen Sie die Histogramm-Entropieschätzung einer Zeichenfolge

19

Schreiben Sie ein Programm oder eine Funktion, die die Shannon-Entropie einer bestimmten Zeichenfolge schätzt.

Wenn eine Zeichenkette n Zeichen und d verschiedene Zeichen hat, x i das i- te verschiedene Zeichen ist und P (x i ) die Wahrscheinlichkeit ist, dass dieses Zeichen in der Zeichenkette vorkommt, dann ist unsere Shannon-Entropieschätzung für diese Zeichenkette gegeben durch:

H = -n \ sum \ limits_ {i = 1} ^ d P (x_i) \ log_2 P (x_i)

Für die Schätzung in dieser Herausforderung nehmen wir an, dass die Wahrscheinlichkeit, dass ein Zeichen in einer Zeichenfolge vorkommt, einfach die Häufigkeit des Auftretens dividiert durch die Gesamtzahl der Zeichen ist.

Ihre Antwort muss nach dem Zeitraum auf mindestens 3 Stellen genau sein.


Testfälle:

"This is a test.", 45.094
"00001111", 8.000
"cwmfjordbankglyphsvextquiz", 122.211
"             ", 0.0
orlp
quelle
Im Gegensatz zu meinen üblichen Herausforderungen sieht diese kompliziert aus, ist aber eigentlich recht einfach :)
orlp
Siehe auch
msh210
Ist es sicher, druckbares ASCII für die Eingabezeichenfolge anzunehmen?
AdmBorkBork
@TimmyD Nein. Jede Zeichenfolge, die der Zeichenfolgentyp Ihrer Sprache unterstützt.
Orlp
Leider zählt Mathematica die EntropyBits pro Zeichen, nicht die Gesamtzahl für die Zeichenfolge.
na ja

Antworten:

2

Jelly, 11 8 Bytes

ċЀ÷Ll.S

Probieren Sie es online!

Dennis
quelle
Kann ich fragen, wie Sie diese Zeichen eingeben? Mit Kopieren und Einfügen?
Bálint
Zumindest unter Linux können sie alle über die internationale US-Tastatur eingegeben werden.
Dennis
11

Python 3.3+, 64 Bytes

import math
lambda s:sum(math.log2(len(s)/s.count(c))for c in s)

Erhielt math.log2von mbomb007-Lösung .

xnor
quelle
@Orlp hat uns also keine vollständig vereinfachte Formel gegeben, oder ...?
mbomb007
@ mbomb007 Hängt davon ab, zu welchem ​​Zweck Sie vereinfachen. Das Schreiben in Bezug auf Wahrscheinlichkeiten und unterschiedliche Zeichen ist eine natürliche Definition, aber beim Golfen ist es kürzer, mit Zählungen zu arbeiten und alle Zeichen zu durchlaufen.
XNOR
1
Pyth-Antwort mit Ihrer Formel: pyth.herokuapp.com/… 8 Bytes
Maltysen
2

APL, 18 14 Bytes

+/2⍟≢÷(+/∘.=⍨)

Dies ist ein unbenannter, monadischer Funktionszug, der eine Zeichenfolge auf der rechten Seite akzeptiert und eine reelle zurückgibt.

Wie alle guten Dinge im Leben wird auch hier die Formel von xnor verwendet . Wir erhalten eine Matrix von Booleschen Werten, die den Vorkommen jedes Zeichens in der Zeichenfolge entsprechen. Addieren Sie diese Werte ∘.=⍨entlang der ersten Achse ( +/), um die Anzahl der Vorkommen jedes Zeichens zu erhalten, dividieren Sie die Länge der Zeichenfolge durch jedes und nehmen Sie dann die Protokollbasis 2 ( 2⍟) und Summe.

Probieren Sie es hier aus

4 Bytes gespart dank Dennis!

Alex A.
quelle
1

MATL, 17 Bytes

S4#Y'ts/tZl*sGn_*

Probieren Sie es online!

Becherglas
quelle
Möglicherweise können Sie einige Bytes mitYm
Luis Mendo
1

JavaScript (ES6), 67 Byte

s=>[...s].map(c=>t+=Math.log2(s.length/~-s.split(c).length),t=0)&&t

Ich muss verwenden, ~-s.splitweil das Zeichenfolgen statt regulärer Ausdrücke akzeptiert. Wie üblich, mapschlägt reducebyteweise.

s=>[...s].reduce((t,c)=>t+Math.log2(s.length/~-s.split(c).length),0)
Neil
quelle
1

Perl 5, 58 Bytes

Ein Unterprogramm:

{for$a(@a=split'',pop){$t+=(log@a/grep/\Q$a/,@a)/log 2}$t}

Ein Tipp von meinem Hut zu xnor für die Formel.

msh210
quelle
-Ffunktioniert nicht (in Strawberry jedenfalls), weil es das enthält $/.
msh210
1

MATL , 14 Bytes

!Gu=stGn/Zl*s|

Probieren Sie es online!

!      % transpose implicit input into column vector
Gu     % row vector with unique elements of input
=      % test for equality, element-wise with broadcast
s      % sum of each column
tGn/   % duplicate. Divide by number of input characters
Zl     % binary logarithm
*      % element-wise multiplication
s      % sum of array
|      % absolute value. Display implicitly
Luis Mendo
quelle
1

Julia, 37 Bytes

x->sum(log2(endof(x)./sum(x.==x',1)))

Nimmt ein Zeichenarray als Eingabe. Probieren Sie es online!

Dennis
quelle
1

J - 18 16 14 Bytes

1#.2^.#%1#.=/~

Verkürzt mit der Idee in Dennis 'Methode.

Verwendung

   f =: 1#.2^.#%1#.=/~
   f 'This is a test.'
45.0936
   f '00001111'
8
   f 'cwmfjordbankglyphsvextquiz'
122.211
   f '             '
0

Erläuterung

1#.2^.#%1#.=/~  Input: string S
           =/~  Create a table testing for equality
        1#.     Convert each row from a list of base 1 digits to decimal
                This is equivalent to taking the sum and forms a list of tallies
      #         Get the length of S
       %        Divide the length by each tally
   2^.          Log base 2 of each
1#.             "Sum" those values and return
Meilen
quelle
1
Ich denke nicht, dass dies eine Funktion ist. Wenn Sie den Code einer Variablen zuweisen, geschieht etwas völlig anderes.
Dennis
@Dennis Soweit ich erfahre, scheint es, als würde J es als eine Kette von Kompositionen interpretieren. Die Verwendung 3 : '... y'derselben Syntax wäre eine gültige Methode, um es als Funktion zu definieren. J gibt an, dass es von rechts nach links ausgewertet wird, sodass ich meinen Code als Zug überarbeitet habe. Ich mag keine Mützen, [:aber ich kann keinen anderen Weg finden, um einen Zug zu bauen.
Meilen
0

Jolf, 26 Bytes

_*liuΜGμiEd*γ/l miLeHlimzγ

Probieren Sie es hier aus! (Beachten Sie, dass die Funktion der Testsuite eingeschränkt ist.)

Erläuterung

_*liuΜGμiEd*γ/l miLeHlimzγ
       μi                   unique members of i
      G  E                  split on ""
     Μ    d                 map over function
               _miLeH       match i with regex escaped member
             /l      li     divide length of (^) by length of i
            γ               γ = (^)
           *           mzγ  (^) * log_2(γ)
 *li                        (^) * length of i
_                           negate
Conor O'Brien
quelle
0

Python 3.3+, 95 91 89 85 Bytes

Einfache lösung. Für die Verwendung ist Version 3.3 erforderlich math.log2.

import math
def f(s):C=s.count;return-sum(C(x)*math.log2(C(x)/len(s))for x in set(s))

Probieren Sie es online aus

mbomb007
quelle
Glaubst du, hier gibt es etwas Unnötiges? n*sum(s.count(c)/n
Orlp
@orlp Danke. Ich hatte ursprünglich eine separate Funktion zum Ermitteln der Wahrscheinlichkeit, hatte sie jedoch zweimal eingefügt und gelöscht, um Zeichen zu sparen.
mbomb007
Sie müssen nicht mehr nin einer Variablen speichern , da Sie sie nur einmal verwenden.
Maltysen
0

Java 7, 207 Bytes

double C(String x,Map<Character,Integer>f){double H=0,g;for(char c:x.toCharArray())f.put(c,f.containsKey(c)?f.get(c)+1:1);for(char c:f.keySet()){g=f.get(c);H+=g*Math.log(g/x.length())/Math.log(2);}return-H;}

Ausführlicher Versuch online

double log2(double d) { return Math.log(d) / Math.log(2); }

double C(String x, Map<Character,Integer>f)
{
    double H=0,g;

    // frequency
    for(char c : x.toCharArray())
    {
        f.put(c, f.containsKey(c) ? f.get(c)+1 : 1);
    }

    // calculate entropy
    for(char c : f.keySet())
    {
        g = f.get(c);
        H += g * log2(g / x.length());
    }

    return -H;
}
Khaled.K
quelle
0

Faktor 98 Bytes

[ [ length ] [ dup [ [ = ] curry dupd count ] { } map-as nip ] bi [ / log 2 log / ] with map sum ]

Dies ist eine direkte Übersetzung dieser Python-Antwort . Ich werde beim Abendessen eine Erklärung hinzufügen.

Katze
quelle
0

Schläger, 130 Bytes

: c

#lang racket
(require math)(λ(S)(let([s(string->list S)])(sum(map(λ(c)(/(log(/(length s)(count(λ(x)(char=? c x))s)))(log 2)))s))))

Die Übersetzung meiner Faktor-Antwort ist also eine indirekte Übersetzung von Kenny Laus Python-Antwort.

Katze
quelle
0

k (32 Bytes)

{-+/c*(log c%n:+/c:#:'=x)%log 2}

Oder in q, die Übersetzung ist gar nicht so kurz, aber klarer:

{neg sum c*2 xlog c%n:sum c:count each group x}
Skeevey
quelle
0

Mathematica, 45 Bytes

Tr[Log[2,Tr@#/#]#]&@Values@CharacterCounts@#&

Verwendung

Dies gibt genaue Ergebnisse zurück, mit denen wir sie approximieren N.

  f = Tr[Log[2,Tr@#/#]#]&@Values@CharacterCounts@#&
  f["This is a test."]//N
45.0936
  f["00001111"]//N
8.
  f["cwmfjordbankglyphsvextquiz"]//N
122.211
  f["             "]//N
0.
Meilen
quelle
0

R, 67 Bytes

l=length(i<-strsplit(readline(),"")[[1]]);-sum(log2(l/table(i)[i]))

Erläuterung

Nehmen Sie die Eingabe von stdin und teilen Sie sie in eine Liste von Zeichen auf. (Diese klobige Syntax ist der Grund, warum Saitengolf-Herausforderungen in R ... so schwierig sind.)

         i<-strsplit(readline(),"")[[1]])

Diese Zuweisung ist in einem lengthBefehl verborgen , daher erhalten wir zwei Zuweisungen zum Preis von einer. Wir haben idie Liste der Zeichen und lihre Länge.

l=length(i<-strsplit(readline(),"")[[1]]);

Nun berechnen wir die Entropie. R hat eine nette Funktion, tabledie die Anzahl aller eindeutigen Werte zurückgibt. Bei Eingabe This is a testwird table(i)zurückgegeben

> table(i)
i
  . a e h i s t T 
3 1 1 1 1 2 3 2 1

Dies wird durch Zeichen indiziert, was sehr schön ist, da wir dann ials Index verwenden können, um die Anzahl der einzelnen Zeichen zu erhalten, wie folgt:

> table(i)[i]
i
T h i s   i s   a   t e s t . 
1 1 2 3 3 2 3 3 1 3 2 1 3 2 1 

Der Rest des Codes ist dann eine einfache Implementierung der Entropieformel, die ein wenig umgedreht ist.

                                           -sum(log2(l/table(i)[i]))
rturnbull
quelle
Speichern Sie zwei Bytes (auch Ihre Einreichung funktioniert nicht auf TIO)
JayCe
0

159 Bytes

Golf gespielt:

string f(string s){var l=s.Length;double sum=0;foreach(var item in s.GroupBy(o=>o)){double p=(double)item.Count()/l;sum+=p*Math.Log(p,2);}return(sum*=-l)+"";}}

Ungolfed:

string f(string s)
{
  var l = s.Length;
  double sum = 0;
  foreach (var item in s.GroupBy(o => o))
  {
    double p = (double)item.Count() / l;
    sum += p * Math.Log(p, 2);
  }
  return (sum *= -l) + "";
}

Prüfung:

var codeGolf = new StringHistogramEntropyEstimation();
    Console.WriteLine(codeGolf.f("This is a test.")); //45.0935839298008
    Console.WriteLine(codeGolf.f("00001111")); //8
    Console.WriteLine(codeGolf.f("cwmfjordbankglyphsvextquiz")); //122.211432671668
    Console.WriteLine(codeGolf.f("             ")); //0
Pete Arden
quelle
0

Groovy, 100 Bytes

{a->n=a.size();a.toList().unique().collect{p=a.count(it)/n;p*(Math.log(p)/Math.log(2.0f))}.sum()*-n}

Tests:

This is a test. = 45.09358393449714
00001111 = 8.0
cwmfjordbankglyphsvextquiz = 122.21143275636976
aaaaaaaa = -0.0
Magische Kraken-Urne
quelle