You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Michael McCandless (JIRA)" <ji...@apache.org> on 2011/07/09 15:03:16 UTC
[jira] [Created] (LUCENE-3297) FST doesn't fully share common
prefix across all outputs
FST doesn't fully share common prefix across all outputs
--------------------------------------------------------
Key: LUCENE-3297
URL: https://issues.apache.org/jira/browse/LUCENE-3297
Project: Lucene - Java
Issue Type: Improvement
Reporter: Michael McCandless
Priority: Minor
FST will try to share prefixes of outputs when possible, however in the [I think unusual in practice] case where all outputs share a common prefix, FST really ought to store this just once, on the root arc, but instead it's only able to push back to the N root arcs. It's sort of an off-by-one on how far back the pushing goes...
One [synthetic] example where this makes a big difference is the new Test2BPostings test, when it uses MemoryCodec, because this test has 26 terms (letters of alphabet) and each term has exactly the same long (~85 MB) all 1s byte[] as the postings. If we fixed this issue, then the resulting FST would only be ~85 MB but now instead it needs to be ~85 * 26 MB.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-3297) FST doesn't fully share common
prefix across all outputs
Posted by "Dawid Weiss (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3297?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13081571#comment-13081571 ]
Dawid Weiss commented on LUCENE-3297:
-------------------------------------
I guess I just don't like marker values from the domain range (like END_LABEL)... they make me nervous. I'll experiment.
> FST doesn't fully share common prefix across all outputs
> --------------------------------------------------------
>
> Key: LUCENE-3297
> URL: https://issues.apache.org/jira/browse/LUCENE-3297
> Project: Lucene - Java
> Issue Type: Improvement
> Components: core/FSTs
> Reporter: Michael McCandless
> Priority: Minor
>
> FST will try to share prefixes of outputs when possible, however in the [I think unusual in practice] case where all outputs share a common prefix, FST really ought to store this just once, on the root arc, but instead it's only able to push back to the N root arcs. It's sort of an off-by-one on how far back the pushing goes...
> One [synthetic] example where this makes a big difference is the new Test2BPostings test, when it uses MemoryCodec, because this test has 26 terms (letters of alphabet) and each term has exactly the same long (~85 MB) all 1s byte[] as the postings. If we fixed this issue, then the resulting FST would only be ~85 MB but now instead it needs to be ~85 * 26 MB.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Updated] (LUCENE-3297) FST doesn't fully share common
prefix across all outputs
Posted by "Michael McCandless (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3297?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Michael McCandless updated LUCENE-3297:
---------------------------------------
Component/s: core/FSTs
> FST doesn't fully share common prefix across all outputs
> --------------------------------------------------------
>
> Key: LUCENE-3297
> URL: https://issues.apache.org/jira/browse/LUCENE-3297
> Project: Lucene - Java
> Issue Type: Improvement
> Components: core/FSTs
> Reporter: Michael McCandless
> Priority: Minor
>
> FST will try to share prefixes of outputs when possible, however in the [I think unusual in practice] case where all outputs share a common prefix, FST really ought to store this just once, on the root arc, but instead it's only able to push back to the N root arcs. It's sort of an off-by-one on how far back the pushing goes...
> One [synthetic] example where this makes a big difference is the new Test2BPostings test, when it uses MemoryCodec, because this test has 26 terms (letters of alphabet) and each term has exactly the same long (~85 MB) all 1s byte[] as the postings. If we fixed this issue, then the resulting FST would only be ~85 MB but now instead it needs to be ~85 * 26 MB.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-3297) FST doesn't fully share common
prefix across all outputs
Posted by "Michael McCandless (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3297?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13062369#comment-13062369 ]
Michael McCandless commented on LUCENE-3297:
--------------------------------------------
I don't plan to work on this any time soon... I think it's low priority.
> FST doesn't fully share common prefix across all outputs
> --------------------------------------------------------
>
> Key: LUCENE-3297
> URL: https://issues.apache.org/jira/browse/LUCENE-3297
> Project: Lucene - Java
> Issue Type: Improvement
> Reporter: Michael McCandless
> Priority: Minor
>
> FST will try to share prefixes of outputs when possible, however in the [I think unusual in practice] case where all outputs share a common prefix, FST really ought to store this just once, on the root arc, but instead it's only able to push back to the N root arcs. It's sort of an off-by-one on how far back the pushing goes...
> One [synthetic] example where this makes a big difference is the new Test2BPostings test, when it uses MemoryCodec, because this test has 26 terms (letters of alphabet) and each term has exactly the same long (~85 MB) all 1s byte[] as the postings. If we fixed this issue, then the resulting FST would only be ~85 MB but now instead it needs to be ~85 * 26 MB.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-3297) FST doesn't fully share common
prefix across all outputs
Posted by "Dawid Weiss (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3297?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080611#comment-13080611 ]
Dawid Weiss commented on LUCENE-3297:
-------------------------------------
Ok, I've found the issue I was looking for. Mike, this should be solved by changing the logical organization of the fst. This would also solve the issue of storing an "empty" automaton and its output (which is currently hardcoded in an unpleasant way). The solution is to introduce an epsilon-labeled arc (epsilon meaning an out-of-alphabet symbol, possibly a flag). The "root" of the fst would be an eps-labeled transition to the actual root node. Then, an empty automaton is basically an eps-terminal transition and prefix sharing you talk about in this issue is whatever can be pushed onto this eps-arc. The automaton remains deterministic, it's just a small change of logic (and addition of the special eps symbol).
> FST doesn't fully share common prefix across all outputs
> --------------------------------------------------------
>
> Key: LUCENE-3297
> URL: https://issues.apache.org/jira/browse/LUCENE-3297
> Project: Lucene - Java
> Issue Type: Improvement
> Components: core/FSTs
> Reporter: Michael McCandless
> Priority: Minor
>
> FST will try to share prefixes of outputs when possible, however in the [I think unusual in practice] case where all outputs share a common prefix, FST really ought to store this just once, on the root arc, but instead it's only able to push back to the N root arcs. It's sort of an off-by-one on how far back the pushing goes...
> One [synthetic] example where this makes a big difference is the new Test2BPostings test, when it uses MemoryCodec, because this test has 26 terms (letters of alphabet) and each term has exactly the same long (~85 MB) all 1s byte[] as the postings. If we fixed this issue, then the resulting FST would only be ~85 MB but now instead it needs to be ~85 * 26 MB.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-3297) FST doesn't fully share common
prefix across all outputs
Posted by "Dawid Weiss (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3297?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080884#comment-13080884 ]
Dawid Weiss commented on LUCENE-3297:
-------------------------------------
Yeah, I know it can be coded by adding new conditions in the implementation. My point was that the code can be more generic and cleaner by introducing the modifications above. I may introduce them in my fst reimplementation and see what comes out.
> FST doesn't fully share common prefix across all outputs
> --------------------------------------------------------
>
> Key: LUCENE-3297
> URL: https://issues.apache.org/jira/browse/LUCENE-3297
> Project: Lucene - Java
> Issue Type: Improvement
> Components: core/FSTs
> Reporter: Michael McCandless
> Priority: Minor
>
> FST will try to share prefixes of outputs when possible, however in the [I think unusual in practice] case where all outputs share a common prefix, FST really ought to store this just once, on the root arc, but instead it's only able to push back to the N root arcs. It's sort of an off-by-one on how far back the pushing goes...
> One [synthetic] example where this makes a big difference is the new Test2BPostings test, when it uses MemoryCodec, because this test has 26 terms (letters of alphabet) and each term has exactly the same long (~85 MB) all 1s byte[] as the postings. If we fixed this issue, then the resulting FST would only be ~85 MB but now instead it needs to be ~85 * 26 MB.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-3297) FST doesn't fully share common
prefix across all outputs
Posted by "Michael McCandless (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3297?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13080878#comment-13080878 ]
Michael McCandless commented on LUCENE-3297:
--------------------------------------------
We sort of have this today, in the root arc (FST.getFirstArc), but it "avoids" eps by not setting the arc's label at all, ie you're only allowed/expected to use this arc's target state, output/nextFinalOutput. This arc is how the consumer of the FST API "gets started" in accessing the FST.
Adding eps label would make me nervous :) For our FST impl (limited because we only support determinized FSTs) we'd never see an eps transition anywhere else right? Ie, it'd only be for the root arc.
So the FST already today can represent a globally shared output prefix; the challenge in fixing this issue is to fix the Builder impl to be able to push the output all the way back onto this root arc; the phase where we push outputs as far back as possible doesn't push far enough...
> FST doesn't fully share common prefix across all outputs
> --------------------------------------------------------
>
> Key: LUCENE-3297
> URL: https://issues.apache.org/jira/browse/LUCENE-3297
> Project: Lucene - Java
> Issue Type: Improvement
> Components: core/FSTs
> Reporter: Michael McCandless
> Priority: Minor
>
> FST will try to share prefixes of outputs when possible, however in the [I think unusual in practice] case where all outputs share a common prefix, FST really ought to store this just once, on the root arc, but instead it's only able to push back to the N root arcs. It's sort of an off-by-one on how far back the pushing goes...
> One [synthetic] example where this makes a big difference is the new Test2BPostings test, when it uses MemoryCodec, because this test has 26 terms (letters of alphabet) and each term has exactly the same long (~85 MB) all 1s byte[] as the postings. If we fixed this issue, then the resulting FST would only be ~85 MB but now instead it needs to be ~85 * 26 MB.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
[jira] [Commented] (LUCENE-3297) FST doesn't fully share common
prefix across all outputs
Posted by "Michael McCandless (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCENE-3297?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13081557#comment-13081557 ]
Michael McCandless commented on LUCENE-3297:
--------------------------------------------
If indeed we can make the code more generic and not lose (too much)
perf then that would be awesome... I'm just having trouble seeing how
adding explicit <eps> label will be more generic since <eps> would
only (and, always) be used in exactly one special-cased place (the
root arc), I think?
I must be missing something in your proposal...
Or, are you suggesting we actually make a "before start" symbol (hmm,
the mirror image of FST.END_LABEL) and always forcefully/explicitly
insert this in front of every byte[] passed to Builder? This would in
fact fix this issue, since Builder should push a global output prefix
onto that first arc... and then that first arc would become the FST's
root arc.
> FST doesn't fully share common prefix across all outputs
> --------------------------------------------------------
>
> Key: LUCENE-3297
> URL: https://issues.apache.org/jira/browse/LUCENE-3297
> Project: Lucene - Java
> Issue Type: Improvement
> Components: core/FSTs
> Reporter: Michael McCandless
> Priority: Minor
>
> FST will try to share prefixes of outputs when possible, however in the [I think unusual in practice] case where all outputs share a common prefix, FST really ought to store this just once, on the root arc, but instead it's only able to push back to the N root arcs. It's sort of an off-by-one on how far back the pushing goes...
> One [synthetic] example where this makes a big difference is the new Test2BPostings test, when it uses MemoryCodec, because this test has 26 terms (letters of alphabet) and each term has exactly the same long (~85 MB) all 1s byte[] as the postings. If we fixed this issue, then the resulting FST would only be ~85 MB but now instead it needs to be ~85 * 26 MB.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org