[
https://issues.apache.org/jira/browse/LUCENE-4682?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13551934#comment-13551934
]
Michael McCandless commented on LUCENE-4682:
--------------------------------------------
Maybe we should just tighten up the FST thresholds for when we make an array
arc:
{noformat}
/**
* @see #shouldExpand(UnCompiledNode)
*/
final static int FIXED_ARRAY_SHALLOW_DISTANCE = 3; // 0 => only root node.
/**
* @see #shouldExpand(UnCompiledNode)
*/
final static int FIXED_ARRAY_NUM_ARCS_SHALLOW = 5;
/**
* @see #shouldExpand(UnCompiledNode)
*/
final static int FIXED_ARRAY_NUM_ARCS_DEEP = 10;
{noformat}
When I print out the waste, it's generally the smaller nodes that have higher
proportional waste:
{noformat}
[java] waste: 44 numArcs=16 perArc=2.75
[java] waste: 20 numArcs=11 perArc=1.8181819
[java] waste: 13 numArcs=5 perArc=2.6
[java] waste: 20 numArcs=12 perArc=1.6666666
[java] waste: 60 numArcs=20 perArc=3.0
[java] waste: 0 numArcs=5 perArc=0.0
[java] waste: 48 numArcs=15 perArc=3.2
[java] waste: 16 numArcs=5 perArc=3.2
[java] waste: 20 numArcs=6 perArc=3.3333333
[java] waste: 8 numArcs=6 perArc=1.3333334
[java] waste: 24 numArcs=8 perArc=3.0
[java] waste: 32 numArcs=9 perArc=3.5555556
[java] waste: 17 numArcs=7 perArc=2.4285715
[java] waste: 13 numArcs=5 perArc=2.6
[java] waste: 17 numArcs=6 perArc=2.8333333
[java] waste: 28 numArcs=8 perArc=3.5
[java] waste: 20 numArcs=16 perArc=1.25
[java] waste: 44 numArcs=15 perArc=2.9333334
[java] waste: 28 numArcs=13 perArc=2.1538463
[java] waste: 28 numArcs=15 perArc=1.8666667
{noformat}
> Reduce wasted bytes in FST due to array arcs
> --------------------------------------------
>
> Key: LUCENE-4682
> URL: https://issues.apache.org/jira/browse/LUCENE-4682
> Project: Lucene - Core
> Issue Type: Improvement
> Components: core/FSTs
> Reporter: Michael McCandless
> Priority: Minor
>
> When a node is close to the root, or it has many outgoing arcs, the FST
> writes the arcs as an array (each arc gets N bytes), so we can e.g. bin
> search on lookup.
> The problem is N is set to the max(numBytesPerArc), so if you have an outlier
> arc e.g. with a big output, you can waste many bytes for all the other arcs
> that didn't need so many bytes.
> I generated Kuromoji's FST and found it has 271187 wasted bytes vs total size
> 1535612 = ~18% wasted.
> It would be nice to reduce this.
> One thing we could do without packing is: in addNode, if we detect that
> number of wasted bytes is above some threshold, then don't do the expansion.
> Another thing, if we are packing: we could record stats in the first pass
> about which nodes wasted the most, and then in the second pass (paack) we
> could set the threshold based on the top X% nodes that waste ...
> Another idea is maybe to deref large outputs, so that the numBytesPerArc is
> more uniform ...
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
