entropy.lisp

;; Shannon Entropy
;; Can be used against strings
;; Requires Alexandria and a rewrite. :-)

(defun entropy (vector)
  (let ((pmf (make-hash-table))
        (counter 0))

    ;; Count up the values O(n)
    (loop for e across vector
          do
             (incf (gethash e pmf 0))
             (incf counter))

    ;; Build the frequency - O(m) (m <= n)
    (maphash
     #'(lambda (k v)
         (setf (gethash k pmf)
               (/ v counter)))
     pmf)

    ;; sum. O(n^2) here, which is foolish. but easy at 1:30 AM.
    (- (reduce #'+
               (mapcar #'(lambda (p-pmf)
                           (*
                            p-pmf
                            (log2 p-pmf)))
                       (alexandria:hash-table-values pmf))))))