lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Robert Muir (Updated) (JIRA)" <>
Subject [jira] [Updated] (LUCENE-3801) Generify FST shortestPaths() to take a comparator
Date Fri, 02 Mar 2012 12:22:57 GMT


Robert Muir updated LUCENE-3801:

    Attachment: LUCENE-3801.patch

updated patch with tests (which exposes a real problem!).

I created "paired" versions (Pair<Long,Long> where its weight,output) of the two existing
shortestPath tests: the simple one, and the random one. The simple one passes (somehow), but
the random one triggers an assertion in shortestPaths

Basically the issue is that the original impl has an optimization: when you pick some minimum
path (say 5), you know there is sequence of all zeros leading to some final state, otherwise
its not actually the minimum :)

The code takes advantage of this and (fortunately) asserts that it finds this path of all

The problem is if you have a PairOutputs(weight,output), its only NO_OUTPUT if *both* weight
and output are also NO_OUTPUT, but this only holds true for the weight... the output has its
own separately pushed minimums that don't necessarily correspond...

> Generify FST shortestPaths() to take a comparator
> -------------------------------------------------
>                 Key: LUCENE-3801
>                 URL:
>             Project: Lucene - Java
>          Issue Type: Improvement
>          Components: core/FSTs
>    Affects Versions: 3.6, 4.0
>            Reporter: Robert Muir
>            Assignee: Robert Muir
>         Attachments: LUCENE-3801.patch, LUCENE-3801.patch
> Not sure we should do this, it costs 5-10% performance for WFSTSuggester.
> But maybe we can optimize something here, or maybe its just no big deal to us.
> Because in general, this could be pretty powerful, e.g. if you needed to store 
> some custom stuff in the suggester, you could use pairoutputs, or whatever.
> And the possibility we might need shortestPaths for other cool things... at the
> least I just wanted to have the patch up here.
> I haven't tested this on pairoutputs... but i've tested it with e.g. FloatOutputs
> and other things and it works fine.
> I tried to minimize the generics violations, there is only 1 (cannot create generic array).

This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:!default.jspa
For more information on JIRA, see:


To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message