← Back to branch summary

~ubuntu-branches/ubuntu/natty/moin/natty-updates

« back to all changes in this revision

Viewing changes to MoinMoin/support/lupy/search/boolean.py

  • Committer: Bazaar Package Importer
  • Author(s): Jonas Smedegaard
  • Date: 2008-06-22 21:17:13 UTC
  • mfrom: (0.9.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20080622211713-fpo2zrq3s5dfecxg
Tags: 1.7.0-3
Simplify /etc/moin/wikilist format: "USER URL" (drop unneeded middle
CONFIG_DIR that was wrongly advertised as DATA_DIR).  Make
moin-mass-migrate handle both formats and warn about deprecation of
the old one.

Show diffs side-by-side

added added

removed removed

Lines of Context:
MoinMoin/support/lupy/search/boolean.py
1
 
# This module is part of the Lupy project and is Copyright 2003 Amir
2
 
# Bakhtiar (amir@divmod.org). This is free software; you can redistribute
3
 
# it and/or modify it under the terms of version 2.1 of the GNU Lesser
4
 
# General Public License as published by the Free Software Foundation.
5
 
 
6
 
import itertools
7
 
import similarity
8
 
import traceback
9
 
 
10
 
class BooleanQuery:
11
 
    """A Query that matches documents matching boolean combinations of
12
 
    other queries, typically L{lupy.search.term.TermQuery}s or L{lupy.search.phrase.PhraseQuery}s."""
13
 
    
14
 
 
15
 
    def __init__(self):
16
 
        """Constructs an empty boolean query."""
17
 
        
18
 
        self.clauses = []
19
 
        self.boost = 1.0
20
 
 
21
 
    def addClause(self, clause):
22
 
        """Adds a BooleanClause to this query."""
23
 
        self.clauses.append(clause)
24
 
 
25
 
 
26
 
    def add(self, query, required, prohibited):
27
 
        """Adds a clause to a boolean query.  Clauses may be:
28
 
        C{required} which means that documents which I{do not}
29
 
        match this sub-query will I{not} match the boolean query;
30
 
        C{prohibited} which means that documents which I{do}
31
 
        match this sub-query will I{not} match the boolean query; or
32
 
        neither, in which case matched documents are neither prohibited from
33
 
        nor required to match the sub-query.
34
 
        
35
 
        It is an error to specify a clause as both C{required} and
36
 
        C{prohibited}."""
37
 
        
38
 
        self.clauses.append(BooleanClause(query,
39
 
                                          required,
40
 
                                          prohibited))
41
 
        
42
 
 
43
 
    def normalize(self, norm):
44
 
        for c in self.clauses:
45
 
            if not c.prohibited:
46
 
                c.query.normalize(norm)
47
 
 
48
 
    def scorer(self, reader):
49
 
        # optimize zero-term case
50
 
        if len(self.clauses) == 1:
51
 
            # just return term scorer
52
 
            c = self.clauses[0]
53
 
            if not c.prohibited:
54
 
                return c.query.scorer(reader)
55
 
 
56
 
        result = BooleanScorer()
57
 
 
58
 
        for c in self.clauses:
59
 
            subScorer = c.query.scorer(reader)
60
 
            if subScorer is not None:
61
 
                result.add(subScorer, c.required, c.prohibited)
62
 
            elif c.required:
63
 
                return None
64
 
 
65
 
        return result
66
 
            
67
 
 
68
 
    def sumOfSquaredWeights(self, searcher):
69
 
        sum = 0.0
70
 
        
71
 
        for c in self.clauses:
72
 
            if not c.prohibited:
73
 
                # sum sub-query weights
74
 
                sum += c.query.sumOfSquaredWeights(searcher)
75
 
            else:
76
 
                # allow complex queries to initialize themself
77
 
                c.query.sumOfSquaredWeights(searcher)
78
 
        return sum
79
 
 
80
 
 
81
 
    def toString(self, field):
82
 
        """Prints a user-readable version of this query"""
83
 
 
84
 
        buffer = ''
85
 
 
86
 
        for c in self.clauses:
87
 
            if c.prohibited:
88
 
                buffer += '-'
89
 
            elif c.required:
90
 
                buffer += '+'
91
 
 
92
 
            subQuery = c.query
93
 
            if isinstance(subQuery, BooleanQuery):
94
 
                # wrap sub-bools in parens
95
 
                buffer += '('
96
 
                buffer += c.query.toString(field)
97
 
                buffer += ')'
98
 
            else:
99
 
                buffer += c.query.toString(field)
100
 
            
101
 
        return buffer
102
 
 
103
 
class BooleanClause(object):
104
 
    """A clause in a BooleanQuery"""
105
 
 
106
 
    def __init__(self, q, r, p):
107
 
        self.query = q
108
 
        self.required = r
109
 
        self.prohibited = p
110
 
    
111
 
class BooleanScorer:
112
 
    
113
 
    def __init__(self):
114
 
        self.coordFactors = None
115
 
        self.maxCoord = 1
116
 
        self.nextMask = 1
117
 
        self.prohibitedMask = 0
118
 
        self.requiredMask = 0
119
 
        self.scorers = []        
120
 
        self.currentDoc = 0
121
 
        self.validList = []
122
 
        self.table = {}
123
 
        
124
 
    def add(self, scorer, required, prohibited):
125
 
        mask = 0
126
 
        if required or prohibited:
127
 
            if self.nextMask == 0:
128
 
                raise Exception, 'More than 32 required/prohibited clauses in a query.'
129
 
            mask = self.nextMask
130
 
            self.nextMask = self.nextMask << 1
131
 
        else:
132
 
            '???'
133
 
            mask = 0
134
 
            
135
 
        if not prohibited:
136
 
            self.maxCoord += 1
137
 
            
138
 
        if prohibited:
139
 
            # Update prohibited mask
140
 
            self.prohibitedMask |= mask
141
 
        elif required:
142
 
            # Update required mask
143
 
            self.requiredMask |= mask
144
 
            
145
 
        self.scorers.append(SubScorer(scorer, required, prohibited, mask))
146
 
        
147
 
        
148
 
    def computeCoordFactors(self):
149
 
        self.coordFactors = []
150
 
        for i in range(self.maxCoord):
151
 
            self.coordFactors.append(similarity.coord(i, self.maxCoord))
152
 
            
153
 
 
154
 
    def collect(self, doc, score, mask):
155
 
        bucket = self.table.get(doc, None)
156
 
        if bucket is None:
157
 
            #doc, score, bits, coord
158
 
            bucket = [-1, 0, 0, 0]
159
 
            self.table[doc] = bucket            
160
 
        if bucket[0] != doc:
161
 
            # invalid doc
162
 
            # initialize fields
163
 
            bucket[:] = [doc, score, mask, 1]            
164
 
            self.validList.append(bucket)
165
 
        else:
166
 
            # valid bucket
167
 
            # increment score
168
 
            bucket[1] += score
169
 
            # add bits in mask
170
 
            bucket[2] |= mask
171
 
            # increment coord
172
 
            bucket[3] += 1 # XXX
173
 
            #print doc, score, mask, bucket
174
 
 
175
 
            
176
 
    def score(self, maxDoc):
177
 
        if self.coordFactors is None:
178
 
            self.computeCoordFactors()
179
 
        for t in self.scorers:
180
 
            #print "SCORER %r" % t.scorer
181
 
            for d,score in t.scorer.score(maxDoc):
182
 
                #print "DOCUMENT %r %r" % (d, score)
183
 
                self.collect(d,score,t.mask)
184
 
        return self.collectHits()
185
 
    
186
 
    def collectHits(self):        
187
 
        for bucket in self.validList:
188
 
            doc, score, bits, coord = bucket
189
 
            if (bits & self.prohibitedMask) == 0 and (bits & self.requiredMask) == self.requiredMask:
190
 
                # if prohibited and required check out
191
 
                # add to results
192
 
                #print "CollectHits:", doc, score, self.coordFactors, coord
193
 
                try:
194
 
                    scorecf = score * self.coordFactors[coord]
195
 
                except IndexError, err: # XXX ugly way to avoid it crashing 8(
196
 
                    scorecf = 0.0
197
 
                yield (doc, scorecf)
198
 
        del self.validList[:]
199
 
            
200
 
                
201
 
class SubScorer(object):
202
 
    
203
 
    def __init__(self, scorer, required, prohibited, mask):
204
 
      self.scorer = scorer
205
 
      self.required = required
206
 
      self.prohibited = prohibited
207
 
      self.mask = mask
208
 
    
209
 
    
210
 
    
211