From: Erik Garrison <erik@hypervolu.me>
Date: Sun, 24 Oct 2010 20:28:15 +0000 (-0400)
Subject: added shannon_H entropy metric for each revision
X-Git-Url: https://projects.mako.cc/source/wikiq/commitdiff_plain/ae96c7a9d99998ad0be4bb8aa382b92df32533a5

added shannon_H entropy metric for each revision
---

diff --git a/Makefile b/Makefile
index bf436d0..fc80d1a 100644
--- a/Makefile
+++ b/Makefile
@@ -1,13 +1,17 @@
 CXX = g++
 CFLAGS = -O3
+OBJECTS = disorder.o
 
 all: wikiq
 
-wikiq: wikiq.c
-	$(CXX) $(CFLAGS) wikiq.c -o wikiq -lexpat
+wikiq: wikiq.c $(OBJECTS)
+	$(CXX) $(CFLAGS) wikiq.c $(OBJECTS) -o wikiq -lexpat
+
+disorder.o: disorder.c
+	$(CXX) $(CFLAGS) -c disorder.c
 
 clean:
-	rm -f wikiq
+	rm -f wikiq $(OBJECTS)
 
 gprof:
 	$(MAKE) CFLAGS=-pg wikiq
diff --git a/disorder.c b/disorder.c
new file mode 100644
index 0000000..a5f7c35
--- /dev/null
+++ b/disorder.c
@@ -0,0 +1,192 @@
+/***************************************************************************
+ *  libdisorder: A Library for Measuring Byte Stream Entropy
+ *  Copyright (C) 2010 Michael E. Locasto
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful, but
+ *  WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the:
+ *       Free Software Foundation, Inc.
+ *       59 Temple Place, Suite 330
+ *       Boston, MA  02111-1307  USA
+ *
+ * $Id$
+ **************************************************************************/
+
+#include <math.h> //for log2()
+#include <stdio.h> //for NULL
+#include "disorder.h"
+
+#if defined(__FreeBSD__)
+#define        log2(x) (log((x)) * (1./M_LN2))
+#endif
+
+/** Frequecies for each byte */
+static int m_token_freqs[LIBDO_MAX_BYTES]; //frequency of each token in sample
+static float m_token_probs[LIBDO_MAX_BYTES]; //P(each token appearing)
+static int m_num_tokens = 0; //actual number of `seen' tokens, max 256 
+static float m_maxent = 0.0;
+static float m_ratio = 0.0;
+static int LIBDISORDER_INITIALIZED = 0;
+
+static void
+initialize_lib()
+{
+  int i = 0;
+  if(1==LIBDISORDER_INITIALIZED)
+    return;
+
+  m_num_tokens = 0;
+
+  for(i=0;i<LIBDO_MAX_BYTES;i++)
+  {
+    m_token_freqs[i]=0;
+    m_token_probs[i]=0.0;
+  }
+
+  LIBDISORDER_INITIALIZED = 1;
+}
+
+/**
+ * Set m_num_tokens by iterating over m_token_freq[] and maintaining
+ * a counter of each position that does not hold the value of zero.
+ */
+static void
+count_num_tokens()
+{
+  int i = 0;
+  int counter = 0;
+  for(i=0;i<LIBDO_MAX_BYTES;i++)
+  {
+    if(0!=m_token_freqs[i])
+    {
+      counter++;
+    }
+  }
+  m_num_tokens = counter;
+  return;
+}
+
+/**
+ * Sum frequencies for each token (i.e., byte values 0 through 255)
+ * We assume the `length' parameter is correct.
+ *
+ * This function is available only to functions in this file.
+ */
+static void
+get_token_frequencies(char* buf, 
+		      long long length)
+{
+  int i=0;
+  char* itr=NULL;
+  unsigned char c=0;
+
+  itr = buf;
+
+  //reset number of tokens
+  m_num_tokens = 0;
+
+  //make sure freqency and probability arrays are cleared
+  for(i=0;i<LIBDO_MAX_BYTES;i++)
+  {
+    m_token_freqs[i] = 0;
+    m_token_probs[i] = 0.0;
+  }
+
+  for(i=0;i<length;i++)
+  {
+    c = (unsigned char)*itr;
+    //assert(0<=c<LIBDO_MAX_BYTES);
+    m_token_freqs[c]++;
+    itr++;
+  }
+}
+
+/**
+ * Return entropy (in bits) of this buffer of bytes. We assume that the
+ * `length' parameter is correct. This implementation is a translation
+ * of the PHP code found here:
+ *
+ *    http://onlamp.com/pub/a/php/2005/01/06/entropy.html
+ *
+ * with a helpful hint on the `foreach' statement from here:
+ *
+ *    http://php.net/manual/en/control-structures.foreach.php
+ */
+float
+shannon_H(char* buf, 
+	  long long length)
+{
+  int i = 0;
+  float bits = 0.0;
+  char* itr=NULL; //values of itr should be zero to 255
+  unsigned char token;
+  int num_events = 0; //`length' parameter
+  float freq = 0.0; //loop variable for holding freq from m_token_freq[]
+  float entropy = 0.0; //running entropy sum
+
+  if(NULL==buf || 0==length)
+    return 0.0;
+
+  if(0==LIBDISORDER_INITIALIZED)
+    initialize_lib();
+
+  itr = buf;
+  m_maxent = 0.0;
+  m_ratio = 0.0;
+  num_events = length;
+  get_token_frequencies(itr, num_events); //modifies m_token_freqs[]
+  //set m_num_tokens by counting unique m_token_freqs entries
+  count_num_tokens(); 
+
+  if(m_num_tokens>LIBDO_MAX_BYTES)
+  {
+    //report error somehow?
+    return 0.0;
+  }
+
+  //iterate through whole m_token_freq array, but only count
+  //spots that have a registered token (i.e., freq>0)
+  for(i=0;i<LIBDO_MAX_BYTES;i++)
+  {
+    if(0!=m_token_freqs[i])
+    {
+      token = i;
+      freq = ((float)m_token_freqs[token]); 
+      m_token_probs[token] = (freq / ((float)num_events));
+      entropy += m_token_probs[token] * log2(m_token_probs[token]);
+    }
+  }
+
+  bits = -1.0 * entropy;
+  m_maxent = log2(m_num_tokens);
+  m_ratio = bits / m_maxent;
+
+  return bits;
+}
+
+int 
+get_num_tokens()
+{
+  return m_num_tokens;
+}
+
+float 
+get_max_entropy()
+{
+  return m_maxent;
+}
+
+float 
+get_entropy_ratio()
+{
+  return m_ratio;
+}
diff --git a/disorder.h b/disorder.h
new file mode 100644
index 0000000..3458774
--- /dev/null
+++ b/disorder.h
@@ -0,0 +1,62 @@
+/***************************************************************************
+ *  libdisorder: A Library for Measuring Byte Stream Entropy
+ *  Copyright (C) 2010 Michael E. Locasto
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful, but
+ *  WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the:
+ *       Free Software Foundation, Inc.
+ *       59 Temple Place, Suite 330
+ *       Boston, MA  02111-1307  USA
+ *
+ * $Id$
+ **************************************************************************/
+
+#ifndef __DISORDER_H_
+#define __DISORDER_H_
+
+/** Max number of bytes (i.e., tokens) */
+#define LIBDO_MAX_BYTES      256
+
+/** A convienance value for clients of this library. Feel free to change
+ * if you plan to use a larger buffer. You can also safely ignore it, as
+ * libdisorder does not use this value internally; it relies on the
+ * client-supplied `length' parameter.
+ *
+ * NB: Might become deprecated because it is potentially misleading and
+ * has zero relationship to any library internal state.
+ */
+#define LIBDO_BUFFER_LEN   16384
+
+/** 
+ * Given a pointer to an array of bytes, return a float indicating the
+ * level of entropy in bits (a number between zero and eight),
+ * assuming a space of 256 possible byte values. The second argument
+ * indicates the number of bytes in the sequence. If this sequence
+ * runs into unallocated memory, this function should fail with a
+ * SIGSEGV.
+ */
+float    shannon_H(char*, long long);
+
+/** Report the number of (unique) tokens seen. This is _not_ the
+    number of individual events seen. For example, if the library sees
+    the string `aaab', the number of events is 4 and the number of
+    tokens is 2. */
+int      get_num_tokens(void);
+
+/** Returns maximum entropy for byte distributions log2(256)=8 bits*/
+float    get_max_entropy(void);
+
+/** Returns the ratio of entropy to maxentropy */
+float    get_entropy_ratio(void);
+
+#endif
diff --git a/wikiq.c b/wikiq.c
index 4d254f2..8920054 100644
--- a/wikiq.c
+++ b/wikiq.c
@@ -10,6 +10,7 @@
 #include <stdlib.h>
 #include "expat.h"
 #include <getopt.h>
+#include "disorder.h"
 
 // timestamp of the form 2003-11-07T00:43:23Z
 #define DATE_LENGTH 10
@@ -225,7 +226,7 @@ write_row(revisionData *data)
     switch (data->output_type)
     {
         case SIMPLE:
-            printf("\t%i\n", (unsigned int) strlen(data->text));
+            printf("\t%i\t%f\n", (unsigned int) strlen(data->text), shannon_H(data->text, data->text_size));
             //printf("\n");
             break;
         case FULL:
@@ -235,40 +236,6 @@ write_row(revisionData *data)
 
 }
 
-char
-*append(char *entry, char *newstr)
-{
-    char *newbuff;
-    int len;
-    len = (strlen(entry)+strlen(newstr))*sizeof(char) + 1;
-    newbuff = (char*) realloc(entry, len);
-    strcat(newbuff, newstr);
-    return newbuff;
-}
-
-char
-*cache(char *entry, char *newstr)
-{
-    char *newbuff;
-    int len;
-    len = strlen(newstr)*sizeof(char) + 1; // include space for the '\0' !
-    newbuff = (char*) malloc(len);
-    strcpy(newbuff,newstr);
-    return newbuff;
-
-}
-
-char
-*store(char *entry, char *newstr)
-{
-    char *newbuff;
-    if (entry == NULL)
-        newbuff = cache(entry, newstr);
-    else 
-        newbuff = append(entry, newstr);
-    return newbuff;
-}
-
 void
 split_timestamp(revisionData *data) 
 {
@@ -278,19 +245,6 @@ split_timestamp(revisionData *data)
     strncpy(data->time, timeinstamp, TIME_LENGTH);
 }
 
-/* currently unused */
-static int
-is_whitespace(char *string) {
-    int len = strlen(string);
-    while (isspace(string[0]) && strlen(string) > 0) {
-        string++;
-    }
-    if (strcmp(string, "") == 0)
-        return 1;
-    else
-        return 0;
-}
-
 // like strncat but with previously known length
 char*
 strlcatn(char *dest, const char *src, size_t dest_len, size_t n)