[Zope-CVS] CVS: Products/ZCTextIndex - Index.py:1.1.2.10

[Jeremy Hylton]

Update of /cvs-repository/Products/ZCTextIndex
In directory cvs.zope.org:/tmp/cvs-serv8005

Modified Files:
      Tag: TextIndexDS9-branch
	Index.py 
Log Message:
Correct implementation of the cosine() function from Managing Gigabytes.

Store results and scaled ints instead of floats, using function
scaled_int() that returns a float * 256.  I'm guessing this is
sufficient precision for ranking, because we're going to return a
percentage relevance based on the cosine.

The comment block explains the calculations in modest detail.

     # Most of the computation for computing a relevance score for the
     # document occurs in the search() method.  The code currently
     # implements the cosine similarity function described in Managing
     # Gigabytes, eq. 4.3, p. 187.  The index_object() method
     # precomputes some values that are independent of the particular
     # query.
 
     # The equation is:
     # sum = 1/W(d) * 1/W(q) + sum(for t in Q^D: w(d,t) * w(q,t))
     # where w(d, t) = 1 + log f(d, t)
     #       w(q, t) = log(1 + N/f(t))
     #       W(d) = sqrt(sum(for t in D: w(d, t) ** 2))
     #       W(q) = sqrt(sum(for t in Q: w(q, t) ** 2))

The function doc_term_weight() computes w(d, t).
The function query_term_weight() computes w(q, t).
The method query_weight() computes W(q).
The attribute self._docweight[d] stores W(d),
    which is computed by _get_frequencies().

Add a bunch of helper functions _get_xxx() to help test the
implementation.  One potential risk is that these _get_xxx() methods
need to stay in sync with the computations that occur in the actual
search and indexing methods, which don't call the _get_xxx() methods.

I think this is an acceptable risk because the _get_xxx() methods only
test intermediate steps in the computation of the cosine.  The unit
tests also test the final cosine; the _get_xxx() methods are primarily
helpful for investigating the details if the cosine is wrong.  It's
unlikely that the code will fail in a way that the cosine is still
computed correctly <wink>.

XXX The code could use more comments.




=== Products/ZCTextIndex/Index.py 1.1.2.9 => 1.1.2.10 ===
 from Products.ZCTextIndex.IIndex import IIndex
 
+def scaled_int(f):
+    return int(f * 256)
 
 class Index:
     __implements__ = IIndex
@@ -40,6 +42,20 @@
         # used for un-indexing
         self._docwords = IOBTree()
 
+    # Most of the computation for computing a relevance score for the
+    # document occurs in the search() method.  The code currently
+    # implements the cosine similarity function described in Managing
+    # Gigabytes, eq. 4.3, p. 187.  The index_object() method
+    # precomputes some values that are independent of the particular
+    # query.
+
+    # The equation is:
+    # sum = 1/W(d) * 1/W(q) + sum(for t in Q^D: w(d,t) * w(q,t))
+    # where w(d, t) = 1 + log f(d, t)
+    #       w(q, t) = log(1 + N/f(t))
+    #       W(d) = sqrt(sum(for t in D: w(d, t) ** 2))
+    #       W(q) = sqrt(sum(for t in Q: w(q, t) ** 2))
+
     def index_doc(self, docid, text, threshold=None):
         wids = self._lexicon.sourceToWordIds(text)
         freqs, docweight = self._get_frequencies(wids)
@@ -63,26 +79,33 @@
         N = len(self._docweight)
         for wid in wids:
             map = self._wordinfo[wid]
-            inv = invfreq(N, len(map))
-            for docid, f in map.items():
-                w = f * inv / self._docweight[docid]
-                result[docid] = result.get(docid, 0) + w
+            idf = query_term_weight(len(map), N)
+            for docid, tf in map.items():
+                w = tf * idf / self._docweight[docid]
+                result[docid] = int(result.get(docid, 0) + w)
         return result
 
     def query_weight(self, terms):
         wids = []
         for term in terms:
             wids += self._lexicon.termToWordIds(term)
-        return self._get_frequencies(wids)[1]
+        N = len(self._docweight)
+        sum = 0
+        for wid in wids:
+            wt = math.log(1 + N / len(self._wordinfo[wid]))
+            sum += wt ** 2
+        return scaled_int(math.sqrt(sum))
 
     def _get_frequencies(self, wids):
+        """Return individual doc-term weights and docweight."""
+        # computes w(d, t) for each term and W(d)
         d = {}
         for wid in wids:
             d[wid] = d.get(wid, 0) + 1
         Wsquares = 0
         freqs = []
         for wid, count in d.items():
-            f = frequency(count)
+            f = doc_term_weight(count)
             Wsquares += f ** 2
             freqs.append((wid, f))
         return freqs, int(math.sqrt(Wsquares))
@@ -104,9 +127,35 @@
         del map[docid]
         self._wordinfo[wid] = map
 
-def frequency(count):
-    # XXX the logarithm calculations need to be added here
-    return count
+    # some helper method included to support unit tests
+    def _get_wdt(self, d, t):
+        wid, = self._lexicon.termToWordIds(t)
+        map = self._wordinfo[wid]
+        return map.get(d, 0)
+
+    def _get_Wd(self, d):
+        return self._docweight[d]
+
+    def _get_ft(self, t):
+        wid, = self._lexicon.termToWordIds(t)
+        return len(self._wordinfo[wid])
+
+    def _get_wt(self, t):
+        wid, = self._lexicon.termToWordIds(t)
+        map = self._wordinfo[wid]
+        return scaled_int(math.log(1 + len(self._docweight) / float(len(map))))
+
+def doc_term_weight(count):
+    """Return the doc-term weight for a term that appears count times."""
+    # implements w(d, t) = 1 + log f(d, t)
+    return scaled_int(1 + math.log(count))
+
+def query_term_weight(term_count, num_terms):
+    """Return the query-term weight for a term,
+
+    that appears term_count times in a collection with num_terms
+    unique terms.
+    """
+    # implements w(q, t) = log(1 + N/f(t))
+    return scaled_int(math.log(1 + float(num_terms) / term_count))
 
-def invfreq(N, ft):
-    return 1 + (N / ft)