You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by Grant Ingersoll <gs...@apache.org> on 2008/05/15 14:47:46 UTC
NGrams and positions
See https://issues.apache.org/jira/browse/LUCENE-1224
Do people have an opinion on what positions ngrams should be output
at? For instance, given 1-grams on "abc fgh", these are currently
output as: a, b, c, f, g,h all with a position increment of 1. That
seems somewhat reasonable, but it has tradeoffs, namely you can't
query for something like: "a f" without some amount of slop, which I
think is a reasonable thing to do (but don't have an actual use case
for at the moment.) An alternative way might be to output a, b, c all
at the same position, then increment for f and then put g and h at the
same position.
I am _wondering_ whether it makes more sense to add an option to the
NGram token streams such that we could have the choice of either
outputting the n-grams within a "token" at the same position or at
successive positions (to be back-compatible.) It isn't clear to me
which is correct, or if there is even a notion of correctness here, in
so much as they are both correct if that is the functionality you want
in your application. As DM Smith noted, if Lucene supported the
notion of "sub" positions, one could output 1.a, 1.b, 1.c, 2.a, 2.b
and 2.c for the example above, but that capability doesn't exist in
Lucene right now, AFAIK.
-Grant
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: NGrams and positions
Posted by Hiroaki Kawai <ka...@iij.ad.jp>.
I think LUCENE-1224 is more complex than LUCENE-1225.
First, I want to solve LUCENE-1225. It might be more
simple to understand.
For LUCENE-1224, I came to the same issue. My current
understanding is this comes from mismatch of TokenFilter and position.
I apologyze for that the patch is confusing. I'm aware that the patch
still has another issue.
When we process a stream to tokenize by two TokenFilters,
the first will tokenize "abc fgh" to 'abc', 'fgh'.
then we tokenize 'ab' 'bc' 'fg' 'gh'.
The question is what about the "positioin"?
The first tokenFilter will create an alignment, and the second
tokenFilter will create a subalignment.
'abc', 'fgh' => position 0, 1
'ab' 'bc' 'fg' 'gh' => position 0-0, 0-1, 1-0, 1-1
Current lucene can't handle the subalignment, and I think supporting
subalignment is an overkill.
By the way, I want to alter the patch of LUCENE-1224.
Aligning 'ab' and 'bc' at the same position was bad, sorry!
LUCENE-1225 is good I think.
Grant Ingersoll <gs...@apache.org> wrote:
> See https://issues.apache.org/jira/browse/LUCENE-1224
>
> Do people have an opinion on what positions ngrams should be output
> at? For instance, given 1-grams on "abc fgh", these are currently
> output as: a, b, c, f, g,h all with a position increment of 1. That
> seems somewhat reasonable, but it has tradeoffs, namely you can't
> query for something like: "a f" without some amount of slop, which I
> think is a reasonable thing to do (but don't have an actual use case
> for at the moment.) An alternative way might be to output a, b, c all
> at the same position, then increment for f and then put g and h at the
> same position.
>
> I am _wondering_ whether it makes more sense to add an option to the
> NGram token streams such that we could have the choice of either
> outputting the n-grams within a "token" at the same position or at
> successive positions (to be back-compatible.) It isn't clear to me
> which is correct, or if there is even a notion of correctness here, in
> so much as they are both correct if that is the functionality you want
> in your application. As DM Smith noted, if Lucene supported the
> notion of "sub" positions, one could output 1.a, 1.b, 1.c, 2.a, 2.b
> and 2.c for the example above, but that capability doesn't exist in
> Lucene right now, AFAIK.
>
> -Grant
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: NGrams and positions
Posted by Hiroaki Kawai <ka...@apache.org>.
I think it is not the matter what ngram in genral.
NGramTokenFilter is a TokenFilter, and this produce a
TRICKY token stream because it is processed more than
one tokenizer.
This discussion is about the mechanism of tokenFilter
itself.
The NGramTokenFilter creates a so tricky token
stream in the current implementation that one might be
consider that is a new version of n-gram.
The token stream genrerated by NGramTokenFilter is
processed not only by n-gram tokenizer but also a
mixture of the other tokenizers, so the token stream
might not look like a normal n-gram.
I think Grant is talking about StandardTokenizer + NGramTokenFilter,
isn't?
Grant Ingersoll <gs...@apache.org> wrote:
> On May 16, 2008, at 11:13 AM, Hiroaki Kawai wrote:
>
> > I think LUCENE-1224 is more complex than LUCENE-1225.
> >
> > First, I want to solve LUCENE-1225. It might be more
> > simple to understand.
> >
> > For LUCENE-1224, I came to the same issue. My current
> > understanding is this comes from mismatch of TokenFilter and position.
> > I apologyze for that the patch is confusing. I'm aware that the patch
> > still has another issue.
>
> The patch itself isn't confusing, IMO (the only issue with the patch
> is the unit test, but that is for the JIRA discussion). I think it
> does what it says it does. This discussion is more philosophical as
> to what kinds of things people want to do with ngrams in general.
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: NGrams and positions
Posted by Grant Ingersoll <gs...@apache.org>.
On May 16, 2008, at 11:13 AM, Hiroaki Kawai wrote:
> I think LUCENE-1224 is more complex than LUCENE-1225.
>
> First, I want to solve LUCENE-1225. It might be more
> simple to understand.
>
> For LUCENE-1224, I came to the same issue. My current
> understanding is this comes from mismatch of TokenFilter and position.
> I apologyze for that the patch is confusing. I'm aware that the patch
> still has another issue.
The patch itself isn't confusing, IMO (the only issue with the patch
is the unit test, but that is for the JIRA discussion). I think it
does what it says it does. This discussion is more philosophical as
to what kinds of things people want to do with ngrams in general.
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: NGrams and positions
Posted by Hiroaki Kawai <ka...@apache.org>.
I think LUCENE-1224 is more complex than LUCENE-1225.
First, I want to solve LUCENE-1225. It might be more
simple to understand.
For LUCENE-1224, I came to the same issue. My current
understanding is this comes from mismatch of TokenFilter and position.
I apologyze for that the patch is confusing. I'm aware that the patch
still has another issue.
When we process a stream to tokenize by two TokenFilters,
the first will tokenize "abc fgh" to 'abc', 'fgh'.
then we tokenize 'ab' 'bc' 'fg' 'gh'.
The question is what about the "positioin"?
The first tokenFilter will create an alignment, and the second
tokenFilter will create a subalignment.
'abc', 'fgh' => position 0, 1
'ab' 'bc' 'fg' 'gh' => position 0-0, 0-1, 1-0, 1-1
Current lucene can't handle the subalignment, and I think supporting
subalignment is an overkill.
By the way, I want to alter the patch of LUCENE-1224.
Aligning 'ab' and 'bc' at the same position was bad, sorry!
LUCENE-1225 is good I think.
Grant Ingersoll <gs...@apache.org> wrote:
> See https://issues.apache.org/jira/browse/LUCENE-1224
>
> Do people have an opinion on what positions ngrams should be output
> at? For instance, given 1-grams on "abc fgh", these are currently
> output as: a, b, c, f, g,h all with a position increment of 1. That
> seems somewhat reasonable, but it has tradeoffs, namely you can't
> query for something like: "a f" without some amount of slop, which I
> think is a reasonable thing to do (but don't have an actual use case
> for at the moment.) An alternative way might be to output a, b, c all
> at the same position, then increment for f and then put g and h at the
> same position.
>
> I am _wondering_ whether it makes more sense to add an option to the
> NGram token streams such that we could have the choice of either
> outputting the n-grams within a "token" at the same position or at
> successive positions (to be back-compatible.) It isn't clear to me
> which is correct, or if there is even a notion of correctness here, in
> so much as they are both correct if that is the functionality you want
> in your application. As DM Smith noted, if Lucene supported the
> notion of "sub" positions, one could output 1.a, 1.b, 1.c, 2.a, 2.b
> and 2.c for the example above, but that capability doesn't exist in
> Lucene right now, AFAIK.
>
> -Grant
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: NGrams and positions
Posted by Grant Ingersoll <gs...@apache.org>.
Note, also, I am proposing to have the option, I agree this is a
valid, good case. One could use payloads and some new fangled query
to do the sub position thing, just for completeness here.
-Grant
On May 15, 2008, at 12:54 PM, Doug Cutting wrote:
> The conventional use of ngrams when searching is not to treat them
> as a set but a sequence. Thus, for "foola" you could index the
> sequence ["_f", "fo", "oo", "ol", "la", "a_"], and then search for
> the phrase ["oo", "ol"] to find all occurences of "ool". This is
> useful in languages that use logograms without spaces, like Japanese
> and Chinese, and in other cases (e.g., Nutch uses word-ngrams to
> optimize searches for phrases containing very common terms).
>
> Do you have a use-case for the alternative, where n-grams are
> treated as a set, rather than a sequence?
>
> Doug
>
> Grant Ingersoll wrote:
>> See https://issues.apache.org/jira/browse/LUCENE-1224
>> Do people have an opinion on what positions ngrams should be output
>> at? For instance, given 1-grams on "abc fgh", these are currently
>> output as: a, b, c, f, g,h all with a position increment of 1.
>> That seems somewhat reasonable, but it has tradeoffs, namely you
>> can't query for something like: "a f" without some amount of slop,
>> which I think is a reasonable thing to do (but don't have an actual
>> use case for at the moment.) An alternative way might be to output
>> a, b, c all at the same position, then increment for f and then put
>> g and h at the same position.
>> I am _wondering_ whether it makes more sense to add an option to
>> the NGram token streams such that we could have the choice of
>> either outputting the n-grams within a "token" at the same position
>> or at successive positions (to be back-compatible.) It isn't clear
>> to me which is correct, or if there is even a notion of correctness
>> here, in so much as they are both correct if that is the
>> functionality you want in your application. As DM Smith noted, if
>> Lucene supported the notion of "sub" positions, one could output
>> 1.a, 1.b, 1.c, 2.a, 2.b and 2.c for the example above, but that
>> capability doesn't exist in Lucene right now, AFAIK.
>> -Grant
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
>> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: NGrams and positions
Posted by Grant Ingersoll <gs...@apache.org>.
I think there is also the use case of using ngrams as a substitute for
wildcard queries, and you could use then imagine doing a phrase query
across those tokens. So, if you had the words "quick red fox" and you
output 1-grams (as an example), you could do a query like "q r f" in
place of "q* r* f*".
On May 15, 2008, at 12:54 PM, Doug Cutting wrote:
> The conventional use of ngrams when searching is not to treat them
> as a set but a sequence. Thus, for "foola" you could index the
> sequence ["_f", "fo", "oo", "ol", "la", "a_"], and then search for
> the phrase ["oo", "ol"] to find all occurences of "ool". This is
> useful in languages that use logograms without spaces, like Japanese
> and Chinese, and in other cases (e.g., Nutch uses word-ngrams to
> optimize searches for phrases containing very common terms).
>
> Do you have a use-case for the alternative, where n-grams are
> treated as a set, rather than a sequence?
>
> Doug
>
> Grant Ingersoll wrote:
>> See https://issues.apache.org/jira/browse/LUCENE-1224
>> Do people have an opinion on what positions ngrams should be output
>> at? For instance, given 1-grams on "abc fgh", these are currently
>> output as: a, b, c, f, g,h all with a position increment of 1.
>> That seems somewhat reasonable, but it has tradeoffs, namely you
>> can't query for something like: "a f" without some amount of slop,
>> which I think is a reasonable thing to do (but don't have an actual
>> use case for at the moment.) An alternative way might be to output
>> a, b, c all at the same position, then increment for f and then put
>> g and h at the same position.
>> I am _wondering_ whether it makes more sense to add an option to
>> the NGram token streams such that we could have the choice of
>> either outputting the n-grams within a "token" at the same position
>> or at successive positions (to be back-compatible.) It isn't clear
>> to me which is correct, or if there is even a notion of correctness
>> here, in so much as they are both correct if that is the
>> functionality you want in your application. As DM Smith noted, if
>> Lucene supported the notion of "sub" positions, one could output
>> 1.a, 1.b, 1.c, 2.a, 2.b and 2.c for the example above, but that
>> capability doesn't exist in Lucene right now, AFAIK.
>> -Grant
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
>> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: NGrams and positions
Posted by Doug Cutting <cu...@apache.org>.
The conventional use of ngrams when searching is not to treat them as a
set but a sequence. Thus, for "foola" you could index the sequence
["_f", "fo", "oo", "ol", "la", "a_"], and then search for the phrase
["oo", "ol"] to find all occurences of "ool". This is useful in
languages that use logograms without spaces, like Japanese and Chinese,
and in other cases (e.g., Nutch uses word-ngrams to optimize searches
for phrases containing very common terms).
Do you have a use-case for the alternative, where n-grams are treated as
a set, rather than a sequence?
Doug
Grant Ingersoll wrote:
> See https://issues.apache.org/jira/browse/LUCENE-1224
>
> Do people have an opinion on what positions ngrams should be output at?
> For instance, given 1-grams on "abc fgh", these are currently output as:
> a, b, c, f, g,h all with a position increment of 1. That seems somewhat
> reasonable, but it has tradeoffs, namely you can't query for something
> like: "a f" without some amount of slop, which I think is a reasonable
> thing to do (but don't have an actual use case for at the moment.) An
> alternative way might be to output a, b, c all at the same position,
> then increment for f and then put g and h at the same position.
>
> I am _wondering_ whether it makes more sense to add an option to the
> NGram token streams such that we could have the choice of either
> outputting the n-grams within a "token" at the same position or at
> successive positions (to be back-compatible.) It isn't clear to me
> which is correct, or if there is even a notion of correctness here, in
> so much as they are both correct if that is the functionality you want
> in your application. As DM Smith noted, if Lucene supported the notion
> of "sub" positions, one could output 1.a, 1.b, 1.c, 2.a, 2.b and 2.c for
> the example above, but that capability doesn't exist in Lucene right
> now, AFAIK.
>
> -Grant
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org