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 Oliver Christ <oc...@ebscohost.com> on 2013/01/16 22:27:33 UTC
Suggesters: circumfix suggestions
Hi,
Has anyone tried to implement circumfix suggesters, where the suggestion
is a circumfix of the lookup string?
E.g. "sox rumor" suggests "boston red sox rumors" (try it on
google.com).
I think there are several of ways to implement this:
* Given some multiword term, add all word subsequences to the
suggester individually ("boston red sox rumors" adds also "red sox
rumors", "sox rumors", "rumors") - that can be achieved using a special
TermFreqIterator. This turns the lookup problem into a standard prefix
search. While this works, it effectively modifies the surface form, and
the "full term" needs to be indexed and looked up elsewhere.
* Constructing a token graph with appropriate substring arcs
from the (hopefully linear) token sequence, using a special TokenFilter.
The benefit is that the surface form is always the same, but the
automaton may become large (at least if you are using an
AnalyzingSuggester).
* DIY, using suffix arrays or something similar.
But I'm sure there are other ways and/or tradeoffs I haven't thought
about J I'd be interested in your feedback.
Cheers, Oli
Re: Suggesters: circumfix suggestions
Posted by Dawid Weiss <da...@gmail.com>.
> Eg, you'd index only "boston", "red", "sox", "rumor" into the FST, and
> then have a separate search index with "boston red sox rumor" indexed
> as a document. If the user types "red so", then you run suggest on
> "red" and on "so", and then run a hmm MultiPhraseQuery for
> (red|redmond|reddit) (so|sox|sophomore|...) against the index? How to
I know of at least one company (ehm, can't tell by name) that does
this for matching physical locations against user queries (n yo => new
york, etc.). Granted, this is a very closed domain and the boosts can
be pretty well approximated (cities by the number of citizens, streets
by the location they're at etc.).
Good idea to try out though. Another possible alternative would be to
run a frequent phrase extraction algorithm of some sort, then collect
only the best candidate phrases. I bet a lot of these these could be
fit into an FST, perhaps even indexed at every starting token's
position so that infix searches could work. If you need absolutely all
suggestions you'll need to come up with something more clever.
Dawid
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
RE: Suggesters: circumfix suggestions
Posted by Oliver Christ <oc...@ebscohost.com>.
In our case (very similar to the "Netflix movie titles" use case) the
AnalyzingSuggester's FST grows by a factor of ~5 when we generate the
token graph.
Looking up and joining individual "postings lists" for the individual
tokens would certainly work, but is certainly more work than injecting a
token graph generator into the index analyzer's token filter chain :)
(or modifying TokenStreamToAutomaton to generate the additional
transitions, but that may be too low-level).
Cheers, Oli
-----Original Message-----
From: Michael McCandless [mailto:lucene@mikemccandless.com]
Sent: Wednesday, January 16, 2013 5:38 PM
To: java-user@lucene.apache.org
Subject: Re: Suggesters: circumfix suggestions
Netflix also does this, eg type transla (you need an account).
I think it'd be good to somehow support this (Lucene's suggesters don't
today).
The first two approaches should conceptually work, but both will bloat
the FST (I'd be curious to know how much!).
Maybe another approach would be ... to index only single tokens into the
suggester? And then, from the user's query, run the suggester on each
token separately, and then do a second search (against a "normal"
Lucene index) to find all documents containing those tokens?
Eg, you'd index only "boston", "red", "sox", "rumor" into the FST, and
then have a separate search index with "boston red sox rumor" indexed as
a document. If the user types "red so", then you run suggest on "red"
and on "so", and then run a hmm MultiPhraseQuery for
(red|redmond|reddit) (so|sox|sophomore|...) against the index? How to
score/sort the resulting hits will be interesting ... if you have strong
priors / boost (e.g. you have a good source of "popularity" or
something) then you could sort by that ...
Mike McCandless
http://blog.mikemccandless.com
On Wed, Jan 16, 2013 at 4:27 PM, Oliver Christ <oc...@ebscohost.com>
wrote:
> Hi,
>
>
>
> Has anyone tried to implement circumfix suggesters, where the
> suggestion is a circumfix of the lookup string?
>
>
>
> E.g. "sox rumor" suggests "boston red sox rumors" (try it on
> google.com).
>
>
>
> I think there are several of ways to implement this:
>
>
>
> * Given some multiword term, add all word subsequences to the
> suggester individually ("boston red sox rumors" adds also "red sox
> rumors", "sox rumors", "rumors") - that can be achieved using a
> special TermFreqIterator. This turns the lookup problem into a
> standard prefix search. While this works, it effectively modifies the
> surface form, and the "full term" needs to be indexed and looked up
elsewhere.
>
> * Constructing a token graph with appropriate substring arcs
> from the (hopefully linear) token sequence, using a special
TokenFilter.
> The benefit is that the surface form is always the same, but the
> automaton may become large (at least if you are using an
> AnalyzingSuggester).
>
> * DIY, using suffix arrays or something similar.
>
>
>
> But I'm sure there are other ways and/or tradeoffs I haven't thought
> about J I'd be interested in your feedback.
>
>
>
> Cheers, Oli
>
>
>
---------------------------------------------------------------------
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: Suggesters: circumfix suggestions
Posted by Michael McCandless <lu...@mikemccandless.com>.
Netflix also does this, eg type transla (you need an account).
I think it'd be good to somehow support this (Lucene's suggesters don't today).
The first two approaches should conceptually work, but both will bloat
the FST (I'd be curious to know how much!).
Maybe another approach would be ... to index only single tokens into
the suggester? And then, from the user's query, run the suggester on
each token separately, and then do a second search (against a "normal"
Lucene index) to find all documents containing those tokens?
Eg, you'd index only "boston", "red", "sox", "rumor" into the FST, and
then have a separate search index with "boston red sox rumor" indexed
as a document. If the user types "red so", then you run suggest on
"red" and on "so", and then run a hmm MultiPhraseQuery for
(red|redmond|reddit) (so|sox|sophomore|...) against the index? How to
score/sort the resulting hits will be interesting ... if you have
strong priors / boost (e.g. you have a good source of "popularity" or
something) then you could sort by that ...
Mike McCandless
http://blog.mikemccandless.com
On Wed, Jan 16, 2013 at 4:27 PM, Oliver Christ <oc...@ebscohost.com> wrote:
> Hi,
>
>
>
> Has anyone tried to implement circumfix suggesters, where the suggestion
> is a circumfix of the lookup string?
>
>
>
> E.g. "sox rumor" suggests "boston red sox rumors" (try it on
> google.com).
>
>
>
> I think there are several of ways to implement this:
>
>
>
> * Given some multiword term, add all word subsequences to the
> suggester individually ("boston red sox rumors" adds also "red sox
> rumors", "sox rumors", "rumors") - that can be achieved using a special
> TermFreqIterator. This turns the lookup problem into a standard prefix
> search. While this works, it effectively modifies the surface form, and
> the "full term" needs to be indexed and looked up elsewhere.
>
> * Constructing a token graph with appropriate substring arcs
> from the (hopefully linear) token sequence, using a special TokenFilter.
> The benefit is that the surface form is always the same, but the
> automaton may become large (at least if you are using an
> AnalyzingSuggester).
>
> * DIY, using suffix arrays or something similar.
>
>
>
> But I'm sure there are other ways and/or tradeoffs I haven't thought
> about J I'd be interested in your feedback.
>
>
>
> Cheers, Oli
>
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org