Added images for blog, refactored code

[cipher-tools.git] / support / norms.py

diff --git a/support/norms.py b/support/norms.py
index eb436c3b8163141a3ada1f1f02f8be741d6f47fb..f131ad597035bbb905a1ec0b875291a49dca8aea 100644 (file)
--- a/support/norms.py
+++ b/support/norms.py
@@ -1,43 +1,35 @@
 import collections
 from math import log10
 
 import collections
 from math import log10
 

-def normalise(frequencies):
-    """Scale a set of frequencies so they sum to one
-    
-    >>> sorted(normalise({1: 1, 2: 0}).items())
-    [(1, 1.0), (2, 0.0)]
-    >>> sorted(normalise({1: 1, 2: 1}).items())
-    [(1, 0.5), (2, 0.5)]
-    >>> sorted(normalise({1: 1, 2: 1, 3: 1}).items()) # doctest: +ELLIPSIS
-    [(1, 0.333...), (2, 0.333...), (3, 0.333...)]
-    >>> sorted(normalise({1: 1, 2: 2, 3: 1}).items())
-    [(1, 0.25), (2, 0.5), (3, 0.25)]
-    """
-    length = sum(f for f in frequencies.values())
-    return collections.defaultdict(int, ((k, v / length) 
-        for (k, v) in frequencies.items()))

 
 

-def euclidean_scale(frequencies):
-    """Scale a set of frequencies so they have a unit euclidean length
-    
-    >>> sorted(euclidean_scale({1: 1, 2: 0}).items())
-    [(1, 1.0), (2, 0.0)]
-    >>> sorted(euclidean_scale({1: 1, 2: 1}).items()) # doctest: +ELLIPSIS
-    [(1, 0.7071067...), (2, 0.7071067...)]
-    >>> sorted(euclidean_scale({1: 1, 2: 1, 3: 1}).items()) # doctest: +ELLIPSIS
-    [(1, 0.577350...), (2, 0.577350...), (3, 0.577350...)]
-    >>> sorted(euclidean_scale({1: 1, 2: 2, 3: 1}).items()) # doctest: +ELLIPSIS
-    [(1, 0.408248...), (2, 0.81649658...), (3, 0.408248...)]
+def lp(v1, v2=None, p=2):
+    """Find the L_p norm. If passed one vector, find the length of that vector.
+    If passed two vectors, find the length of the difference between them.

     """
     """

-    length = sum([f ** 2 for f in frequencies.values()]) ** 0.5
-    return collections.defaultdict(int, ((k, v / length) 
-        for (k, v) in frequencies.items()))
+    if v2:
+        vec = {k: abs(v1[k] - v2[k]) for k in (v1.keys() | v2.keys())}
+    else:
+        vec = v1
+    return sum(v ** p for v in vec.values()) ** (1.0 / p)

 
 

-def identity_scale(frequencies):
-    return frequencies
-        
+def l1(v1, v2=None):
+    """Finds the distances between two frequency profiles, expressed as 
+    dictionaries. Assumes every key in frequencies1 is also in frequencies2
+
+    >>> l1({'a':1, 'b':1, 'c':1}, {'a':1, 'b':1, 'c':1})
+    0.0
+    >>> l1({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1})
+    3.0
+    >>> l1(normalise({'a':2, 'b':2, 'c':2}), normalise({'a':1, 'b':1, 'c':1}))
+    0.0
+    >>> l1({'a':0, 'b':2, 'c':0}, {'a':1, 'b':1, 'c':1})
+    3.0
+    >>> l1({'a':0, 'b':1}, {'a':1, 'b':1})
+    1.0
+    """    
+    return lp(v1, v2, 1)

 
 

-def l2(frequencies1, frequencies2):
+def l2(v1, v2=None):

     """Finds the distances between two frequency profiles, expressed as dictionaries.
     Assumes every key in frequencies1 is also in frequencies2
     
     """Finds the distances between two frequency profiles, expressed as dictionaries.
     Assumes every key in frequencies1 is also in frequencies2
     


@@ -55,33 +47,9 @@ def l2(frequencies1, frequencies2):
     >>> l2({'a':0, 'b':1}, {'a':1, 'b':1})
     1.0
     """
     >>> l2({'a':0, 'b':1}, {'a':1, 'b':1})
     1.0
     """

-    total = 0
-    for k in frequencies1:
-        total += (frequencies1[k] - frequencies2[k]) ** 2
-    return total ** 0.5
-euclidean_distance = l2
-
-def l1(frequencies1, frequencies2):
-    """Finds the distances between two frequency profiles, expressed as 
-    dictionaries. Assumes every key in frequencies1 is also in frequencies2
-
-    >>> l1({'a':1, 'b':1, 'c':1}, {'a':1, 'b':1, 'c':1})
-    0
-    >>> l1({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1})
-    3
-    >>> l1(normalise({'a':2, 'b':2, 'c':2}), normalise({'a':1, 'b':1, 'c':1}))
-    0.0
-    >>> l1({'a':0, 'b':2, 'c':0}, {'a':1, 'b':1, 'c':1})
-    3
-    >>> l1({'a':0, 'b':1}, {'a':1, 'b':1})
-    1
-    """
-    total = 0
-    for k in frequencies1:
-        total += abs(frequencies1[k] - frequencies2[k])
-    return total
+    return lp(v1, v2, 2)

 
 

-def l3(frequencies1, frequencies2):
+def l3(v1, v2=None):

     """Finds the distances between two frequency profiles, expressed as 
     dictionaries. Assumes every key in frequencies1 is also in frequencies2
 
     """Finds the distances between two frequency profiles, expressed as 
     dictionaries. Assumes every key in frequencies1 is also in frequencies2
 


@@ -99,10 +67,53 @@ def l3(frequencies1, frequencies2):
     >>> l3(normalise({'a':0, 'b':1}), normalise({'a':1, 'b':1})) # doctest: +ELLIPSIS
     0.6299605249...
     """
     >>> l3(normalise({'a':0, 'b':1}), normalise({'a':1, 'b':1})) # doctest: +ELLIPSIS
     0.6299605249...
     """

-    total = 0
-    for k in frequencies1:
-        total += abs(frequencies1[k] - frequencies2[k]) ** 3
-    return total ** (1/3)
+    return lp(v1, v2, 3)
+
+def linf(v1, v2=None):    
+    if v2:
+        vec = {k: abs(v1[k] - v2[k]) for k in (v1.keys() | v2.keys())}
+    else:
+        vec = v1
+    return max(v for v in vec.values())
+
+
+def scale(frequencies, norm=l2):
+    length = norm(frequencies)
+    return collections.defaultdict(int, 
+        {k: v / length for k, v in frequencies.items()})
+
+def l2_scale(f):
+    """Scale a set of frequencies so they have a unit euclidean length
+    
+    >>> sorted(euclidean_scale({1: 1, 2: 0}).items())
+    [(1, 1.0), (2, 0.0)]
+    >>> sorted(euclidean_scale({1: 1, 2: 1}).items()) # doctest: +ELLIPSIS
+    [(1, 0.7071067...), (2, 0.7071067...)]
+    >>> sorted(euclidean_scale({1: 1, 2: 1, 3: 1}).items()) # doctest: +ELLIPSIS
+    [(1, 0.577350...), (2, 0.577350...), (3, 0.577350...)]
+    >>> sorted(euclidean_scale({1: 1, 2: 2, 3: 1}).items()) # doctest: +ELLIPSIS
+    [(1, 0.408248...), (2, 0.81649658...), (3, 0.408248...)]
+    """
+    return scale(f, l2)
+
+def l1_scale(f):
+    """Scale a set of frequencies so they sum to one
+    
+    >>> sorted(normalise({1: 1, 2: 0}).items())
+    [(1, 1.0), (2, 0.0)]
+    >>> sorted(normalise({1: 1, 2: 1}).items())
+    [(1, 0.5), (2, 0.5)]
+    >>> sorted(normalise({1: 1, 2: 1, 3: 1}).items()) # doctest: +ELLIPSIS
+    [(1, 0.333...), (2, 0.333...), (3, 0.333...)]
+    >>> sorted(normalise({1: 1, 2: 2, 3: 1}).items())
+    [(1, 0.25), (2, 0.5), (3, 0.25)]
+    """    
+    return scale(f, l1)
+
+normalise = l1_scale
+euclidean_distance = l2
+euclidean_scale = l2_scale
+

 
 def geometric_mean(frequencies1, frequencies2):
     """Finds the geometric mean of the absolute differences between two frequency profiles, 
 
 def geometric_mean(frequencies1, frequencies2):
     """Finds the geometric mean of the absolute differences between two frequency profiles, 


@@ -110,11 +121,11 @@ def geometric_mean(frequencies1, frequencies2):
     Assumes every key in frequencies1 is also in frequencies2
     
     >>> geometric_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1})
     Assumes every key in frequencies1 is also in frequencies2
     
     >>> geometric_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1})

-    1
+    1.0

     >>> geometric_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1})
     >>> geometric_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':1, 'c':1})

-    1
+    1.0

     >>> geometric_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':5, 'c':1})
     >>> geometric_mean({'a':2, 'b':2, 'c':2}, {'a':1, 'b':5, 'c':1})

-    3
+    3.0

     >>> geometric_mean(normalise({'a':2, 'b':2, 'c':2}), \
                        normalise({'a':1, 'b':5, 'c':1})) # doctest: +ELLIPSIS
     0.01382140...
     >>> geometric_mean(normalise({'a':2, 'b':2, 'c':2}), \
                        normalise({'a':1, 'b':5, 'c':1})) # doctest: +ELLIPSIS
     0.01382140...


@@ -125,7 +136,7 @@ def geometric_mean(frequencies1, frequencies2):
                        normalise({'a':1, 'b':1, 'c':0})) # doctest: +ELLIPSIS
     0.009259259...
     """
                        normalise({'a':1, 'b':1, 'c':0})) # doctest: +ELLIPSIS
     0.009259259...
     """

-    total = 1
+    total = 1.0

     for k in frequencies1:
         total *= abs(frequencies1[k] - frequencies2[k])
     return total
     for k in frequencies1:
         total *= abs(frequencies1[k] - frequencies2[k])
     return total


@@ -146,16 +157,16 @@ def harmonic_mean(frequencies1, frequencies2):
     0.228571428571...
     >>> harmonic_mean(normalise({'a':2, 'b':2, 'c':2}), \
                       normalise({'a':1, 'b':1, 'c':1})) # doctest: +ELLIPSIS
     0.228571428571...
     >>> harmonic_mean(normalise({'a':2, 'b':2, 'c':2}), \
                       normalise({'a':1, 'b':1, 'c':1})) # doctest: +ELLIPSIS

-    0
+    0.0

     >>> harmonic_mean(normalise({'a':2, 'b':2, 'c':2}), \
                       normalise({'a':1, 'b':1, 'c':0})) # doctest: +ELLIPSIS
     0.2
     """
     >>> harmonic_mean(normalise({'a':2, 'b':2, 'c':2}), \
                       normalise({'a':1, 'b':1, 'c':0})) # doctest: +ELLIPSIS
     0.2
     """

-    total = 0
+    total = 0.0

     for k in frequencies1:
         if abs(frequencies1[k] - frequencies2[k]) == 0:
     for k in frequencies1:
         if abs(frequencies1[k] - frequencies2[k]) == 0:

-            return 0
-        total += 1 / abs(frequencies1[k] - frequencies2[k])
+            return 0.0
+        total += 1.0 / abs(frequencies1[k] - frequencies2[k])

     return len(frequencies1) / total
 
 
     return len(frequencies1) / total