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 Dawid Weiss <da...@cs.put.poznan.pl> on 2006/03/15 18:02:47 UTC

PhraseQuery and edit distance slightly confusing.

Hi there,

I get the concept implemented in PhraseQuery but isn't calling it an 
edit distance a little bit far fetched? Only the marginal elements 
(minimum and maximum distance from their respective query positions) are 
taken into account. Consider this example:

phrase:     a  b  c  d
term pos:   0  1  2  3

document A: a  c  b  d
term pos:   0  1  2  3
pos. diff:  0 -1  1  0

=> slope = (1 - (-1)) = 2

document B: a  c  b  x  d
term pos:   0  1  2  3  4
pos. diff:  0 -1  1  -  1

=> slope = (1 - (-1) = 2

It's how it is currently implemented, isn't it? The scoring difference 
(attached example) is different just because "document" lengths are 
different, phrases themselves are scored identically even though I 
believe B should be penalized. A simple way to do it would be include 
phrase length divided by the matching span length... but I'm guessing 
it's implemented like that for a reason, just didn't know what that
reason might be ;)

Dawid





Re: PhraseQuery and edit distance slightly confusing.

Posted by Dawid Weiss <da...@cs.put.poznan.pl>.
Hi Doug,

> Yes, it should probably be called "edit-distance-like" or something.

It should definitely say so in the JavaDoc because I've seen this 
propagate to people's articles (it was Eric Hatcher's I think, but I'm 
not sure).

> But what then would the criteria for matching at all be?  Right now it 
> is "distance <= slop", but, with this change, shouldn't it also take 
> into account the match length?

To be honest I didn't go that deep in the subject. I just found myself 
perplexed a bit when I saw you calculating the edit distance as a 
difference of two values :) Nothing personal of course, your code in 
there is quite neat but it tosses all all kinds of indices around and I 
actually thought I got it wrong somehow so I asked to be sure.

>  Right now the penalty is like the maximum error, but the sum of errors 
> in the match might be better.

That's the idea I came up too -- aggregating the error over absolute 
values of positional differences (?) would solve the problem; I'd also 
go for incrementing/ decrementing totalError instead of changing method 
signatures. I'm just not sure if it makes sense to change the behavior 
of PhraseQuery just because I had to please my curiosity :). People are 
used to how it works and maybe it should stay this way. If somebody 
really wants a real edit distance then with your hints and understanding 
of how PhraseQuery works it should be quite straightforward to implement.

Thanks for clarifications,
Dawid




---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org


Re: PhraseQuery and edit distance slightly confusing.

Posted by Doug Cutting <cu...@apache.org>.
Dawid Weiss wrote:
> I get the concept implemented in PhraseQuery but isn't calling it an 
> edit distance a little bit far fetched?

Yes, it should probably be called "edit-distance-like" or something.

> Only the marginal elements 
> (minimum and maximum distance from their respective query positions) are 
> taken into account. Consider this example:
> 
> phrase:     a  b  c  d
> term pos:   0  1  2  3
> 
> document A: a  c  b  d
> term pos:   0  1  2  3
> pos. diff:  0 -1  1  0
> 
> => slope = (1 - (-1)) = 2
> 
> document B: a  c  b  x  d
> term pos:   0  1  2  3  4
> pos. diff:  0 -1  1  -  1
> 
> => slope = (1 - (-1) = 2
> 
> It's how it is currently implemented, isn't it?

That's correct.

> The scoring difference 
> (attached example) is different just because "document" lengths are 
> different, phrases themselves are scored identically even though I 
> believe B should be penalized. A simple way to do it would be include 
> phrase length divided by the matching span length...

We could do this by adding more parameters to Similarity.sloppyFreq(). 
For example, the signature could become:

public float sloppyFreq(int distance, int matchLength);

But what then would the criteria for matching at all be?  Right now it 
is "distance <= slop", but, with this change, shouldn't it also take 
into account the match length?

> but I'm guessing 
> it's implemented like that for a reason, just didn't know what that
> reason might be ;)

No particularly good reason.  I was looking for a simple single measure 
that incorporated both out-of-order and insertion.  You argue that, when 
both are present, the penalty should be higher, which makes good sense. 
  Right now the penalty is like the maximum error, but the sum of errors 
in the match might be better.

To implement this, we could sum the absolute values of your "pos. diff" 
values.  That would give an error value of 2 for document A and 3 for 
document B, as you desire.  This would have the benefit of not changing 
the signature of sloppyFreq() and would also still provide a clear 
criteria for matching:  totalError < slop.  The biggest downside is that 
it would not be back-compatible: documents which used to match with 
slop=2 would no longer.  I don't think this is a huge problem, but it 
does warrant providing an option to restore the old behaviour.

There might be a slight performance impact.  I think we could implement 
this by simply decrementing and incrementing the totalError each time 
SloppyPhraseScorer calls nextPosition() or firstPosition().  Does that 
sound right to you?

Cheers,

Doug

---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org