Reduce wasted bytes in FST due to array arcs [LUCENE-4682]

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 ...

---
Migrated from [LUCENE-4682](https://issues.apache.org/jira/browse/LUCENE-4682) by Michael McCandless (@mikemccand), updated Dec 21 2017
Attachments: [fstByteStats.txt](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-4682/fstByteStats.txt), [kuromoji.wasted.bytes.txt](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-4682/kuromoji.wasted.bytes.txt), [LUCENE-4682.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-4682/LUCENE-4682.patch)
Linked issues:
- #9132

Start by reading the FST addNode path and the packing logic mentioned in the issue, then review LUCENE-4682.patch and the fstByteStats.txt and kuromoji.wasted.bytes.txt attachments. Define how wasted-byte thresholds or output dereferencing should be selected, and validate the result against the reported Kuromoji FST size and waste figures.

Written by the indexing model from the issue text.