[ZopeCVS] CVS: Products/ZCTextIndex  Index.py:1.1.2.31
Guido van Rossum
guido@python.org
Mon, 6 May 2002 09:13:43 0400
Update of /cvsrepository/Products/ZCTextIndex
In directory cvs.zope.org:/tmp/cvsserv15806
Modified Files:
Tag: TextIndexDS9branch
Index.py
Log Message:
This is the new Index.py, which stores scaled_int(w(d, t) / W(d)) in
_wordinfo[t], so that the inner loop in search() can be replaced by a
single constant scale factor, applied by weightedUnion.
With a small change to _get_wdt() and one change in ZCTest (because
the results are now scaled differently), this now passes the test
suite, so it can't be all bad. :)
On a corpus of 73420 email messages, a search for an uncommon term is
now immeasurably fast (less than 10 msec); a search for a very common
term (occurring 39379 times) takes 250 msec, another even more common
term (52286 hits) takes 320 msec, and combining these two takes about
the sum of those times.
Tim brought up some good issues with the new approach, so it needs to
be tweaked more, especially to avoid losing too much precision: the
values stored in _wordinfo are small, which is good since it makes for
small pickles, but often very small, which gives us very little to
work with (and for collections with large documents this will be even
worse). But first I'd like to work on refactoring how the query
engine and the query parser connect to the index.
=== Products/ZCTextIndex/Index.py 1.1.2.30 => 1.1.2.31 ===
#
##############################################################################
"""Text Index.
Plugin text index for ZCatalog, with relevance ranking.
"""
+"""Full text index with relevance ranking."""
import math
from BTrees.IOBTree import IOBTree
from BTrees.IIBTree import IIBTree, IIBucket, IISet
+from BTrees.IIBTree import IIBTree, IIBucket, IISet, weightedUnion
from Products.ZCTextIndex.IIndex import IIndex
@@ 40,6 +38,7 @@
return int(f * scale + 0.5)
class Index:
+
__implements__ = IIndex
def __init__(self, lexicon):
@@ 55,6 +54,9 @@
# used for unindexing
self._docwords = IOBTree()
+ def length(self):
+ return len(self._docweight)
+
# 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
@@ 73,9 +75,7 @@
#
# w(d, t) = 1 + log f(d, t)
# computed by doc_term_weight(); for a given word t,
 # self._wordinfo[t] is a map from d to w(d, t). To save space
 # in binary pickles, we actually store f(d, t) if that's < 256.
 # In that case, WDT[f(d, t)] retrieves the correct w(d, t).
+ # self._wordinfo[t] is a map from d to w(d, t).
#
# w(q, t) = log(1 + N/f(t))
# computed by query_term_weight()
@@ 104,17 +104,21 @@
def search(self, term):
wids = self._lexicon.termToWordIds(term)
 result = IIBucket()
+ if not wids:
+ return IIBucket()
N = float(len(self._docweight))
+ L = []
for wid in wids:
d2w = self._wordinfo[wid] # maps docid to w(docid, wid)
idf = query_term_weight(len(d2w), N) # this is an unscaled float
 for docid, tf in d2w.items():
 if tf < 256:
 tf = WDT[tf]
 # scaled int * unscaled float / scaled int > unscaled float
 w = tf * idf / self._docweight[docid]
 result[docid] = result.get(docid, 0) + scaled_int(w)
+ #print "idf = %.3f" % idf
+ if isinstance(d2w, type({})):
+ d2w = IIBucket(d2w)
+ L.append((d2w, scaled_int(idf)))
+ L.sort(lambda x, y: cmp(len(x[0]), len(y[0])))
+ result = IIBTree()
+ for d2w, weight in L:
+ dummy, result = weightedUnion(result, d2w, 1, weight)
return result
def query_weight(self, terms):
@@ 122,10 +126,10 @@
for term in terms:
wids += self._lexicon.termToWordIds(term)
N = float(len(self._docweight))
 sum = 0.
+ sum = 0.0
for wid in wids:
 wt = math.log(1. + N / len(self._wordinfo[wid]))
 sum += wt ** 2.
+ wt = math.log(1.0 + N / len(self._wordinfo[wid]))
+ sum += wt ** 2.0
return scaled_int(math.sqrt(sum))
def _get_frequencies(self, wids):
@@ 138,17 +142,20 @@
d = {}
for wid in wids:
d[wid] = d.get(wid, 0) + 1
 Wsquares = 0.
+ Wsquares = 0.0
weights = []
push = weights.append
for count in d.values():
w = doc_term_weight(count)
Wsquares += w * w
 if count < 256:
 push(count) # 1 byte in a binary pickle
 else:
 push(scaled_int(w)) # 2 bytes in a binary pickle, and rare
 return d.keys(), weights, scaled_int(math.sqrt(Wsquares))
+ push(w)
+ W = math.sqrt(Wsquares)
+ #print "W = %.3f" % W
+ for i in xrange(len(weights)):
+ #print i, ":", "%.3f" % weights[i],
+ weights[i] = scaled_int(weights[i] / W)
+ #print ">", weights[i]
+ return d.keys(), weights, scaled_int(W)
DICT_CUTOFF = 10
@@ 177,34 +184,26 @@
try:
map = self._wordinfo[wid]
except KeyError:
 map = {}
 # _add_wordinfo() is called for each update. If the map size
 # exceeds the DICT_CUTOFF, convert to an IIBTree.
 if len(map) == self.DICT_CUTOFF:
 map = IIBTree(map)
+ self._wordinfo[wid] = map = {}
+ else:
+ # _add_wordinfo() is called for each update. If the map
+ # size exceeds the DICT_CUTOFF, convert to an IIBTree.
+ if len(map) == self.DICT_CUTOFF:
+ self._wordinfo[wid] = map = IIBTree(map)
map[docid] = f
 self._wordinfo[wid] = map
def _del_wordinfo(self, wid, docid):
map = self._wordinfo[wid]
 if len(map) == 1:
 assert map.has_key(docid)
 del self._wordinfo[wid]
 return
del map[docid]
 self._wordinfo[wid] = map
+ if len(map) == 0:
+ del self._wordinfo[wid]
+
+ # The rest are helper methods to support unit tests
 # some helper method included to support unit tests
def _get_wdt(self, d, t):
wid, = self._lexicon.termToWordIds(t)
map = self._wordinfo[wid]
 w = map.get(d, 0)
 if w == 0:
 return 0
 elif w < 256:
 return WDT[w]
 else:
 return w
+ return map.get(d, 0) * self._docweight[d] / SCALE_FACTOR
def _get_Wd(self, d):
return self._docweight[d]
@@ 221,7 +220,7 @@
def doc_term_weight(count):
"""Return the docterm weight for a term that appears count times."""
# implements w(d, t) = 1 + log f(d, t)
 return 1. + math.log(count)
+ return 1.0 + math.log(count)
def query_term_weight(term_count, num_items):
"""Return the queryterm weight for a term,
@@ 230,17 +229,4 @@
total items.
"""
# implements w(q, t) = log(1 + N/f(t))
 return math.log(1. + float(num_items) / term_count)

# For 0 < i < 256, WDT[i] is the integer scaled value of doc_term_weight(i).
# WDT[0] is None, because doc_term_weight(0) should never happen, and
# returning None then should quickly lead to an exception.
WDT = [scaled_int(doc_term_weight(i)) for i in range(1, 256)]
del i
WDT.insert(0, None)

# Upon reading up a "w(d, t)" value, we need to know whether it's a true
# scaled w(d,t), or a raw count that must be used to index WDT[] to get
# the true scaled w(d,t). The key is that for raw counts >= 256, their
# scaled w(d,t) values are greater than 255.
assert scaled_int(doc_term_weight(256)) > 255
+ return math.log(1.0 + float(num_items) / term_count)