You are viewing a plain text version of this content. The canonical link for it is here.
Posted to java-user@lucene.apache.org by Chris Harris <ry...@gmail.com> on 2012/05/16 23:11:20 UTC
Approches/semantics for arbitrarily combining boolean and proximity
search operators?
I'm working on a product for librarians and similar people, who
apparently expect to be able to combine classic boolean operators
(i.e. AND, OR, NOT) with proximity operators (especially w/n and pre/n
-- which basically map to unordered and ordered SpanQueries with slop
n, respectively) in unrestricted fashion. For example, users appear to
believe that not only are relatively easy-to-grasp queries like these
legitimate:
medical w/5 agreement
(medical w/5 agreement) and (doctor w/10 rights)
but also crazier ones, perhaps like
agreement w/5 (medical and companion)
(dog or dragon) w/5 (cat and cow)
(daisy and (dog or dragon)) w/25 (cat not cow)
What I've noticed is that it's not always obvious how to interpret
such queries; it's not always obvious what the user had in mind, nor
how you might construct a Lucene query to carry out the user's intent.
Therefore, to broaden my understanding of the problem, I'd like to
learn more about schemes people may have used/proposed to assign
meanings to arbitrary combinations/nestings of, say, the AND, OR, NOT,
W, and PRE operators. Ultimately I'm interested in parsing queries
into Lucene Query objects (perhaps SpanQuery objects). But I'm also
interested in a more abstract/mathematical discussion. (After all, I'm
open to the possibility that the best implementation requires new
Query classes to be written.)
So far I've found two main sources of inspiration, but I'm not 100%
satisfied with either:
1. Mark Miller's no-longer-maintained qsol query parser
(https://github.com/markrmiller/qsol)
The premise of qsol seems to be that you can simplify any arbitrary
combination of boolean and proximity operators into an equivalent
expression where boolean operators can contain proximity operators,
but where no boolean operator appears nested inside a proximity
operator. (With the exception of OR, which maps nicely to a
SpanOrQuery...) This is a convenient transformation, because then you
can readily express the query in terms of existing SpanQuery and
BooleanQuery classes.
The main principle that qsol uses for these transformations might be
sloppily summarized as, "You can distribute any boolean operator over
any proximity operator".
Thus, for example, input query
agreement w/5 (medical and companion)
gets morphed into something along along the lines of
(agreement w/5 medical) and (medical w/5 companion)
In closer-to-Lucene syntax, that's
+(spanNear(slop=5, inOrder=false, ageement, medical))
+(spanNear(slop=5, inOrder=false, medical, companion))
I like how qsol is able to provide at least *some* Lucene-executable
Query for every input query string, and I like how it seems to take a
single principle of distributing booleans over proximities and see it
through pretty systematically.
Unfortunately, the Query objects returned by qsol don't always align
perfectly with what I imagine user intent to be.
For example, when my users try queries like
agreement w/5 (medical and companion)
I believe they are seeking spans where a single occurrence of
"agreement" is near both "medical" and "companion". qsol will find
documents like that, but it will also return what I think I consider
to be spurious matches, namely docs where there's an "agreement" near
"medical" and an "agreement" near "companion", but no "agreement"
that's near both.
Also non-intuitive is that qsol generates rather different Query
objects for these two queries:
(dog or dragon) w/5 (cat and cow)
(cat and cow) w/5 (dog or dragon)
The former maps to something like
((dog w/5 cat) AND (dog w/5 cow)) OR ((dragon w/5 cat) AND (dragon w/5 cow))
while the latter maps to something like
((cat w/5 dog) OR (cat w/5 dragon)) AND ((cow w/5 dog) OR (cow w/5 dragon))
I'm not sure there's an obviously better thing for qsol to do with
these, but it would be nice if w/5 were a symmetric operation.
Note: The above does not reflect qsol's actual syntax, only its semantics.
2. Minimum interval semantics
This approach is reflected in the Lucene "positions branch"
(PositionIntervalIterator stuff). It's also nicely described in the
paper "An Algebra for Structured Text Search and A Framework for its
Implementation" (Clarke, Cormack, Burkowski).
I don't know of a Lucene query parser built around this stuff yet, but
it seems possible to construct one. The basic idea is that each
subquery of a query string corresponds to a set of matching
spans/intervals/extents, and operators (whether "boolean" or
"proximity") are a means of filter and combining
spans/intervals/extents. For example:
* Query [ medical ] would correspond to every span where the term
"medical" appears
* Query [ medical and companion ] would correspond to all the
minimum-match spans containing both "medical" and "companion"
* Query [ agreement w/5 (medical and companion) ] would correspond to
all the minimum-match spans where "agreement" was within 5 words of a
minimum-match span for [medical and companion]
I like how minimum interval semantics gives a precise meaning to not
just a query but every subcomponent thereof. There is a very clear
story for why every document did/didn't match.
Unfortunately, I doubt that minimum interval semantics corresponds
especially well to my users' expectations. For example, in the above
interpretation of [agreement w/5 (medical and companion)], that query
would match the hypothetical span
medical ... [insert 50,000 words here, none of which is
"companion"] ... companion to the agreement
whereas I'm pretty sure my users are hoping to find instances where
"medical" and "companion" are much closer together.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: Approches/semantics for arbitrarily combining boolean and
proximity search operators?
Posted by Trejkaz <tr...@trypticon.org>.
On Sat, May 26, 2012 at 12:07 PM, Chris Harris <ry...@gmail.com> wrote:
>
> Alternatively, if you insist that query
>
> merger w/5 (medical and agreement)
>
> should match document "medical x x x merger x x x agreement"
>
> then you can propagate 2x the parent's slop value down to child queries.
This is in fact exactly how we are approximating them. The selling
point was this one:
> * You get a nice 1-to-1 mapping from one subquery to one SpanQuery;
> the output query trees look recognizably parallel to the input
> queries, regardless of query complexity.
The problem with the other "more accurate" transformations at the time
were the explosion of query complexity once users started to combine
them.
Of course, a native SpanAndQuery would allow for a more elegant and
precise 1-to-1 mapping. :) I even tried to modify one of the
existing span queries to get similar behaviour, but it wasn't easy
enough to get it right.
TX
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: Approches/semantics for arbitrarily combining boolean and
proximity search operators?
Posted by Chris Harris <ry...@gmail.com>.
In case it's of interest, I have a new approach I'm considering.
For the basic intuition, a colleague who works with some of the users
formulating these complicated queries proposed that
(merger and agreement) w/5 (medical and companion)
is approximately the same as
(merger w/5 agreement) w/5 (medical w/5 companion)
That is
* and-inside-proximity can become SpanNears (agreeing with minimal
interval semantics)
* you can propagate the slop value (5) down from parent queries to
child queries (a new idea)
Alternatively, if you insist that query
merger w/5 (medical and agreement)
should match document "medical x x x merger x x x agreement"
then you can propagate 2x the parent's slop value down to child queries.
At first I thought this couldn't possibly work, but it's growing on me.
The advantages:
* It results seem to feel right-ish in a lot of cases. (I say
"right-ish" in order to grant that there are individual specialized
cases [e.g. a w/5 (b and c)] where something else seems more right.
Nonetheless a lot of those specialized rules seem hard to generalize
into something universally great.)
* Like the qsol and interval semantics approaches (it's a variant of
the latter, I guess), it can assign a meaning to all
boolean-inside-proximity queries, rather than just a subset
* You get a nice 1-to-1 mapping from one subquery to one SpanQuery;
the output query trees look recognizably parallel to the input
queries, regardless of query complexity.
To be a little more precise, I have a hypothetical function "expand"
that carries out the translation recursively:
expand(x1 w/n x2, n) -> SpanNear(n, expand(x1, n), expand(x2, n))
expand(x1 or x2, n) -> SpanOr(n, expand(x1, n), expand(x2, n))
expand(x1 and x2, n) -> SpanNear(n, expand(x1, n), expand(x2, n))
expand(x1 not x2, n) -> expand(x1, n) not/n expand(x2, n)
expand(term, n) -> SpanTermQuery
n is the proximity value passed in from the parent clause. (For
clarify of exposition, I've removed the rules that deal with
non-proximity portions of the query, and considered only binary
versions of and/or.)
a not/n b means "a, not within n words of b". I don't think it can be
implemented directly using existing SpanQueries, but I think it's
probably easy to extend SpanQuery to do the job.
On Wed, May 16, 2012 at 2:11 PM, Chris Harris <ry...@gmail.com> wrote:
> I'm working on a product for librarians and similar people, who
> apparently expect to be able to combine classic boolean operators
> (i.e. AND, OR, NOT) with proximity operators (especially w/n and pre/n
> -- which basically map to unordered and ordered SpanQueries with slop
> n, respectively) in unrestricted fashion. For example, users appear to
> believe that not only are relatively easy-to-grasp queries like these
> legitimate:
>
> medical w/5 agreement
> (medical w/5 agreement) and (doctor w/10 rights)
>
> but also crazier ones, perhaps like
>
> agreement w/5 (medical and companion)
> (dog or dragon) w/5 (cat and cow)
> (daisy and (dog or dragon)) w/25 (cat not cow)
>
> What I've noticed is that it's not always obvious how to interpret
> such queries; it's not always obvious what the user had in mind, nor
> how you might construct a Lucene query to carry out the user's intent.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: Approches/semantics for arbitrarily combining boolean and proximity search operators?
Posted by Alan Woodward <al...@romseysoftware.co.uk>.
You're right, those cases won't be covered, and probably can't be without some hacking at the NearSpans* classes. The other niggle I've found is that it doesn't play well with highlighting - you get the entire span highlighted, rather than the individual terms within it.
For NOT WITHIN queries, I use the following:
X NOT WITHIN/5 Y -> SpanNotQuery(X, SpanNear(X, Y, 5))
which finds all instances of X, and then removes any that are also within 5 of Y.
On 17 May 2012, at 20:02, Chris Harris wrote:
> First impression is, that's a reasonably clever way to get the user
> intent basically right without having to add a new SpanQuery. Have you
> come up with any edge cases where it could do something unexpected?
>
> So far I've thought of one, though you could argue it has more to do
> with the "minimum/lazy/nonoverlapping match" nature of SpanQuery than
> with your particular implementation of "and": Suppose there's a
> document whose complete text is
>
> B A x A x x x x C
>
> From my hypothetical user's perspective, this should match the query
> [A w/5 (B and C)], because the second "A" is within slop 5 of both B
> and C. However, because SpanNear only does minimum-ish matches, this
> document *won't* match the rewritten query SpanNear(A, spanNear(A, B,
> 5), spanNear(A, C, 5), 0); the only span generated for the SpanNear(A,
> B, 5) subquery will be "B A", and the only span for SpanNear(A, C, 5)
> will be "A x x x x C", and those two are not adjacent, so there's no
> match for the outer SpanNear.
>
> Also, while we're exploring your solution, do you also have a rule to
> cover "not"?
>
> On Thu, May 17, 2012 at 12:58 AM, Alan Woodward
> <al...@romseysoftware.co.uk> wrote:
>> I've just had to implement exactly this - the solution I came up with was to translate:
>>
>> A w/5 (B and C) -> SpanNear(A, spanNear(A, B, 5), spanNear(A, C, 5), 0)
>> A w/5 (B or C) -> OR(spanNear(A, B, 5), spanNear(A, C, 5))
>>
>> More complex queries (such as (A AND B) w/5 (C AND D)) are dealt with by applying the above rules recursively. You do end up with some horribly overcomplicated queries, but it seems to be performant enough.
>>
>>
>>
>> On 17 May 2012, at 04:38, Mike Sokolov wrote:
>>
>>> It sounds me as if there could be a market for a new kind of query that would implement:
>>>
>>> A w/5 (B and C)
>>>
>>> in the way that people understand it to mean - the same A near both B and C, not just any A.
>>>
>>> Maybe it's too hard to implement using rewrites into existing SpanQueries?
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: Approches/semantics for arbitrarily combining boolean and
proximity search operators?
Posted by Chris Harris <ry...@gmail.com>.
First impression is, that's a reasonably clever way to get the user
intent basically right without having to add a new SpanQuery. Have you
come up with any edge cases where it could do something unexpected?
So far I've thought of one, though you could argue it has more to do
with the "minimum/lazy/nonoverlapping match" nature of SpanQuery than
with your particular implementation of "and": Suppose there's a
document whose complete text is
B A x A x x x x C
>From my hypothetical user's perspective, this should match the query
[A w/5 (B and C)], because the second "A" is within slop 5 of both B
and C. However, because SpanNear only does minimum-ish matches, this
document *won't* match the rewritten query SpanNear(A, spanNear(A, B,
5), spanNear(A, C, 5), 0); the only span generated for the SpanNear(A,
B, 5) subquery will be "B A", and the only span for SpanNear(A, C, 5)
will be "A x x x x C", and those two are not adjacent, so there's no
match for the outer SpanNear.
Also, while we're exploring your solution, do you also have a rule to
cover "not"?
On Thu, May 17, 2012 at 12:58 AM, Alan Woodward
<al...@romseysoftware.co.uk> wrote:
> I've just had to implement exactly this - the solution I came up with was to translate:
>
> A w/5 (B and C) -> SpanNear(A, spanNear(A, B, 5), spanNear(A, C, 5), 0)
> A w/5 (B or C) -> OR(spanNear(A, B, 5), spanNear(A, C, 5))
>
> More complex queries (such as (A AND B) w/5 (C AND D)) are dealt with by applying the above rules recursively. You do end up with some horribly overcomplicated queries, but it seems to be performant enough.
>
>
>
> On 17 May 2012, at 04:38, Mike Sokolov wrote:
>
>> It sounds me as if there could be a market for a new kind of query that would implement:
>>
>> A w/5 (B and C)
>>
>> in the way that people understand it to mean - the same A near both B and C, not just any A.
>>
>> Maybe it's too hard to implement using rewrites into existing SpanQueries?
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: Approches/semantics for arbitrarily combining boolean and proximity search operators?
Posted by Alan Woodward <al...@romseysoftware.co.uk>.
I've just had to implement exactly this - the solution I came up with was to translate:
A w/5 (B and C) -> SpanNear(A, spanNear(A, B, 5), spanNear(A, C, 5), 0)
A w/5 (B or C) -> OR(spanNear(A, B, 5), spanNear(A, C, 5))
More complex queries (such as (A AND B) w/5 (C AND D)) are dealt with by applying the above rules recursively. You do end up with some horribly overcomplicated queries, but it seems to be performant enough.
On 17 May 2012, at 04:38, Mike Sokolov wrote:
> It sounds me as if there could be a market for a new kind of query that would implement:
>
> A w/5 (B and C)
>
> in the way that people understand it to mean - the same A near both B and C, not just any A.
>
> Maybe it's too hard to implement using rewrites into existing SpanQueries?
>
> In term of the PositionIterator work - instead of A being within 5 in a "minimum" distance sense, what we want is that its "maximum" distance to all the terms in the other query (B and C) is 5. I'm not sure if any query in that branch covers this case though, either, but if I recall, there was a way to implement extensions to it that were fairly natural.
>
> -Mike
>
> On 5/16/2012 7:15 PM, Trejkaz wrote:
>> On Thu, May 17, 2012 at 7:11 AM, Chris Harris<ry...@gmail.com> wrote:
>>> but also crazier ones, perhaps like
>>>
>>> agreement w/5 (medical and companion)
>>> (dog or dragon) w/5 (cat and cow)
>>> (daisy and (dog or dragon)) w/25 (cat not cow)
>> [skip]
>>
>> Everything in your post matches our experience. We ended up writing
>> something which transforms the query as well but had to give up on
>> certain crazy things people tried, such as this form:
>>
>> (A and B) w/5 (C and D)
>>
>> For this one:
>>
>> A w/5 (B and C)
>>
>> We found the user expected the same A to be within 5 terms of both a B
>> and a C, and rewrote it to match that but also match more than they
>> asked for. So far, there have been no complaints about the overmatches
>> (it's documented.)
>>
>> There is probably an extremely accurate way to rewrite it, but it
>> couldn't be figured out at the time. Maybe start with spans for A and
>> then remove spans not-near a B and spans not-near a C, which would
>> leave you with only spans near an A. The problem is that if you expand
>> the query to something like this, it gets quite a bit more complex, so
>> a user query which is already complex could turn into a really hard to
>> understand mess...
>>
>> TX
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
>> For additional commands, e-mail: java-user-help@lucene.apache.org
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: Approches/semantics for arbitrarily combining boolean and proximity
search operators?
Posted by Mike Sokolov <so...@ifactory.com>.
It sounds me as if there could be a market for a new kind of query that
would implement:
A w/5 (B and C)
in the way that people understand it to mean - the same A near both B
and C, not just any A.
Maybe it's too hard to implement using rewrites into existing SpanQueries?
In term of the PositionIterator work - instead of A being within 5 in a
"minimum" distance sense, what we want is that its "maximum" distance to
all the terms in the other query (B and C) is 5. I'm not sure if any
query in that branch covers this case though, either, but if I recall,
there was a way to implement extensions to it that were fairly natural.
-Mike
On 5/16/2012 7:15 PM, Trejkaz wrote:
> On Thu, May 17, 2012 at 7:11 AM, Chris Harris<ry...@gmail.com> wrote:
>> but also crazier ones, perhaps like
>>
>> agreement w/5 (medical and companion)
>> (dog or dragon) w/5 (cat and cow)
>> (daisy and (dog or dragon)) w/25 (cat not cow)
> [skip]
>
> Everything in your post matches our experience. We ended up writing
> something which transforms the query as well but had to give up on
> certain crazy things people tried, such as this form:
>
> (A and B) w/5 (C and D)
>
> For this one:
>
> A w/5 (B and C)
>
> We found the user expected the same A to be within 5 terms of both a B
> and a C, and rewrote it to match that but also match more than they
> asked for. So far, there have been no complaints about the overmatches
> (it's documented.)
>
> There is probably an extremely accurate way to rewrite it, but it
> couldn't be figured out at the time. Maybe start with spans for A and
> then remove spans not-near a B and spans not-near a C, which would
> leave you with only spans near an A. The problem is that if you expand
> the query to something like this, it gets quite a bit more complex, so
> a user query which is already complex could turn into a really hard to
> understand mess...
>
> TX
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: Approches/semantics for arbitrarily combining boolean and
proximity search operators?
Posted by Trejkaz <tr...@trypticon.org>.
On Thu, May 17, 2012 at 7:11 AM, Chris Harris <ry...@gmail.com> wrote:
> but also crazier ones, perhaps like
>
> agreement w/5 (medical and companion)
> (dog or dragon) w/5 (cat and cow)
> (daisy and (dog or dragon)) w/25 (cat not cow)
[skip]
Everything in your post matches our experience. We ended up writing
something which transforms the query as well but had to give up on
certain crazy things people tried, such as this form:
(A and B) w/5 (C and D)
For this one:
A w/5 (B and C)
We found the user expected the same A to be within 5 terms of both a B
and a C, and rewrote it to match that but also match more than they
asked for. So far, there have been no complaints about the overmatches
(it's documented.)
There is probably an extremely accurate way to rewrite it, but it
couldn't be figured out at the time. Maybe start with spans for A and
then remove spans not-near a B and spans not-near a C, which would
leave you with only spans near an A. The problem is that if you expand
the query to something like this, it gets quite a bit more complex, so
a user query which is already complex could turn into a really hard to
understand mess...
TX
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
Re: Approches/semantics for arbitrarily combining boolean and proximity search operators?
Posted by Ahmet Arslan <io...@yahoo.com>.
> medical w/5 agreement
> (medical w/5 agreement) and (doctor w/10 rights)
>
> but also crazier ones, perhaps like
>
> agreement w/5 (medical and companion)
> (dog or dragon) w/5 (cat and cow)
> (daisy and (dog or dragon)) w/25 (cat not cow)
This syntax reminds me Surround.
http://wiki.apache.org/solr/SurroundQueryParser
http://www.lucidimagination.com/blog/2009/02/22/exploring-query-parsers/
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org