Missing expected results in fuzzy search (no stemming)

[lucaong]

Performing fuzzy search seems to miss some words within the given edit distance. Here is one example (disabling stemming and all other pipeline functions to ensure that we are only observing the behavior of fuzzy search):

const l = lunr(function () {
  this.field('txt')
  this.pipeline.remove(lunr.stemmer)
  this.pipeline.remove(lunr.trimmer)
  this.pipeline.remove(lunr.stopWordFilter)
  this.searchPipeline.remove(lunr.stemmer)
  this.searchPipeline.remove(lunr.trimmer)
  this.searchPipeline.remove(lunr.stopWordFilter)

  ;[
    { id: 1, txt: 'coscienza' },
    { id: 2, txt: 'scienza' },
    { id: 3, txt: 'conoscienza' },
    { id: 4, txt: 'coscienzaxx' },
  ].forEach(line => this.add(line))
})

l.search('coscienza~2')
// => [ { ref: '3', score: ... }, { ref: '1', score: ... } ]

In the example above, I would expect the words scienza and coscienzaxx to also match, as they are at edit distance of 2 from the query term coscienza (two deletions or insertions at the word boundary).

This is also visible if one observes the fuzzy TokenSet expansion for the term coscienza:

lunr.TokenSet.fromFuzzyString("coscienza", 2).toArray()
// => results contains `*scienza` and `coscienza`, but not `scienza` or `coscienza**`
// (in the context of fuzzy search the * token is not linked to itself, so it matches exactly 1 character)

I am not sure if this is a bug or the intended behavior of fuzzy search. In the latter case, maybe it would deserve a mention in the documentation.

Thanks again for the great work!

[olivernn]

Sorry for taking a while to get to this...

Looks like a bug to me, I put together a simplified reproduction on jsfiddle.

It looks like, for some reason, that trailing characters only match if they are the same as the last character in the fuzzy string, weird! This also explains why the test is passing.

I'll dig into this a bit and come up with a fix, thanks for reporting.

[hoelzro]

Looking at q.toArray() from @olivernn's example, I see the following output:

[ '*oo',
  '*foo',
  'oo',
  'ofo',
  'f*o',
  'f*oo',
  'fo',
  'fo*',
  'fo*o',
  'foo' ]

Would I be incorrect in thinking that foo* should be in there as well? The presence of fo*o explains why fooo is in the intersection, but why food is not.

[hoelzro]

I've created a PR at #382 that I believe fixes this issue.

[olivernn]

I've just pushed 2.3.5 which includes the fix from @hoelzro .