[
https://issues.apache.org/jira/browse/LUCENE-3714?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13190539#comment-13190539
]
Dawid Weiss commented on LUCENE-3714:
-------------------------------------
I thought you had a solution that collects top-N, but your patch selects one
(best) matching solution only. I don't know how you planned to go around
selecting top-N, but in my understanding (at that moment) top-N selection is
not going to work via recursive scan because an output at the given level
doesn't tell you much about which arcs to follow.
I can see how this can be solved by picking the arc/direction with the "next
smallest/largest" output among all arcs traversed so far but this will be more
complex and I cannot provide any bounds on how large the queue can be or what
the worst case lookup then is. I do have a feeling a degenerate example can
be devised, but then I also have a feeling these are uncommon in practice.
Sorting arcs by score doesn't help if you use the pq -- you need to add all of
them to the pq and then pick the smallest path. In a way it is like what you
did, but the pq is maintaining fast access to the next-smaller-cost path.
Another feeling is that the PQ can be bound to a maximum size of N? Every arc
leads to at least one leaf so while traversing you'd drop those arcs that
definitely would have fallen out of the first N smallest/largest weights...
Yes, this could work. I'd still try to devise a degenerate example to see what
the cost of maintaining the PQ can be.
> add suggester that uses shortest path/wFST instead of buckets
> -------------------------------------------------------------
>
> Key: LUCENE-3714
> URL: https://issues.apache.org/jira/browse/LUCENE-3714
> Project: Lucene - Java
> Issue Type: New Feature
> Components: modules/spellchecker
> Reporter: Robert Muir
> Attachments: LUCENE-3714.patch, out.png
>
>
> Currently the FST suggester (really an FSA) quantizes weights into buckets
> (e.g. single byte) and puts them in front of the word.
> This makes it fast, but you lose granularity in your suggestions.
> Lately the question was raised, if you build lucene's FST with
> positiveintoutputs, does it behave the same as a tropical semiring wFST?
> In other words, after completing the word, we instead traverse min(output) at
> each node to find the 'shortest path' to the
> best suggestion (with the highest score).
> This means we wouldnt need to quantize weights at all and it might make some
> operations (e.g. adding fuzzy matching etc) a lot easier.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:
https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
