You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2019/11/14 08:41:11 UTC

[lucene-solr] 06/07: LUCENE-8920: Reduce the memory used by direct addressing of arcs (#980)

This is an automated email from the ASF dual-hosted git repository.

jpountz pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git

commit 5dd9c4c04bcab9911b9a9f0b092eadc50262ee2c
Author: Bruno Roustant <33...@users.noreply.github.com>
AuthorDate: Wed Nov 13 22:48:13 2019 +0100

    LUCENE-8920: Reduce the memory used by direct addressing of arcs (#980)
---
 .../analysis/ja/dict/TokenInfoDictionary$fst.dat   | Bin 1698570 -> 1707541 bytes
 .../analysis/ko/dict/TokenInfoDictionary$fst.dat   | Bin 5640903 -> 6009053 bytes
 .../codecs/blocktreeords/OrdsSegmentTermsEnum.java |   2 +-
 .../src/java/org/apache/lucene/util/BitUtil.java   | 125 ++++
 .../java/org/apache/lucene/util/fst/Builder.java   | 114 +++-
 .../org/apache/lucene/util/fst/BytesStore.java     |  21 +
 .../src/java/org/apache/lucene/util/fst/FST.java   | 715 +++++++++++++++------
 .../java/org/apache/lucene/util/fst/FSTEnum.java   | 236 ++++---
 .../java/org/apache/lucene/util/fst/NodeHash.java  |  17 +-
 .../src/java/org/apache/lucene/util/fst/Util.java  |  29 +-
 .../test/org/apache/lucene/util/TestBitUtil.java   |  85 +++
 .../test/org/apache/lucene/util/fst/TestFSTs.java  |  33 +-
 .../org/apache/lucene/util/fst/TestFstDirect.java  | 106 ---
 .../lucene/util/fst/TestFstDirectAddressing.java   | 212 ++++++
 .../test/org/apache/lucene/util/fst/TestUtil.java  |  21 +-
 15 files changed, 1266 insertions(+), 450 deletions(-)

diff --git a/lucene/analysis/kuromoji/src/resources/org/apache/lucene/analysis/ja/dict/TokenInfoDictionary$fst.dat b/lucene/analysis/kuromoji/src/resources/org/apache/lucene/analysis/ja/dict/TokenInfoDictionary$fst.dat
index c06fd4a..9ffdbc9 100644
Binary files a/lucene/analysis/kuromoji/src/resources/org/apache/lucene/analysis/ja/dict/TokenInfoDictionary$fst.dat and b/lucene/analysis/kuromoji/src/resources/org/apache/lucene/analysis/ja/dict/TokenInfoDictionary$fst.dat differ
diff --git a/lucene/analysis/nori/src/resources/org/apache/lucene/analysis/ko/dict/TokenInfoDictionary$fst.dat b/lucene/analysis/nori/src/resources/org/apache/lucene/analysis/ko/dict/TokenInfoDictionary$fst.dat
index fa0cb32..bf84bd8 100644
Binary files a/lucene/analysis/nori/src/resources/org/apache/lucene/analysis/ko/dict/TokenInfoDictionary$fst.dat and b/lucene/analysis/nori/src/resources/org/apache/lucene/analysis/ko/dict/TokenInfoDictionary$fst.dat differ
diff --git a/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java b/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java
index d6a182b..d740b3b 100644
--- a/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java
+++ b/lucene/codecs/src/java/org/apache/lucene/codecs/blocktreeords/OrdsSegmentTermsEnum.java
@@ -1084,7 +1084,7 @@ public final class OrdsSegmentTermsEnum extends BaseTermsEnum {
         result.grow(1+upto);
         fr.index.readFirstRealTargetArc(arc.target(), arc, fstReader);
 
-        if (arc.bytesPerArc() != 0 && arc.arcIdx() > Integer.MIN_VALUE) {
+        if (arc.bytesPerArc() != 0 && arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
           // System.out.println("  array arcs");
           int low = 0;
           int high = arc.numArcs() -1;
diff --git a/lucene/core/src/java/org/apache/lucene/util/BitUtil.java b/lucene/core/src/java/org/apache/lucene/util/BitUtil.java
index bcc66a1..f9557bc 100644
--- a/lucene/core/src/java/org/apache/lucene/util/BitUtil.java
+++ b/lucene/core/src/java/org/apache/lucene/util/BitUtil.java
@@ -178,4 +178,129 @@ public final class BitUtil {
      return ((l >>> 1) ^ -(l & 1));
    }
 
+  /**
+   * Returns whether the bit at given zero-based index is set.
+   * <br>Example: bitIndex 66 means the third bit on the right of the second long.
+   *
+   * @param bits     The bits stored in an array of long for efficiency.
+   * @param numLongs The number of longs in {@code bits} to consider.
+   * @param bitIndex The bit zero-based index. It must be greater than or equal to 0,
+   *                 and strictly less than {@code numLongs * Long.SIZE}.
+   */
+  public static boolean isBitSet(long[] bits, int numLongs, int bitIndex) {
+    assert numLongs >= 0 && numLongs <= bits.length && bitIndex >= 0 && bitIndex < numLongs * Long.SIZE
+        : "bitIndex=" + bitIndex + " numLongs=" + numLongs + " bits.length=" + bits.length;
+    return (bits[bitIndex / Long.SIZE] & (1L << bitIndex)) != 0; // Shifts are mod 64.
+  }
+
+  /**
+   * Counts all bits set in the provided longs.
+   *
+   * @param bits     The bits stored in an array of long for efficiency.
+   * @param numLongs The number of longs in {@code bits} to consider.
+   */
+  public static int countBits(long[] bits, int numLongs) {
+    assert numLongs >= 0 && numLongs <= bits.length
+        : "numLongs=" + numLongs + " bits.length=" + bits.length;
+    int bitCount = 0;
+    for (int i = 0; i < numLongs; i++) {
+      bitCount += Long.bitCount(bits[i]);
+    }
+    return bitCount;
+  }
+
+  /**
+   * Counts the bits set up to the given bit zero-based index, exclusive.
+   * <br>In other words, how many 1s there are up to the bit at the given index excluded.
+   * <br>Example: bitIndex 66 means the third bit on the right of the second long.
+   *
+   * @param bits     The bits stored in an array of long for efficiency.
+   * @param numLongs The number of longs in {@code bits} to consider.
+   * @param bitIndex The bit zero-based index, exclusive. It must be greater than or equal to 0,
+   *                 and less than or equal to {@code numLongs * Long.SIZE}.
+   */
+  public static int countBitsUpTo(long[] bits, int numLongs, int bitIndex) {
+    assert numLongs >= 0 && numLongs <= bits.length && bitIndex >= 0 && bitIndex <= numLongs * Long.SIZE
+        : "bitIndex=" + bitIndex + " numLongs=" + numLongs + " bits.length=" + bits.length;
+    int bitCount = 0;
+    int lastLong = bitIndex / Long.SIZE;
+    for (int i = 0; i < lastLong; i++) {
+      // Count the bits set for all plain longs.
+      bitCount += Long.bitCount(bits[i]);
+    }
+    if (lastLong < numLongs) {
+      // Prepare a mask with 1s on the right up to bitIndex exclusive.
+      long mask = (1L << bitIndex) - 1L; // Shifts are mod 64.
+      // Count the bits set only within the mask part, so up to bitIndex exclusive.
+      bitCount += Long.bitCount(bits[lastLong] & mask);
+    }
+    return bitCount;
+  }
+
+  /**
+   * Returns the index of the next bit set following the given bit zero-based index.
+   * <br>For example with bits 100011:
+   * the next bit set after index=-1 is at index=0;
+   * the next bit set after index=0 is at index=1;
+   * the next bit set after index=1 is at index=5;
+   * there is no next bit set after index=5.
+   *
+   * @param bits     The bits stored in an array of long for efficiency.
+   * @param numLongs The number of longs in {@code bits} to consider.
+   * @param bitIndex The bit zero-based index. It must be greater than or equal to -1,
+   *                 and strictly less than {@code numLongs * Long.SIZE}.
+   * @return The zero-based index of the next bit set after the provided {@code bitIndex};
+   * or -1 if none.
+   */
+  public static int nextBitSet(long[] bits, int numLongs, int bitIndex) {
+    assert numLongs >= 0 && numLongs <= bits.length && bitIndex >= -1 && bitIndex < numLongs * Long.SIZE
+        : "bitIndex=" + bitIndex + " numLongs=" + numLongs + " bits.length=" + bits.length;
+    int longIndex = bitIndex / Long.SIZE;
+    // Prepare a mask with 1s on the left down to bitIndex exclusive.
+    long mask = -(1L << (bitIndex + 1)); // Shifts are mod 64.
+    long l = mask == -1 && bitIndex != -1 ? 0 : bits[longIndex] & mask;
+    while (l == 0) {
+      if (++longIndex == numLongs) {
+        return -1;
+      }
+      l = bits[longIndex];
+    }
+    return Long.numberOfTrailingZeros(l) + longIndex * 64;
+  }
+
+  /**
+   * Returns the index of the previous bit set preceding the given bit zero-based index.
+   * <br>For example with bits 100011:
+   * there is no previous bit set before index=0.
+   * the previous bit set before index=1 is at index=0;
+   * the previous bit set before index=5 is at index=1;
+   * the previous bit set before index=64 is at index=5;
+   *
+   * @param bits     The bits stored in an array of long for efficiency.
+   * @param numLongs The number of longs in {@code bits} to consider.
+   * @param bitIndex The bit zero-based index. It must be greater than or equal to 0,
+   *                 and less than or equal to {@code numLongs * Long.SIZE}.
+   * @return The zero-based index of the previous bit set before the provided {@code bitIndex};
+   * or -1 if none.
+   */
+  public static int previousBitSet(long[] bits, int numLongs, int bitIndex) {
+    assert numLongs >= 0 && numLongs <= bits.length && bitIndex >= 0 && bitIndex <= numLongs * Long.SIZE
+        : "bitIndex=" + bitIndex + " numLongs=" + numLongs + " bits.length=" + bits.length;
+    int longIndex = bitIndex / Long.SIZE;
+    long l;
+    if (longIndex == numLongs) {
+      l = 0;
+    } else {
+      // Prepare a mask with 1s on the right up to bitIndex exclusive.
+      long mask = (1L << bitIndex) - 1L; // Shifts are mod 64.
+      l = bits[longIndex] & mask;
+    }
+    while (l == 0) {
+      if (longIndex-- == 0) {
+        return -1;
+      }
+      l = bits[longIndex];
+    }
+    return 63 - Long.numberOfLeadingZeros(l) + longIndex * 64;
+  }
 }
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/Builder.java b/lucene/core/src/java/org/apache/lucene/util/fst/Builder.java
index c54b144..a35c4d7 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/Builder.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/Builder.java
@@ -19,6 +19,7 @@ package org.apache.lucene.util.fst;
 
 import java.io.IOException;
 
+import org.apache.lucene.store.ByteArrayDataOutput;
 import org.apache.lucene.util.ArrayUtil;
 import org.apache.lucene.util.IntsRef;
 import org.apache.lucene.util.IntsRefBuilder;
@@ -50,6 +51,30 @@ import org.apache.lucene.util.fst.FST.INPUT_TYPE; // javadoc
 
 public class Builder<T> {
 
+  /**
+   * Default oversizing factor used to decide whether to encode a node with direct addressing or binary search.
+   * Default is 1: ensure no oversizing on average.
+   * <p>
+   * This factor does not determine whether to encode a node with a list of variable length arcs or with
+   * fixed length arcs. It only determines the effective encoding of a node that is already known to be
+   * encoded with fixed length arcs.
+   * See {@code FST.shouldExpandNodeWithFixedLengthArcs()}
+   * and {@code FST.shouldExpandNodeWithDirectAddressing()}.
+   * <p>
+   * For English words we measured 217K nodes, only 3.27% nodes are encoded with fixed length arcs,
+   * and 99.99% of them with direct addressing. Overall FST memory reduced by 1.67%.
+   * <p>
+   * For worst case we measured 168K nodes, 50% of them are encoded with fixed length arcs,
+   * and 14% of them with direct encoding. Overall FST memory reduced by 0.8%.
+   * <p>
+   * Use {@code TestFstDirectAddressing.main()}
+   * and {@code TestFstDirectAddressing.testWorstCaseForDirectAddressing()}
+   * to evaluate a change.
+   *
+   * @see #setDirectAddressingMaxOversizingFactor
+   */
+  static final float DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR = 1.0f;
+
   private final NodeHash<T> dedupHash;
   final FST<T> fst;
   private final T NO_OUTPUT;
@@ -83,12 +108,18 @@ public class Builder<T> {
   long lastFrozenNode;
 
   // Reused temporarily while building the FST:
-  int[] reusedBytesPerArc = new int[4];
+  int[] numBytesPerArc = new int[4];
+  int[] numLabelBytesPerArc = new int[numBytesPerArc.length];
+  final FixedLengthArcsBuffer fixedLengthArcsBuffer = new FixedLengthArcsBuffer();
 
   long arcCount;
   long nodeCount;
+  long binarySearchNodeCount;
+  long directAddressingNodeCount;
 
-  boolean allowArrayArcs;
+  boolean allowFixedLengthArcs;
+  float directAddressingMaxOversizingFactor = DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR;
+  long directAddressingExpansionCredit;
 
   BytesStore bytes;
 
@@ -138,9 +169,9 @@ public class Builder<T> {
    *    FSA, use {@link NoOutputs#getSingleton()} and {@link NoOutputs#getNoOutput()} as the
    *    singleton output object.
    *
-   * @param allowArrayArcs Pass false to disable the array arc optimization
-   *    while building the FST; this will make the resulting
-   *    FST smaller but slower to traverse.
+   * @param allowFixedLengthArcs Pass false to disable the fixed length arc optimization (binary search or
+   *    direct addressing) while building the FST; this will make the resulting FST smaller but slower to
+   *    traverse.
    *
    * @param bytesPageBits How many bits wide to make each
    *    byte[] block in the BytesStore; if you know the FST
@@ -149,12 +180,12 @@ public class Builder<T> {
    */
   public Builder(FST.INPUT_TYPE inputType, int minSuffixCount1, int minSuffixCount2, boolean doShareSuffix,
                  boolean doShareNonSingletonNodes, int shareMaxTailLength, Outputs<T> outputs,
-                 boolean allowArrayArcs, int bytesPageBits) {
+                 boolean allowFixedLengthArcs, int bytesPageBits) {
     this.minSuffixCount1 = minSuffixCount1;
     this.minSuffixCount2 = minSuffixCount2;
     this.doShareNonSingletonNodes = doShareNonSingletonNodes;
     this.shareMaxTailLength = shareMaxTailLength;
-    this.allowArrayArcs = allowArrayArcs;
+    this.allowFixedLengthArcs = allowFixedLengthArcs;
     fst = new FST<>(inputType, outputs, bytesPageBits);
     bytes = fst.bytes;
     assert bytes != null;
@@ -173,6 +204,27 @@ public class Builder<T> {
     }
   }
 
+  /**
+   * Overrides the default the maximum oversizing of fixed array allowed to enable direct addressing
+   * of arcs instead of binary search.
+   * <p>
+   * Setting this factor to a negative value (e.g. -1) effectively disables direct addressing,
+   * only binary search nodes will be created.
+   *
+   * @see #DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR
+   */
+  public Builder<T> setDirectAddressingMaxOversizingFactor(float factor) {
+    directAddressingMaxOversizingFactor = factor;
+    return this;
+  }
+
+  /**
+   * @see #setDirectAddressingMaxOversizingFactor(float)
+   */
+  public float getDirectAddressingMaxOversizingFactor() {
+    return directAddressingMaxOversizingFactor;
+  }
+
   public long getTermCount() {
     return frontier[0].inputCount;
   }
@@ -639,4 +691,52 @@ public class Builder<T> {
       }
     }
   }
+
+  /**
+   * Reusable buffer for building nodes with fixed length arcs (binary search or direct addressing).
+   */
+  static class FixedLengthArcsBuffer {
+
+    // Initial capacity is the max length required for the header of a node with fixed length arcs:
+    // header(byte) + numArcs(vint) + numBytes(vint)
+    private byte[] bytes = new byte[11];
+    private final ByteArrayDataOutput bado = new ByteArrayDataOutput(bytes);
+
+    /** Ensures the capacity of the internal byte array. Enlarges it if needed. */
+    FixedLengthArcsBuffer ensureCapacity(int capacity) {
+      if (bytes.length < capacity) {
+        bytes = new byte[ArrayUtil.oversize(capacity, Byte.BYTES)];
+        bado.reset(bytes);
+      }
+      return this;
+    }
+
+    FixedLengthArcsBuffer resetPosition() {
+      bado.reset(bytes);
+      return this;
+    }
+
+    FixedLengthArcsBuffer writeByte(byte b) {
+      bado.writeByte(b);
+      return this;
+    }
+
+    FixedLengthArcsBuffer writeVInt(int i) {
+      try {
+        bado.writeVInt(i);
+      } catch (IOException e) { // Never thrown.
+        throw new RuntimeException(e);
+      }
+      return this;
+    }
+
+    int getPosition() {
+      return bado.getPosition();
+    }
+
+    /** Gets the internal byte array. */
+    byte[] getBytes() {
+      return bytes;
+    }
+  }
 }
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/BytesStore.java b/lucene/core/src/java/org/apache/lucene/util/fst/BytesStore.java
index 37b2baa..02ff583 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/BytesStore.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/BytesStore.java
@@ -239,6 +239,27 @@ class BytesStore extends DataOutput implements Accountable {
     }
   }
 
+  /** Copies bytes from this store to a target byte array. */
+  public void copyBytes(long src, byte[] dest, int offset, int len) {
+    int blockIndex = (int) (src >> blockBits);
+    int upto = (int) (src & blockMask);
+    byte[] block = blocks.get(blockIndex);
+    while (len > 0) {
+      int chunk = blockSize - upto;
+      if (len <= chunk) {
+        System.arraycopy(block, upto, dest, offset, len);
+        break;
+      } else {
+        System.arraycopy(block, upto, dest, offset, chunk);
+        blockIndex++;
+        block = blocks.get(blockIndex);
+        upto = 0;
+        len -= chunk;
+        offset += chunk;
+      }
+    }
+  }
+
   /** Writes an int at the absolute position without
    *  changing the current pointer. */
   public void writeInt(long pos, int value) {
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/FST.java b/lucene/core/src/java/org/apache/lucene/util/fst/FST.java
index 3389343..89e4e62 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/FST.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/FST.java
@@ -26,7 +26,6 @@ import java.nio.file.Files;
 import java.nio.file.Path;
 
 import org.apache.lucene.codecs.CodecUtil;
-import org.apache.lucene.store.ByteArrayDataOutput;
 import org.apache.lucene.store.DataInput;
 import org.apache.lucene.store.DataOutput;
 import org.apache.lucene.store.InputStreamDataInput;
@@ -34,6 +33,7 @@ import org.apache.lucene.store.OutputStreamDataOutput;
 import org.apache.lucene.store.RAMOutputStream;
 import org.apache.lucene.util.Accountable;
 import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BitUtil;
 import org.apache.lucene.util.Constants;
 import org.apache.lucene.util.RamUsageEstimator;
 
@@ -81,33 +81,43 @@ public final class FST<T> implements Accountable {
 
   private static final int BIT_ARC_HAS_FINAL_OUTPUT = 1 << 5;
 
-  // We use this as a marker (because this one flag is
-  // illegal by itself ...):
-  private static final byte ARCS_AS_ARRAY_PACKED = BIT_ARC_HAS_FINAL_OUTPUT;
+  /** Value of the arc flags to declare a node with fixed length arcs
+   * designed for binary search. */
+  // We use this as a marker because this one flag is illegal by itself.
+  public static final byte ARCS_FOR_BINARY_SEARCH = BIT_ARC_HAS_FINAL_OUTPUT;
 
-  // this means either of these things in different contexts
-  // in the midst of a direct array:
-  private static final byte BIT_MISSING_ARC = 1 << 6;
+  /** Value of the arc flags to declare a node with fixed length arcs
+   * and bit table designed for direct addressing. */
+  static final byte ARCS_FOR_DIRECT_ADDRESSING = 1 << 6;
 
   /**
-   * @see #shouldExpand(Builder, Builder.UnCompiledNode)
+   * @see #shouldExpandNodeWithFixedLengthArcs
    */
-  static final int FIXED_ARRAY_SHALLOW_DISTANCE = 3; // 0 => only root node.
+  static final int FIXED_LENGTH_ARC_SHALLOW_DEPTH = 3; // 0 => only root node.
 
   /**
-   * @see #shouldExpand(Builder, Builder.UnCompiledNode)
+   * @see #shouldExpandNodeWithFixedLengthArcs
    */
-  static final int FIXED_ARRAY_NUM_ARCS_SHALLOW = 5;
+  static final int FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS = 5;
 
   /**
-   * @see #shouldExpand(Builder, Builder.UnCompiledNode)
+   * @see #shouldExpandNodeWithFixedLengthArcs
    */
-  static final int FIXED_ARRAY_NUM_ARCS_DEEP = 10;
+  static final int FIXED_LENGTH_ARC_DEEP_NUM_ARCS = 10;
+
+  /**
+   * Maximum oversizing factor allowed for direct addressing compared to binary search when expansion
+   * credits allow the oversizing. This factor prevents expansions that are obviously too costly even
+   * if there are sufficient credits.
+   *
+   * @see #shouldExpandNodeWithDirectAddressing
+   */
+  private static final float DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR = 1.66f;
 
   // Increment version to change it
   private static final String FILE_FORMAT_NAME = "FST";
   private static final int VERSION_START = 6;
-  private static final int VERSION_CURRENT = VERSION_START;
+  private static final int VERSION_CURRENT = 7;
 
   // Never serialized; just used to represent the virtual
   // final node w/ no arcs:
@@ -145,6 +155,8 @@ public final class FST<T> implements Accountable {
   /** Represents a single arc. */
   public static final class Arc<T> {
 
+    //*** Arc fields.
+
     private int label;
 
     private T output;
@@ -155,17 +167,25 @@ public final class FST<T> implements Accountable {
 
     private T nextFinalOutput;
 
-    // address (into the byte[]), or ord/address if label == END_LABEL
     private long nextArc;
 
+    private int arcIdx;
+
+    //*** Fields for arcs belonging to a node with fixed length arcs.
+    // So only valid when bytesPerArc != 0.
+
+    private byte nodeFlags;
+
     private long posArcsStart;
 
     private int bytesPerArc;
 
-    private int arcIdx;
-
     private int numArcs;
 
+    private BitTable bitTable;
+
+    private int firstLabel;
+
     /** Returns this */
     public Arc<T> copyFrom(Arc<T> other) {
       label = other.label();
@@ -174,11 +194,16 @@ public final class FST<T> implements Accountable {
       output = other.output();
       nextFinalOutput = other.nextFinalOutput();
       nextArc = other.nextArc();
+      nodeFlags = other.nodeFlags();
       bytesPerArc = other.bytesPerArc();
       if (bytesPerArc() != 0) {
         posArcsStart = other.posArcsStart();
         arcIdx = other.arcIdx();
         numArcs = other.numArcs();
+        if (nodeFlags() == ARCS_FOR_DIRECT_ADDRESSING) {
+          bitTable = other.bitTable() == null ? null : other.bitTable().copy();
+          firstLabel = other.firstLabel();
+        }
       }
       return this;
     }
@@ -195,10 +220,6 @@ public final class FST<T> implements Accountable {
       return flag(BIT_FINAL_ARC);
     }
 
-    public boolean isPackedArray() {
-      return bytesPerArc != 0 && arcIdx > Integer.MIN_VALUE;
-    }
-
     @Override
     public String toString() {
       StringBuilder b = new StringBuilder();
@@ -236,7 +257,7 @@ public final class FST<T> implements Accountable {
       return output;
     }
 
-    /** To node (ord or address) */
+    /** Ord/address to target node. */
     public long target() {
       return target;
     }
@@ -249,38 +270,126 @@ public final class FST<T> implements Accountable {
       return nextFinalOutput;
     }
 
-    long nextArc() {
+    /** Address (into the byte[]) of the next arc - only for list of variable length arc.
+     * Or ord/address to the next node if label == {@link #END_LABEL}. */
+     long nextArc() {
       return nextArc;
     }
 
-    /** Where the first arc in the array starts; only valid if
-     *  bytesPerArc != 0 */
+    /** Where we are in the array; only valid if bytesPerArc != 0. */
+    public int arcIdx() {
+      return arcIdx;
+    }
+
+    /** Node header flags. Only meaningful to check if the value is either
+     * {@link #ARCS_FOR_BINARY_SEARCH} or {@link #ARCS_FOR_DIRECT_ADDRESSING}
+     * (other value when bytesPerArc == 0). */
+    public byte nodeFlags() {
+      return nodeFlags;
+    }
+
+    /** Where the first arc in the array starts; only valid if bytesPerArc != 0 */
     public long posArcsStart() {
       return posArcsStart;
     }
 
-    /** Non-zero if this arc is part of an array, which means all
+    /** Non-zero if this arc is part of a node with fixed length arcs, which means all
      *  arcs for the node are encoded with a fixed number of bytes so
-     *  that we can random access by index.  We do when there are enough
-     *  arcs leaving one node.  It wastes some bytes but gives faster
-     *  lookups. */
+     *  that we binary search or direct address. We do when there are enough
+     *  arcs leaving one node. It wastes some bytes but gives faster lookups. */
     public int bytesPerArc() {
       return bytesPerArc;
     }
 
-    /** Where we are in the array; only valid if bytesPerArc != 0, and the array has no holes.
-     * arcIdx = Integer.MIN_VALUE indicates that the arc is part of a direct array, addressed by
-     * label.
-     */
-    public int arcIdx() {
-      return arcIdx;
-    }
-
-    /** How many arc, if bytesPerArc == 0. Otherwise, the size of the arc array. If the array is
-     * direct, this may include holes. Otherwise it is also how many arcs are in the array */
+    /** How many arcs; only valid if bytesPerArc != 0 (fixed length arcs).
+     * For a node designed for binary search this is the array size.
+     * For a node designed for direct addressing, this is the label range. */
     public int numArcs() {
       return numArcs;
     }
+
+    /** Table of bits of a direct addressing node.
+     * Only valid if nodeFlags == {@link #ARCS_FOR_DIRECT_ADDRESSING};
+     * may be null otherwise. */
+    BitTable bitTable() {
+      return bitTable;
+    }
+
+    /** The table of bits of a direct addressing node created lazily. */
+    BitTable getOrCreateBitTable() {
+      if (bitTable == null) {
+        bitTable = new BitTable();
+      }
+      return bitTable;
+    }
+
+    /** First label of a direct addressing node.
+     * Only valid if nodeFlags == {@link #ARCS_FOR_DIRECT_ADDRESSING}. */
+    int firstLabel() {
+      return firstLabel;
+    }
+
+    /**
+     * Reusable table of bits using an array of long internally.
+     */
+    static class BitTable {
+
+      private long[] bits;
+      private int numLongs;
+
+      /** Sets the number of longs in the internal long array.
+       * Enlarges it if needed. Always clears the array. */
+      BitTable setNumLongs(int numLongs) {
+        assert numLongs >= 0;
+        this.numLongs = numLongs;
+        if (bits == null || bits.length < numLongs) {
+          bits = new long[ArrayUtil.oversize(numLongs, Long.BYTES)];
+        } else {
+          for (int i = 0; i < numLongs; i++) {
+            bits[i] = 0L;
+          }
+        }
+        return this;
+      }
+
+      /** Creates a new {@link BitTable} by copying this one. */
+      BitTable copy() {
+        BitTable bitTable = new BitTable();
+        bitTable.bits = ArrayUtil.copyOfSubArray(bits, 0, bits.length);
+        bitTable.numLongs = numLongs;
+        return bitTable;
+      }
+
+      boolean assertIsValid() {
+        assert numLongs > 0 && numLongs <= bits.length;
+        return true;
+      }
+
+      /** Forwards to {@link BitUtil#isBitSet(long[], int, int)}. */
+      boolean isBitSet(int bitIndex) {
+        return BitUtil.isBitSet(bits, numLongs, bitIndex);
+      }
+
+      /** Forwards to {@link BitUtil#countBits(long[], int)}. */
+      int countBits() {
+        return BitUtil.countBits(bits, numLongs);
+      }
+
+      /** Forwards to {@link BitUtil#countBitsUpTo(long[], int, int)}. */
+      int countBitsUpTo(int bitIndex) {
+        return BitUtil.countBitsUpTo(bits, numLongs, bitIndex);
+      }
+
+      /** Forwards to {@link BitUtil#nextBitSet(long[], int, int)}. */
+      int nextBitSet(int bitIndex) {
+        return BitUtil.nextBitSet(bits, numLongs, bitIndex);
+      }
+
+      /** Forwards to {@link BitUtil#previousBitSet(long[], int, int)}. */
+      int previousBitSet(int bitIndex) {
+        return BitUtil.previousBitSet(bits, numLongs, bitIndex);
+      }
+    }
   }
 
   private static boolean flag(int flags, int bit) {
@@ -436,7 +545,7 @@ public final class FST<T> implements Accountable {
       int cacheRAM = (int) ramBytesUsed(arcs);
 
       // Don't cache if there are only a few arcs or if the cache would use > 20% RAM of the FST itself:
-      if (count >= FIXED_ARRAY_NUM_ARCS_SHALLOW && cacheRAM < ramBytesUsed()/5) {
+      if (count >= FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS && cacheRAM < ramBytesUsed()/5) {
         cachedRootArcs = arcs;
         cachedArcsBytesUsed = cacheRAM;
       }
@@ -576,11 +685,12 @@ public final class FST<T> implements Accountable {
     final long startAddress = builder.bytes.getPosition();
     //System.out.println("  startAddr=" + startAddress);
 
-    final boolean doFixedArray = shouldExpand(builder, nodeIn);
-    if (doFixedArray) {
-      //System.out.println("  fixedArray");
-      if (builder.reusedBytesPerArc.length < nodeIn.numArcs) {
-        builder.reusedBytesPerArc = new int[ArrayUtil.oversize(nodeIn.numArcs, 1)];
+    final boolean doFixedLengthArcs = shouldExpandNodeWithFixedLengthArcs(builder, nodeIn);
+    if (doFixedLengthArcs) {
+      //System.out.println("  fixed length arcs");
+      if (builder.numBytesPerArc.length < nodeIn.numArcs) {
+        builder.numBytesPerArc = new int[ArrayUtil.oversize(nodeIn.numArcs, Integer.BYTES)];
+        builder.numLabelBytesPerArc = new int[builder.numBytesPerArc.length];
       }
     }
 
@@ -590,6 +700,7 @@ public final class FST<T> implements Accountable {
 
     long lastArcStart = builder.bytes.getPosition();
     int maxBytesPerArc = 0;
+    int maxBytesPerArcWithoutLabel = 0;
     for(int arcIdx=0; arcIdx < nodeIn.numArcs; arcIdx++) {
       final Builder.Arc<T> arc = nodeIn.arcs[arcIdx];
       final Builder.CompiledNode target = (Builder.CompiledNode) arc.target;
@@ -600,7 +711,7 @@ public final class FST<T> implements Accountable {
         flags += BIT_LAST_ARC;
       }
 
-      if (builder.lastFrozenNode == target.node && !doFixedArray) {
+      if (builder.lastFrozenNode == target.node && !doFixedLengthArcs) {
         // TODO: for better perf (but more RAM used) we
         // could avoid this except when arc is "near" the
         // last arc:
@@ -627,7 +738,9 @@ public final class FST<T> implements Accountable {
       }
 
       builder.bytes.writeByte((byte) flags);
+      long labelStart = builder.bytes.getPosition();
       writeLabel(builder.bytes, arc.label);
+      int numLabelBytes = (int) (builder.bytes.getPosition() - labelStart);
 
       // System.out.println("  write arc: label=" + (char) arc.label + " flags=" + flags + " target=" + target.node + " pos=" + bytes.getPosition() + " output=" + outputs.outputToString(arc.output));
 
@@ -649,15 +762,18 @@ public final class FST<T> implements Accountable {
 
       // just write the arcs "like normal" on first pass, but record how many bytes each one took
       // and max byte size:
-      if (doFixedArray) {
-        builder.reusedBytesPerArc[arcIdx] = (int) (builder.bytes.getPosition() - lastArcStart);
+      if (doFixedLengthArcs) {
+        int numArcBytes = (int) (builder.bytes.getPosition() - lastArcStart);
+        builder.numBytesPerArc[arcIdx] = numArcBytes;
+        builder.numLabelBytesPerArc[arcIdx] = numLabelBytes;
         lastArcStart = builder.bytes.getPosition();
-        maxBytesPerArc = Math.max(maxBytesPerArc, builder.reusedBytesPerArc[arcIdx]);
-        //System.out.println("    bytes=" + builder.reusedBytesPerArc[arcIdx]);
+        maxBytesPerArc = Math.max(maxBytesPerArc, numArcBytes);
+        maxBytesPerArcWithoutLabel = Math.max(maxBytesPerArcWithoutLabel, numArcBytes - numLabelBytes);
+        //System.out.println("    arcBytes=" + numArcBytes + " labelBytes=" + numLabelBytes);
       }
     }
 
-    // TODO: try to avoid wasteful cases: disable doFixedArray in that case
+    // TODO: try to avoid wasteful cases: disable doFixedLengthArcs in that case
     /* 
      * 
      * LUCENE-4682: what is a fair heuristic here?
@@ -667,65 +783,245 @@ public final class FST<T> implements Accountable {
      * 3. waste: numBytes vs numBytesExpanded
      * 
      * the one below just looks at #3
-    if (doFixedArray) {
+    if (doFixedLengthArcs) {
       // rough heuristic: make this 1.25 "waste factor" a parameter to the phd ctor????
       int numBytes = lastArcStart - startAddress;
       int numBytesExpanded = maxBytesPerArc * nodeIn.numArcs;
       if (numBytesExpanded > numBytes*1.25) {
-        doFixedArray = false;
+        doFixedLengthArcs = false;
       }
     }
     */
 
-    if (doFixedArray) {
-      final int MAX_HEADER_SIZE = 11; // header(byte) + numArcs(vint) + numBytes(vint)
+    if (doFixedLengthArcs) {
       assert maxBytesPerArc > 0;
       // 2nd pass just "expands" all arcs to take up a fixed byte size
 
-      // create the header
-      // TODO: clean this up: or just rewind+reuse and deal with it
-      byte[] header = new byte[MAX_HEADER_SIZE];
-      ByteArrayDataOutput bad = new ByteArrayDataOutput(header);
-      // write a "false" first arc:
-      bad.writeByte(ARCS_AS_ARRAY_PACKED);
-      bad.writeVInt(nodeIn.numArcs);
-      bad.writeVInt(maxBytesPerArc);
-      int headerLen = bad.getPosition();
-      
-      final long fixedArrayStart = startAddress + headerLen;
-
-      writeArrayPacked(builder, nodeIn, fixedArrayStart, maxBytesPerArc);
-      
-      // now write the header
-      builder.bytes.writeBytes(startAddress, header, 0, headerLen);
+      int labelRange = nodeIn.arcs[nodeIn.numArcs - 1].label - nodeIn.arcs[0].label + 1;
+      assert labelRange > 0;
+      if (shouldExpandNodeWithDirectAddressing(builder, nodeIn, maxBytesPerArc, maxBytesPerArcWithoutLabel, labelRange)) {
+        writeNodeForDirectAddressing(builder, nodeIn, startAddress, maxBytesPerArcWithoutLabel, labelRange);
+        builder.directAddressingNodeCount++;
+      } else {
+        writeNodeForBinarySearch(builder, nodeIn, startAddress, maxBytesPerArc);
+        builder.binarySearchNodeCount++;
+      }
     }
 
     final long thisNodeAddress = builder.bytes.getPosition()-1;
-
     builder.bytes.reverse(startAddress, thisNodeAddress);
-
     builder.nodeCount++;
     return thisNodeAddress;
   }
 
-  private void writeArrayPacked(Builder<T> builder, Builder.UnCompiledNode<T> nodeIn, long fixedArrayStart, int maxBytesPerArc) {
-    // expand the arcs in place, backwards
+  /**
+   * Returns whether the given node should be expanded with fixed length arcs.
+   * Nodes will be expanded depending on their depth (distance from the root node) and their number
+   * of arcs.
+   * <p>
+   * Nodes with fixed length arcs use more space, because they encode all arcs with a fixed number
+   * of bytes, but they allow either binary search or direct addressing on the arcs (instead of linear
+   * scan) on lookup by arc label.
+   */
+  private boolean shouldExpandNodeWithFixedLengthArcs(Builder<T> builder, Builder.UnCompiledNode<T> node) {
+    return builder.allowFixedLengthArcs &&
+        ((node.depth <= FIXED_LENGTH_ARC_SHALLOW_DEPTH && node.numArcs >= FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS) ||
+            node.numArcs >= FIXED_LENGTH_ARC_DEEP_NUM_ARCS);
+  }
+
+  /**
+   * Returns whether the given node should be expanded with direct addressing instead of binary search.
+   * <p>
+   * Prefer direct addressing for performance if it does not oversize binary search byte size too much,
+   * so that the arcs can be directly addressed by label.
+   *
+   * @see Builder#getDirectAddressingMaxOversizingFactor()
+   */
+  private boolean shouldExpandNodeWithDirectAddressing(Builder<T> builder, Builder.UnCompiledNode<T> nodeIn,
+                                                       int numBytesPerArc, int maxBytesPerArcWithoutLabel, int labelRange) {
+    // Anticipate precisely the size of the encodings.
+    int sizeForBinarySearch = numBytesPerArc * nodeIn.numArcs;
+    int sizeForDirectAddressing = getNumPresenceBytes(labelRange) + builder.numLabelBytesPerArc[0]
+        + maxBytesPerArcWithoutLabel * nodeIn.numArcs;
+
+    // Determine the allowed oversize compared to binary search.
+    // This is defined by a parameter of FST Builder (default 1: no oversize).
+    int allowedOversize = (int) (sizeForBinarySearch * builder.getDirectAddressingMaxOversizingFactor());
+    int expansionCost = sizeForDirectAddressing - allowedOversize;
+
+    // Select direct addressing if either:
+    // - Direct addressing size is smaller than binary search.
+    //   In this case, increment the credit by the reduced size (to use it later).
+    // - Direct addressing size is larger than binary search, but the positive credit allows the oversizing.
+    //   In this case, decrement the credit by the oversize.
+    // In addition, do not try to oversize to a clearly too large node size
+    // (this is the DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR parameter).
+    if (expansionCost <= 0 || (builder.directAddressingExpansionCredit >= expansionCost
+        && sizeForDirectAddressing <= allowedOversize * DIRECT_ADDRESSING_MAX_OVERSIZE_WITH_CREDIT_FACTOR)) {
+      builder.directAddressingExpansionCredit -= expansionCost;
+      return true;
+    }
+    return false;
+  }
+
+  private void writeNodeForBinarySearch(Builder<T> builder, Builder.UnCompiledNode<T> nodeIn, long startAddress, int maxBytesPerArc) {
+    // Build the header in a buffer.
+    // It is a false/special arc which is in fact a node header with node flags followed by node metadata.
+    builder.fixedLengthArcsBuffer
+        .resetPosition()
+        .writeByte(ARCS_FOR_BINARY_SEARCH)
+        .writeVInt(nodeIn.numArcs)
+        .writeVInt(maxBytesPerArc);
+    int headerLen = builder.fixedLengthArcsBuffer.getPosition();
+
+    // Expand the arcs in place, backwards.
     long srcPos = builder.bytes.getPosition();
-    long destPos = fixedArrayStart + nodeIn.numArcs * maxBytesPerArc;
+    long destPos = startAddress + headerLen + nodeIn.numArcs * maxBytesPerArc;
     assert destPos >= srcPos;
     if (destPos > srcPos) {
       builder.bytes.skipBytes((int) (destPos - srcPos));
-      for(int arcIdx = nodeIn.numArcs - 1; arcIdx >= 0; arcIdx--) {
+      for (int arcIdx = nodeIn.numArcs - 1; arcIdx >= 0; arcIdx--) {
         destPos -= maxBytesPerArc;
-        srcPos -= builder.reusedBytesPerArc[arcIdx];
-        //System.out.println("  repack arcIdx=" + arcIdx + " srcPos=" + srcPos + " destPos=" + destPos);
+        int arcLen = builder.numBytesPerArc[arcIdx];
+        srcPos -= arcLen;
         if (srcPos != destPos) {
-          //System.out.println("  copy len=" + builder.reusedBytesPerArc[arcIdx]);
-          assert destPos > srcPos: "destPos=" + destPos + " srcPos=" + srcPos + " arcIdx=" + arcIdx + " maxBytesPerArc=" + maxBytesPerArc + " reusedBytesPerArc[arcIdx]=" + builder.reusedBytesPerArc[arcIdx] + " nodeIn.numArcs=" + nodeIn.numArcs;
-          builder.bytes.copyBytes(srcPos, destPos, builder.reusedBytesPerArc[arcIdx]);
+          assert destPos > srcPos: "destPos=" + destPos + " srcPos=" + srcPos + " arcIdx=" + arcIdx + " maxBytesPerArc=" + maxBytesPerArc + " arcLen=" + arcLen + " nodeIn.numArcs=" + nodeIn.numArcs;
+          builder.bytes.copyBytes(srcPos, destPos, arcLen);
         }
       }
     }
+
+    // Write the header.
+    builder.bytes.writeBytes(startAddress, builder.fixedLengthArcsBuffer.getBytes(), 0, headerLen);
+  }
+
+  private void writeNodeForDirectAddressing(Builder<T> builder, Builder.UnCompiledNode<T> nodeIn, long startAddress, int maxBytesPerArcWithoutLabel, int labelRange) {
+    // Expand the arcs backwards in a buffer because we remove the labels.
+    // So the obtained arcs might occupy less space. This is the reason why this
+    // whole method is more complex.
+    // Drop the label bytes since we can infer the label based on the arc index,
+    // the presence bits, and the first label. Keep the first label.
+    int headerMaxLen = 11;
+    int numPresenceBytes = getNumPresenceBytes(labelRange);
+    long srcPos = builder.bytes.getPosition();
+    int totalArcBytes = builder.numLabelBytesPerArc[0] + nodeIn.numArcs * maxBytesPerArcWithoutLabel;
+    int bufferOffset = headerMaxLen + numPresenceBytes + totalArcBytes;
+    byte[] buffer = builder.fixedLengthArcsBuffer.ensureCapacity(bufferOffset).getBytes();
+    // Copy the arcs to the buffer, dropping all labels except first one.
+    for (int arcIdx = nodeIn.numArcs - 1; arcIdx >= 0; arcIdx--) {
+      bufferOffset -= maxBytesPerArcWithoutLabel;
+      int srcArcLen = builder.numBytesPerArc[arcIdx];
+      srcPos -= srcArcLen;
+      int labelLen = builder.numLabelBytesPerArc[arcIdx];
+      // Copy the flags.
+      builder.bytes.copyBytes(srcPos, buffer, bufferOffset, 1);
+      // Skip the label, copy the remaining.
+      int remainingArcLen = srcArcLen - 1 - labelLen;
+      if (remainingArcLen != 0) {
+        builder.bytes.copyBytes(srcPos + 1 + labelLen, buffer, bufferOffset + 1, remainingArcLen);
+      }
+      if (arcIdx == 0) {
+        // Copy the label of the first arc only.
+        bufferOffset -= labelLen;
+        builder.bytes.copyBytes(srcPos + 1, buffer, bufferOffset, labelLen);
+      }
+    }
+    assert bufferOffset == headerMaxLen + numPresenceBytes;
+
+    // Build the header in the buffer.
+    // It is a false/special arc which is in fact a node header with node flags followed by node metadata.
+    builder.fixedLengthArcsBuffer
+        .resetPosition()
+        .writeByte(ARCS_FOR_DIRECT_ADDRESSING)
+        .writeVInt(labelRange) // labelRange instead of numArcs.
+        .writeVInt(maxBytesPerArcWithoutLabel); // maxBytesPerArcWithoutLabel instead of maxBytesPerArc.
+    int headerLen = builder.fixedLengthArcsBuffer.getPosition();
+
+    // Prepare the builder byte store. Enlarge or truncate if needed.
+    long nodeEnd = startAddress + headerLen + numPresenceBytes + totalArcBytes;
+    long currentPosition = builder.bytes.getPosition();
+    if (nodeEnd >= currentPosition) {
+      builder.bytes.skipBytes((int) (nodeEnd - currentPosition));
+    } else {
+      builder.bytes.truncate(nodeEnd);
+    }
+    assert builder.bytes.getPosition() == nodeEnd;
+
+    // Write the header.
+    long writeOffset = startAddress;
+    builder.bytes.writeBytes(writeOffset, builder.fixedLengthArcsBuffer.getBytes(), 0, headerLen);
+    writeOffset += headerLen;
+
+    // Write the presence bits
+    writePresenceBits(builder, nodeIn, writeOffset, numPresenceBytes);
+    writeOffset += numPresenceBytes;
+
+    // Write the first label and the arcs.
+    builder.bytes.writeBytes(writeOffset, builder.fixedLengthArcsBuffer.getBytes(), bufferOffset, totalArcBytes);
+  }
+
+  private void writePresenceBits(Builder<T> builder, Builder.UnCompiledNode<T> nodeIn, long dest, int numPresenceBytes) {
+    long bytePos = dest;
+    byte presenceBits = 1; // The first arc is always present.
+    int presenceIndex = 0;
+    int previousLabel = nodeIn.arcs[0].label;
+    for (int arcIdx = 1; arcIdx < nodeIn.numArcs; arcIdx++) {
+      int label = nodeIn.arcs[arcIdx].label;
+      assert label > previousLabel;
+      presenceIndex += label - previousLabel;
+      while (presenceIndex >= Byte.SIZE) {
+        builder.bytes.writeByte(bytePos++, presenceBits);
+        presenceBits = 0;
+        presenceIndex -= Byte.SIZE;
+      }
+      // Set the bit at presenceIndex to flag that the corresponding arc is present.
+      presenceBits |= 1 << presenceIndex;
+      previousLabel = label;
+    }
+    assert presenceIndex == (nodeIn.arcs[nodeIn.numArcs - 1].label - nodeIn.arcs[0].label) % 8;
+    assert presenceBits != 0; // The last byte is not 0.
+    assert (presenceBits & (1 << presenceIndex)) != 0; // The last arc is always present.
+    builder.bytes.writeByte(bytePos++, presenceBits);
+    assert bytePos - dest == numPresenceBytes;
+  }
+
+  /** Gets the number of bytes required to flag the presence of each arc in the given label range, one bit per arc. */
+  private static int getNumPresenceBytes(int labelRange) {
+    return (labelRange + 7) / Byte.SIZE;
+  }
+
+  /**
+   * Reads the presence bits of a direct-addressing node, store them in the provided arc {@link Arc#bitTable()}
+   * and returns the number of presence bytes.
+   */
+  private int readPresenceBytes(Arc<T> arc, BytesReader in) throws IOException {
+    int numPresenceBytes = getNumPresenceBytes(arc.numArcs());
+    Arc.BitTable presenceBits = arc.getOrCreateBitTable().setNumLongs((numPresenceBytes + 7) / Long.BYTES);
+    for (int i = 0; i < numPresenceBytes; i++) {
+      // Read the next unsigned byte, shift it to the left, and appends it to the current long.
+      presenceBits.bits[i / Long.BYTES] |= (in.readByte() & 0xFFL) << (i * Byte.SIZE);
+    }
+    assert assertPresenceBytesAreValid(arc);
+    return numPresenceBytes;
+  }
+
+  private int getNumArcsDirectAddressing(Arc<T> arc) {
+    assert arc.nodeFlags() == ARCS_FOR_DIRECT_ADDRESSING;
+    return arc.bitTable().countBits();
+  }
+
+  private boolean assertPresenceBytesAreValid(Arc<T> arc) {
+    assert arc.bitTable() != null;
+    assert arc.bitTable().assertIsValid();
+    // First bit must be set.
+    assert arc.bitTable().isBitSet(0);
+    // Last bit must be set.
+    assert arc.bitTable().isBitSet(arc.numArcs() - 1);
+    // No bit set after the last arc.
+    assert arc.bitTable().nextBitSet(arc.numArcs() - 1) == -1;
+    // Total bit set (real num arcs) must be <= label range (stored in arc.numArcs()).
+    assert getNumArcsDirectAddressing(arc) <= arc.numArcs();
+    return true;
   }
 
   /** Fills virtual 'start' arc, ie, an empty incoming arc to the FST's start node */
@@ -765,19 +1061,29 @@ public final class FST<T> implements Accountable {
       arc.target = FINAL_END_NODE;
       arc.output = follow.nextFinalOutput();
       arc.flags = BIT_LAST_ARC;
+      arc.nodeFlags = arc.flags;
       return arc;
     } else {
       in.setPosition(follow.target());
-      final byte b = in.readByte();
-      if (b == ARCS_AS_ARRAY_PACKED) {
-        // array: jump straight to end
+      byte flags = arc.nodeFlags = in.readByte();
+      if (flags == ARCS_FOR_BINARY_SEARCH || flags == ARCS_FOR_DIRECT_ADDRESSING) {
+        // Special arc which is actually a node header for fixed length arcs.
+        // Jump straight to end to find the last arc.
         arc.numArcs = in.readVInt();
         arc.bytesPerArc = in.readVInt();
         //System.out.println("  array numArcs=" + arc.numArcs + " bpa=" + arc.bytesPerArc);
-        arc.posArcsStart = in.getPosition();
-        arc.arcIdx = arc.numArcs - 2;
+        if (flags == ARCS_FOR_DIRECT_ADDRESSING) {
+          readPresenceBytes(arc, in);
+          arc.firstLabel = readLabel(in);
+          arc.posArcsStart = in.getPosition();
+          readArcByDirectAddressing(arc, in, arc.numArcs() - 1);
+        } else {
+          arc.arcIdx = arc.numArcs() - 2;
+          arc.posArcsStart = in.getPosition();
+          readNextRealArc(arc, in);
+        }
       } else {
-        arc.flags = b;
+        arc.flags = flags;
         // non-array: linear scan
         arc.bytesPerArc = 0;
         //System.out.println("  scan");
@@ -800,8 +1106,8 @@ public final class FST<T> implements Accountable {
         // Undo the byte flags we read:
         in.skipBytes(-1);
         arc.nextArc = in.getPosition();
+        readNextRealArc(arc, in);
       }
-      readNextRealArc(arc, in);
       assert arc.isLast();
       return arc;
     }
@@ -833,6 +1139,7 @@ public final class FST<T> implements Accountable {
         arc.nextArc = follow.target();
       }
       arc.target = FINAL_END_NODE;
+      arc.nodeFlags = arc.flags;
       //System.out.println("    insert isFinal; nextArc=" + follow.target + " isLast=" + arc.isLast() + " output=" + outputs.outputToString(arc.output));
       return arc;
     } else {
@@ -844,21 +1151,20 @@ public final class FST<T> implements Accountable {
     in.setPosition(nodeAddress);
     //System.out.println("   flags=" + arc.flags);
 
-    byte flags = in.readByte();
-    if (flags == ARCS_AS_ARRAY_PACKED) {
-      //System.out.println("  fixedArray");
-      // this is first arc in a fixed-array
+    byte flags = arc.nodeFlags = in.readByte();
+    if (flags == ARCS_FOR_BINARY_SEARCH || flags == ARCS_FOR_DIRECT_ADDRESSING) {
+      //System.out.println("  fixed length arc");
+      // Special arc which is actually a node header for fixed length arcs.
       arc.numArcs = in.readVInt();
       arc.bytesPerArc = in.readVInt();
-      if (flags == ARCS_AS_ARRAY_PACKED) {
-        arc.arcIdx = -1;
-      } else {
-        arc.arcIdx = Integer.MIN_VALUE;
+      arc.arcIdx = -1;
+      if (flags == ARCS_FOR_DIRECT_ADDRESSING) {
+        readPresenceBytes(arc, in);
+        arc.firstLabel = readLabel(in);
       }
-      arc.nextArc = arc.posArcsStart = in.getPosition();
+      arc.posArcsStart = in.getPosition();
       //System.out.println("  bytesPer=" + arc.bytesPerArc + " numArcs=" + arc.numArcs + " arcsStart=" + pos);
     } else {
-      //arc.flags = b;
       arc.nextArc = nodeAddress;
       arc.bytesPerArc = 0;
     }
@@ -867,10 +1173,7 @@ public final class FST<T> implements Accountable {
   }
 
   /**
-   * Checks if <code>arc</code>'s target state is in expanded (or vector) format. 
-   * 
-   * @return Returns <code>true</code> if <code>arc</code> points to a state in an
-   * expanded array format.
+   * Returns whether <code>arc</code>'s target points to a node in expanded format (fixed length arcs).
    */
   boolean isExpandedTarget(Arc<T> follow, BytesReader in) throws IOException {
     if (!targetHasArcs(follow)) {
@@ -878,7 +1181,7 @@ public final class FST<T> implements Accountable {
     } else {
       in.setPosition(follow.target());
       byte flags = in.readByte();
-      return flags == ARCS_AS_ARRAY_PACKED;
+      return flags == ARCS_FOR_BINARY_SEARCH || flags == ARCS_FOR_DIRECT_ADDRESSING;
     }
   }
 
@@ -901,68 +1204,73 @@ public final class FST<T> implements Accountable {
     assert !arc.isLast();
 
     if (arc.label() == END_LABEL) {
-      //System.out.println("    nextArc fake " +
-      //arc.nextArc);
-      
-      long pos = arc.nextArc();
-      in.setPosition(pos);
-
-      final byte flags = in.readByte();
-      if (flags == ARCS_AS_ARRAY_PACKED) {
-        //System.out.println("    nextArc fixed array");
-        in.readVInt();
+      //System.out.println("    nextArc fake " + arc.nextArc);
+      // Next arc is the first arc of a node.
+      // Position to read the first arc label.
 
-        // Skip bytesPerArc:
-        in.readVInt();
-      } else {
-        in.setPosition(pos);
+      in.setPosition(arc.nextArc());
+      byte flags = in.readByte();
+      if (flags == ARCS_FOR_BINARY_SEARCH || flags == ARCS_FOR_DIRECT_ADDRESSING) {
+        //System.out.println("    nextArc fixed length arc");
+        // Special arc which is actually a node header for fixed length arcs.
+        int numArcs = in.readVInt();
+        in.readVInt(); // Skip bytesPerArc.
+        if (flags == ARCS_FOR_BINARY_SEARCH) {
+          in.readByte(); // Skip arc flags.
+        } else {
+          in.skipBytes(getNumPresenceBytes(numArcs));
+        }
       }
-      // skip flags
-      in.readByte();
     } else {
       if (arc.bytesPerArc() != 0) {
         //System.out.println("    nextArc real array");
-        // arcs are in an array
-        if (arc.arcIdx() >= 0) {
-          in.setPosition(arc.posArcsStart());
-          // point at next arc, -1 to skip flags
-          in.skipBytes((1 + arc.arcIdx()) * arc.bytesPerArc() + 1);
+        // Arcs have fixed length.
+        if (arc.nodeFlags() == ARCS_FOR_BINARY_SEARCH) {
+          // Point to next arc, -1 to skip arc flags.
+          in.setPosition(arc.posArcsStart() - (1 + arc.arcIdx()) * arc.bytesPerArc() - 1);
         } else {
-          in.setPosition(arc.nextArc());
-          byte flags = in.readByte();
-          // skip missing arcs
-          while (flag(flags, BIT_MISSING_ARC)) {
-            in.skipBytes(arc.bytesPerArc() - 1);
-            flags = in.readByte();
-          }
+          assert arc.nodeFlags() == ARCS_FOR_DIRECT_ADDRESSING;
+          // Direct addressing node. The label is not stored but rather inferred
+          // based on first label and arc index in the range.
+          assert assertPresenceBytesAreValid(arc);
+          assert arc.bitTable().isBitSet(arc.arcIdx());
+          int nextIndex = arc.bitTable().nextBitSet(arc.arcIdx());
+          assert nextIndex != -1;
+          return arc.firstLabel() + nextIndex;
         }
       } else {
-        // arcs are packed
-        //System.out.println("    nextArc real packed");
-        // -1 to skip flags
+        // Arcs have variable length.
+        //System.out.println("    nextArc real list");
+        // Position to next arc, -1 to skip flags.
         in.setPosition(arc.nextArc() - 1);
       }
     }
     return readLabel(in);
   }
 
-  public Arc<T> readArcAtPosition(Arc<T> arc, final BytesReader in, long pos) throws IOException {
-    in.setPosition(pos);
+  public Arc<T> readArcByIndex(Arc<T> arc, final BytesReader in, int idx) throws IOException {
+    assert idx >= 0 && idx < arc.numArcs();
+    in.setPosition(arc.posArcsStart() - idx * arc.bytesPerArc());
+    arc.arcIdx = idx;
     arc.flags = in.readByte();
-    arc.nextArc = pos;
-    while (flag(arc.flags(), BIT_MISSING_ARC)) {
-      // skip empty arcs
-      arc.nextArc -= arc.bytesPerArc();
-      in.skipBytes(arc.bytesPerArc() - 1);
-      arc.flags = in.readByte();
-    }
     return readArc(arc, in);
   }
 
-  public Arc<T> readArcByIndex(Arc<T> arc, final BytesReader in, int idx) throws IOException {
-    arc.arcIdx = idx;
-    assert arc.arcIdx() < arc.numArcs();
-    in.setPosition(arc.posArcsStart() - arc.arcIdx() * arc.bytesPerArc());
+  /** Reads a present direct addressing node arc, with the provided index in the label range.
+   *
+   * @param rangeIndex The index of the arc in the label range. It must be present.
+   *                   The real arc offset is computed based on the presence bits of
+   *                   the direct addressing node.
+   */
+  public Arc<T> readArcByDirectAddressing(Arc<T> arc, final BytesReader in, int rangeIndex) throws IOException {
+    assert arc.nodeFlags() == ARCS_FOR_DIRECT_ADDRESSING;
+    assert arc.bytesPerArc() > 0;
+    assert assertPresenceBytesAreValid(arc);
+    assert rangeIndex >= 0 && rangeIndex < arc.numArcs();
+    assert arc.bitTable().isBitSet(rangeIndex);
+    int presenceIndex = arc.bitTable().countBitsUpTo(rangeIndex);
+    in.setPosition(arc.posArcsStart() - presenceIndex * arc.bytesPerArc());
+    arc.arcIdx = rangeIndex;
     arc.flags = in.readByte();
     return readArc(arc, in);
   }
@@ -974,35 +1282,43 @@ public final class FST<T> implements Accountable {
     // TODO: can't assert this because we call from readFirstArc
     // assert !flag(arc.flags, BIT_LAST_ARC);
 
-    // this is a continuing arc in a fixed array
-    if (arc.bytesPerArc() != 0) {
-      // arcs are in an array
-      if (arc.arcIdx() > Integer.MIN_VALUE) {
+    switch (arc.nodeFlags()) {
+
+      case ARCS_FOR_BINARY_SEARCH:
+        assert arc.bytesPerArc() > 0;
         arc.arcIdx++;
-        assert arc.arcIdx < arc.numArcs;
+        assert arc.arcIdx() >= 0 && arc.arcIdx() < arc.numArcs();
         in.setPosition(arc.posArcsStart() - arc.arcIdx() * arc.bytesPerArc());
         arc.flags = in.readByte();
-      } else {
-        assert arc.nextArc() <= arc.posArcsStart() && arc.nextArc() > arc.posArcsStart() - arc.numArcs() * arc.bytesPerArc();
+        break;
+
+      case ARCS_FOR_DIRECT_ADDRESSING:
+        assert arc.bytesPerArc() > 0;
+        assert assertPresenceBytesAreValid(arc);
+        assert arc.arcIdx() == -1 || arc.bitTable().isBitSet(arc.arcIdx());
+        int nextIndex = arc.bitTable().nextBitSet(arc.arcIdx());
+        return readArcByDirectAddressing(arc, in, nextIndex);
+
+      default:
+        // Variable length arcs - linear search.
+        assert arc.bytesPerArc() == 0;
         in.setPosition(arc.nextArc());
         arc.flags = in.readByte();
-        while (flag(arc.flags(), BIT_MISSING_ARC)) {
-          // skip empty arcs
-          arc.nextArc = arc.nextArc() - arc.bytesPerArc();
-          in.skipBytes(arc.bytesPerArc() - 1);
-          arc.flags = in.readByte();
-        }
-      }
-    } else {
-      // arcs are packed
-      in.setPosition(arc.nextArc());
-      arc.flags = in.readByte();
     }
     return readArc(arc, in);
   }
 
+  /**
+   * Reads an arc.
+   * <br>Precondition: The arc flags byte has already been read and set;
+   * the given BytesReader is positioned just after the arc flags byte.
+   */
   private Arc<T> readArc(Arc<T> arc, BytesReader in) throws IOException {
-    arc.label = readLabel(in);
+    if (arc.nodeFlags() == ARCS_FOR_DIRECT_ADDRESSING) {
+      arc.label = arc.firstLabel() + arc.arcIdx();
+    } else {
+      arc.label = readLabel(in);
+    }
 
     if (arc.flag(BIT_ARC_HAS_OUTPUT)) {
       arc.output = outputs.read(in);
@@ -1022,13 +1338,9 @@ public final class FST<T> implements Accountable {
       } else {
         arc.target = NON_FINAL_END_NODE;
       }
-      if (arc.bytesPerArc() == 0) {
-        arc.nextArc = in.getPosition();
-      } else {
-        arc.nextArc -= arc.bytesPerArc();
-      }
+      arc.nextArc = in.getPosition(); // Only useful for list.
     } else if (arc.flag(BIT_TARGET_NEXT)) {
-      arc.nextArc = in.getPosition();
+      arc.nextArc = in.getPosition(); // Only useful for list.
       // TODO: would be nice to make this lazy -- maybe
       // caller doesn't need the target and is scanning arcs...
       if (!arc.flag(BIT_LAST_ARC)) {
@@ -1036,21 +1348,14 @@ public final class FST<T> implements Accountable {
           // must scan
           seekToNextNode(in);
         } else {
-          in.setPosition(arc.posArcsStart());
-          in.skipBytes(arc.bytesPerArc() * arc.numArcs());
+          int numArcs = arc.nodeFlags == ARCS_FOR_DIRECT_ADDRESSING ? getNumArcsDirectAddressing(arc) : arc.numArcs();
+          in.setPosition(arc.posArcsStart() - arc.bytesPerArc() * numArcs);
         }
       }
       arc.target = in.getPosition();
     } else {
       arc.target = readUnpackedNodeTarget(in);
-      if (arc.bytesPerArc() > 0 && arc.arcIdx() == Integer.MIN_VALUE) {
-        // nextArc was pointing to *this* arc when we entered; advance to the next
-        // if it is a missing arc, we will skip it later
-        arc.nextArc = arc.nextArc() - arc.bytesPerArc();
-      } else {
-        // in list and fixed table encodings, the next arc always follows this one
-        arc.nextArc = in.getPosition();
-      }
+      arc.nextArc = in.getPosition(); // Only useful for list.
     }
     return arc;
   }
@@ -1090,12 +1395,14 @@ public final class FST<T> implements Accountable {
       assert cachedArc.bytesPerArc() == result.bytesPerArc();
       assert cachedArc.flags() == result.flags();
       assert cachedArc.label() == result.label();
-      assert (cachedArc.bytesPerArc() != 0 && cachedArc.arcIdx() != Integer.MIN_VALUE) || cachedArc.nextArc() == result.nextArc();
+      assert cachedArc.bytesPerArc() != 0 || cachedArc.nextArc() == result.nextArc();
       assert cachedArc.nextFinalOutput().equals(result.nextFinalOutput());
       assert cachedArc.numArcs() == result.numArcs();
       assert cachedArc.output().equals(result.output());
       assert cachedArc.posArcsStart() == result.posArcsStart();
       assert cachedArc.target() == result.target();
+      assert cachedArc.nodeFlags() == result.nodeFlags();
+      assert cachedArc.nodeFlags() != ARCS_FOR_DIRECT_ADDRESSING || cachedArc.firstLabel() == result.firstLabel();
     }
 
     return true;
@@ -1125,6 +1432,7 @@ public final class FST<T> implements Accountable {
         }
         arc.output = follow.nextFinalOutput();
         arc.label = END_LABEL;
+        arc.nodeFlags = arc.flags;
         return arc;
       } else {
         return null;
@@ -1155,8 +1463,22 @@ public final class FST<T> implements Accountable {
 
     // System.out.println("fta label=" + (char) labelToMatch);
 
-    byte flags = in.readByte();
-    if (flags == ARCS_AS_ARRAY_PACKED) {
+    byte flags = arc.nodeFlags = in.readByte();
+    if (flags == ARCS_FOR_DIRECT_ADDRESSING) {
+      arc.numArcs = in.readVInt(); // This is in fact the label range.
+      arc.bytesPerArc = in.readVInt();
+      readPresenceBytes(arc, in);
+      arc.firstLabel = readLabel(in);
+      arc.posArcsStart = in.getPosition();
+
+      int arcIndex = labelToMatch - arc.firstLabel();
+      if (arcIndex < 0 || arcIndex >= arc.numArcs()) {
+        return null; // Before or after label range.
+      } else if (!arc.bitTable().isBitSet(arcIndex)) {
+        return null; // Arc missing in the range.
+      }
+      return readArcByDirectAddressing(arc, in, arcIndex);
+    } else if (flags == ARCS_FOR_BINARY_SEARCH) {
       arc.numArcs = in.readVInt();
       arc.bytesPerArc = in.readVInt();
       arc.posArcsStart = in.getPosition();
@@ -1230,27 +1552,6 @@ public final class FST<T> implements Accountable {
     }
   }
 
-  /**
-   * Nodes will be expanded if their depth (distance from the root node) is
-   * &lt;= this value and their number of arcs is &gt;=
-   * {@link #FIXED_ARRAY_NUM_ARCS_SHALLOW}.
-   * 
-   * <p>
-   * Fixed array consumes more RAM but enables binary search on the arcs
-   * (instead of a linear scan) on lookup by arc label.
-   * 
-   * @return <code>true</code> if <code>node</code> should be stored in an
-   *         expanded (array) form.
-   * 
-   * @see #FIXED_ARRAY_NUM_ARCS_DEEP
-   * @see Builder.UnCompiledNode#depth
-   */
-  private boolean shouldExpand(Builder<T> builder, Builder.UnCompiledNode<T> node) {
-    return builder.allowArrayArcs &&
-      ((node.depth <= FIXED_ARRAY_SHALLOW_DISTANCE && node.numArcs >= FIXED_ARRAY_NUM_ARCS_SHALLOW) || 
-       node.numArcs >= FIXED_ARRAY_NUM_ARCS_DEEP);
-  }
-  
   /** Returns a {@link BytesReader} for this FST, positioned at
    *  position 0. */
   public BytesReader getBytesReader() {
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java b/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java
index 36d8ddd..fb82194 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/FSTEnum.java
@@ -138,12 +138,13 @@ abstract class FSTEnum<T> {
     while(arc != null) {
       int targetLabel = getTargetLabel();
       //System.out.println("  cycle upto=" + upto + " arc.label=" + arc.label + " (" + (char) arc.label + ") vs targetLabel=" + targetLabel);
-      if (arc.bytesPerArc() != 0 && arc.label() != -1) {
+      if (arc.bytesPerArc() != 0 && arc.label() != FST.END_LABEL) {
         // Arcs are in an array
         final FST.BytesReader in = fst.getBytesReader();
-        if (arc.arcIdx() == Integer.MIN_VALUE) {
-          arc = doSeekCeilArrayWithGaps(arc, targetLabel, in);
+        if (arc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING) {
+          arc = doSeekCeilArrayDirectAddressing(arc, targetLabel, in);
         } else {
+          assert arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH;
           arc = doSeekCeilArrayPacked(arc, targetLabel, in);
         }
       } else {
@@ -152,17 +153,12 @@ abstract class FSTEnum<T> {
     }
   }
 
-  private FST.Arc<T> doSeekCeilArrayWithGaps(final FST.Arc<T> arc, final int targetLabel, final FST.BytesReader in) throws IOException {
-    // The array is addressed directly by label and may contain holes.
+  private FST.Arc<T> doSeekCeilArrayDirectAddressing(final FST.Arc<T> arc, final int targetLabel, final FST.BytesReader in) throws IOException {
+    // The array is addressed directly by label, with presence bits to compute the actual arc offset.
 
-    in.setPosition(arc.posArcsStart());
-    in.skipBytes(1);
-    int firstLabel = fst.readLabel(in);
-    int arcOffset = targetLabel - firstLabel;
-    if (arcOffset >= arc.numArcs()) {
-      // target is beyond the last arc
-      fst.readArcAtPosition(arc, in, arc.posArcsStart() - (arc.numArcs() - 1) * arc.bytesPerArc());
-      assert arc.isLast();
+    int targetIndex = targetLabel - arc.firstLabel();
+    if (targetIndex >= arc.numArcs()) {
+      // Target is beyond the last arc, out of label range.
       // Dead end (target is after the last arc);
       // rollback to last fork then push
       upto--;
@@ -180,17 +176,13 @@ abstract class FSTEnum<T> {
         upto--;
       }
     } else {
-      // TODO: if firstLabel == targetLabel
-      long pos;
-      if (arcOffset >= 0) {
-        pos = arc.posArcsStart() - (arc.bytesPerArc() * arcOffset);
-      } else {
-        pos = arc.posArcsStart();
-      }
-      fst.readArcAtPosition(arc, in, pos);
-      if (arc.label() == targetLabel) {
+      if (targetIndex < 0) {
+        targetIndex = -1;
+      } else if (arc.bitTable().isBitSet(targetIndex)) {
+        fst.readArcByDirectAddressing(arc, in, targetIndex);
+        assert arc.label() == targetLabel;
         // found -- copy pasta from below
-        output[upto] = fst.outputs.add(output[upto-1], arc.output());
+        output[upto] = fst.outputs.add(output[upto - 1], arc.output());
         if (targetLabel == FST.END_LABEL) {
           return null;
         }
@@ -198,7 +190,10 @@ abstract class FSTEnum<T> {
         incr();
         return fst.readFirstTargetArc(arc, getArc(upto), fstReader);
       }
-      // not found, return the next highest
+      // Not found, return the next arc (ceil).
+      int ceilIndex = arc.bitTable().nextBitSet(targetIndex);
+      assert ceilIndex != -1;
+      fst.readArcByDirectAddressing(arc, in, ceilIndex);
       assert arc.label() > targetLabel;
       pushFirst();
       return null;
@@ -319,9 +314,10 @@ abstract class FSTEnum<T> {
       if (arc.bytesPerArc() != 0 && arc.label() != FST.END_LABEL) {
         // Arcs are in an array
         final FST.BytesReader in = fst.getBytesReader();
-        if (arc.arcIdx() == Integer.MIN_VALUE) {
-          arc = doSeekFloorArrayWithGaps(arc, targetLabel, in);
+        if (arc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING) {
+          arc = doSeekFloorArrayDirectAddressing(arc, targetLabel, in);
         } else {
+          assert arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH;
           arc = doSeekFloorArrayPacked(arc, targetLabel, in);
         }
       } else {
@@ -330,46 +326,25 @@ abstract class FSTEnum<T> {
     }
   }
 
-  private FST.Arc<T> doSeekFloorArrayWithGaps(FST.Arc<T> arc, int targetLabel, final FST.BytesReader in) throws IOException {
-    // The array is addressed directly by label and may contain holes.
-    in.setPosition(arc.posArcsStart());
-    in.skipBytes(1);
-    int firstLabel = fst.readLabel(in);
-    int targetOffset = targetLabel - firstLabel;
-    if (targetOffset < 0) {
-      //System.out.println(" before first"); Very first arc is after our target TODO: if each
-      // arc could somehow read the arc just before, we can save this re-scan.  The ceil case
-      // doesn't need this because it reads the next arc instead:
-      while(true) {
-        // First, walk backwards until we find a first arc
-        // that's before our target label:
-        fst.readFirstTargetArc(getArc(upto-1), arc, fstReader);
-        if (arc.label() < targetLabel) {
-          // Then, scan forwards to the arc just before
-          // the targetLabel:
-          while(!arc.isLast() && fst.readNextArcLabel(arc, in) < targetLabel) {
-            fst.readNextArc(arc, fstReader);
-          }
-          pushLast();
-          return null;
-        }
-        upto--;
-        if (upto == 0) {
-          return null;
-        }
-        targetLabel = getTargetLabel();
-        arc = getArc(upto);
-      }
+  private FST.Arc<T> doSeekFloorArrayDirectAddressing(FST.Arc<T> arc, int targetLabel, FST.BytesReader in) throws IOException {
+    // The array is addressed directly by label, with presence bits to compute the actual arc offset.
+
+    int targetIndex = targetLabel - arc.firstLabel();
+    if (targetIndex < 0) {
+      // Before first arc.
+      return backtrackToFloorArc(arc, targetLabel, in);
+   } else if (targetIndex >= arc.numArcs()) {
+      // After last arc.
+      fst.readArcByDirectAddressing(arc, in, arc.numArcs() - 1);
+      assert arc.label() < targetLabel;
+      assert arc.isLast();
+      pushLast();
+      return null;
     } else {
-      if (targetOffset >= arc.numArcs()) {
-        fst.readArcAtPosition(arc, in, arc.posArcsStart() - arc.bytesPerArc() * (arc.numArcs() - 1));
-        assert arc.isLast();
-        assert arc.label() < targetLabel: "arc.label=" + arc.label() + " vs targetLabel=" + targetLabel;
-        pushLast();
-        return null;
-      }
-      fst.readArcAtPosition(arc, in, arc.posArcsStart() - arc.bytesPerArc() * targetOffset);
-      if (arc.label() == targetLabel) {
+      // Within label range.
+      if (arc.bitTable().isBitSet(targetIndex)) {
+        fst.readArcByDirectAddressing(arc, in, targetIndex);
+        assert arc.label() == targetLabel;
         // found -- copy pasta from below
         output[upto] = fst.outputs.add(output[upto-1], arc.output());
         if (targetLabel == FST.END_LABEL) {
@@ -379,18 +354,99 @@ abstract class FSTEnum<T> {
         incr();
         return fst.readFirstTargetArc(arc, getArc(upto), fstReader);
       }
-      // Scan backwards to find a floor arc that is not missing
-      for (long arcOffset = arc.posArcsStart() - targetOffset * arc.bytesPerArc(); arcOffset <= arc.posArcsStart(); arcOffset += arc.bytesPerArc()) {
-        // TODO: we can do better here by skipping missing arcs
-        fst.readArcAtPosition(arc, in, arcOffset);
-        if (arc.label() < targetLabel) {
-          assert arc.isLast() || fst.readNextArcLabel(arc, in) > targetLabel;
-          pushLast();
-          return null;
+      // Scan backwards to find a floor arc.
+      int floorIndex = arc.bitTable().previousBitSet(targetIndex);
+      assert floorIndex != -1;
+      fst.readArcByDirectAddressing(arc, in, floorIndex);
+      assert arc.label() < targetLabel;
+      assert arc.isLast() || fst.readNextArcLabel(arc, in) > targetLabel;
+      pushLast();
+      return null;
+    }
+  }
+
+  /**
+   * Backtracks until it finds a node which first arc is before our target label.`
+   * Then on the node, finds the arc just before the targetLabel.
+   *
+   * @return null to continue the seek floor recursion loop.
+   */
+  private FST.Arc<T> backtrackToFloorArc(FST.Arc<T> arc, int targetLabel, final FST.BytesReader in) throws IOException {
+    while (true) {
+      // First, walk backwards until we find a node which first arc is before our target label.
+      fst.readFirstTargetArc(getArc(upto-1), arc, fstReader);
+      if (arc.label() < targetLabel) {
+        // Then on this node, find the arc just before the targetLabel.
+        if (!arc.isLast()) {
+          if (arc.bytesPerArc() != 0 && arc.label() != FST.END_LABEL) {
+            if (arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
+              findNextFloorArcBinarySearch(arc, targetLabel, in);
+            } else {
+              assert arc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING;
+              findNextFloorArcDirectAddressing(arc, targetLabel, in);
+            }
+          } else {
+            while (!arc.isLast() && fst.readNextArcLabel(arc, in) < targetLabel) {
+              fst.readNextArc(arc, fstReader);
+            }
+          }
+        }
+        assert arc.label() < targetLabel;
+        assert arc.isLast() || fst.readNextArcLabel(arc, in) >= targetLabel;
+        pushLast();
+        return null;
+      }
+      upto--;
+      if (upto == 0) {
+        return null;
+      }
+      targetLabel = getTargetLabel();
+      arc = getArc(upto);
+    }
+  }
+
+  /**
+   * Finds and reads an arc on the current node which label is strictly less than the given label.
+   * Skips the first arc, finds next floor arc; or none if the floor arc is the first
+   * arc itself (in this case it has already been read).
+   * <p>
+   * Precondition: the given arc is the first arc of the node.
+   */
+  private void findNextFloorArcDirectAddressing(FST.Arc<T> arc, int targetLabel, final FST.BytesReader in) throws IOException {
+    assert arc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING;
+    assert arc.label() != FST.END_LABEL;
+    assert arc.label() == arc.firstLabel();
+    if (arc.numArcs() > 1) {
+      int targetIndex = targetLabel - arc.firstLabel();
+      assert targetIndex >= 0;
+      if (targetIndex >= arc.numArcs()) {
+        // Beyond last arc. Take last arc.
+        fst.readArcByDirectAddressing(arc, in, arc.numArcs() - 1);
+      } else {
+        // Take the preceding arc, even if the target is present.
+        int floorIndex = arc.bitTable().previousBitSet(targetIndex);
+        if (floorIndex > 0) {
+          fst.readArcByDirectAddressing(arc, in, floorIndex);
         }
       }
-      assert false: "arc.label=" + arc.label() + " vs targetLabel=" + targetLabel;
-      return arc;               // unreachable
+    }
+  }
+
+  /**
+   * Same as {@link #findNextFloorArcDirectAddressing} for binary search node.
+   */
+  private void findNextFloorArcBinarySearch(FST.Arc<T> arc, int targetLabel, FST.BytesReader in) throws IOException {
+    assert arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH;
+    assert arc.label() != FST.END_LABEL;
+    assert arc.arcIdx() == 0;
+    if (arc.numArcs() > 1) {
+      int idx = Util.binarySearch(fst, arc, targetLabel);
+      assert idx != -1;
+      if (idx > 1) {
+        fst.readArcByIndex(arc, in, idx - 1);
+      } else if (idx < -2) {
+        fst.readArcByIndex(arc, in, -2 - idx);
+      }
     }
   }
 
@@ -412,34 +468,10 @@ abstract class FSTEnum<T> {
       incr();
       return fst.readFirstTargetArc(arc, getArc(upto), fstReader);
     } else if (idx == -1) {
-      //System.out.println("  before first");
-      // Very first arc is after our target
-      // TODO: if each arc could somehow read the arc just
-      // before, we can save this re-scan.  The ceil case
-      // doesn't need this because it reads the next arc
-      // instead:
-      while(true) {
-        // First, walk backwards until we find a first arc
-        // that's before our target label:
-        fst.readFirstTargetArc(getArc(upto-1), arc, fstReader);
-        if (arc.label() < targetLabel) {
-          // Then, scan forwards to the arc just before
-          // the targetLabel:
-          while(!arc.isLast() && fst.readNextArcLabel(arc, in) < targetLabel) {
-            fst.readNextArc(arc, fstReader);
-          }
-          pushLast();
-          return null;
-        }
-        upto--;
-        if (upto == 0) {
-          return null;
-        }
-        targetLabel = getTargetLabel();
-        arc = getArc(upto);
-      }
+      // Before first arc.
+      return backtrackToFloorArc(arc, targetLabel, in);
     } else {
-      // There is a floor arc; idx will be {@code -1 - (floor + 1)}.
+      // There is a floor arc; idx will be (-1 - (floor + 1)).
       fst.readArcByIndex(arc, in, -2 - idx);
       assert arc.isLast() || fst.readNextArcLabel(arc, in) > targetLabel;
       assert arc.label() < targetLabel: "arc.label=" + arc.label() + " vs targetLabel=" + targetLabel;
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java b/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java
index 8530ccb..af152fe 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/NodeHash.java
@@ -41,9 +41,22 @@ final class NodeHash<T> {
 
   private boolean nodesEqual(Builder.UnCompiledNode<T> node, long address) throws IOException {
     fst.readFirstRealTargetArc(address, scratchArc, in);
-    if (scratchArc.isPackedArray() && node.numArcs != scratchArc.numArcs()) {
-      return false;
+
+    // Fail fast for a node with fixed length arcs.
+    if (scratchArc.bytesPerArc() != 0) {
+      if (scratchArc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
+        if (node.numArcs != scratchArc.numArcs()) {
+          return false;
+        }
+      } else {
+        assert scratchArc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING;
+        if ((node.arcs[node.numArcs - 1].label - node.arcs[0].label + 1) != scratchArc.numArcs()
+            || node.numArcs != scratchArc.bitTable().countBits()) {
+          return false;
+        }
+      }
     }
+
     for(int arcUpto=0; arcUpto < node.numArcs; arcUpto++) {
       final Builder.Arc<T> arc = node.arcs[arcUpto];
       if (arc.label != scratchArc.label() ||
diff --git a/lucene/core/src/java/org/apache/lucene/util/fst/Util.java b/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
index ddecade..5f822c4 100644
--- a/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
+++ b/lucene/core/src/java/org/apache/lucene/util/fst/Util.java
@@ -151,7 +151,7 @@ public final class Util {
         
         fst.readFirstRealTargetArc(arc.target(), arc, in);
 
-        if (arc.bytesPerArc() != 0 && arc.arcIdx() > Integer.MIN_VALUE) {
+        if (arc.bytesPerArc() != 0 && arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH) {
 
           int low = 0;
           int high = arc.numArcs() -1;
@@ -940,18 +940,27 @@ public final class Util {
     }
     fst.readFirstTargetArc(follow, arc, in);
     if (arc.bytesPerArc() != 0 && arc.label() != FST.END_LABEL) {
-      if (arc.arcIdx() == Integer.MIN_VALUE) {
-        // Arcs are in an array-with-gaps
-        int offset = label - arc.label();
-        if (offset >= arc.numArcs()) {
+      if (arc.nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING) {
+        // Fixed length arcs in a direct addressing node.
+        int targetIndex = label - arc.label();
+        if (targetIndex >= arc.numArcs()) {
           return null;
-        } else if (offset < 0) {
+        } else if (targetIndex < 0) {
           return arc;
         } else {
-          return fst.readArcAtPosition(arc, in, arc.posArcsStart() - offset * arc.bytesPerArc());
+          if (arc.bitTable().isBitSet(targetIndex)) {
+            fst.readArcByDirectAddressing(arc, in, targetIndex);
+            assert arc.label() == label;
+          } else {
+            int ceilIndex = arc.bitTable().nextBitSet(targetIndex);
+            assert ceilIndex != -1;
+            fst.readArcByDirectAddressing(arc, in, ceilIndex);
+            assert arc.label() > label;
+          }
+          return arc;
         }
       }
-      // Arcs are packed array -- use binary search to find the target.
+      // Fixed length arcs in a binary search node.
       int idx = binarySearch(fst, arc, label);
       if (idx >= 0) {
         return fst.readArcByIndex(arc, in, idx);
@@ -964,7 +973,8 @@ public final class Util {
       return fst.readArcByIndex(arc, in , idx);
     }
 
-    // Linear scan
+    // Variable length arcs in a linear scan list,
+    // or special arc with label == FST.END_LABEL.
     fst.readFirstRealTargetArc(follow.target(), arc, in);
 
     while (true) {
@@ -995,6 +1005,7 @@ public final class Util {
    * @throws IOException when the FST reader does
    */
   static <T> int binarySearch(FST<T> fst, FST.Arc<T> arc, int targetLabel) throws IOException {
+    assert arc.nodeFlags() == FST.ARCS_FOR_BINARY_SEARCH : "Arc is not encoded as packed array for binary search (nodeFlags=" + arc.nodeFlags() + ")";
     BytesReader in = fst.getBytesReader();
     int low = arc.arcIdx();
     int mid = 0;
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestBitUtil.java b/lucene/core/src/test/org/apache/lucene/util/TestBitUtil.java
new file mode 100644
index 0000000..84a7b75
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/util/TestBitUtil.java
@@ -0,0 +1,85 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.util;
+
+public class TestBitUtil extends LuceneTestCase {
+
+  public void testNextBitSet() {
+    for (int i = 0; i < 10000; i++) {
+      long[] bits = buildRandomBits();
+      int numLong = bits.length - 1;
+
+      // Verify nextBitSet with countBitsUpTo for all bit indexes.
+      for (int bitIndex = -1; bitIndex < 64 * numLong; bitIndex++) {
+        int nextIndex = BitUtil.nextBitSet(bits, numLong, bitIndex);
+        if (nextIndex == -1) {
+          assertEquals("No next bit set, so expected no bit count diff"
+                  + " (i=" + i + " bitIndex=" + bitIndex + ")",
+              BitUtil.countBitsUpTo(bits, numLong, bitIndex + 1), BitUtil.countBits(bits, numLong));
+        } else {
+          assertTrue("Expected next bit set at nextIndex=" + nextIndex
+                  + " (i=" + i + " bitIndex=" + bitIndex + ")",
+              BitUtil.isBitSet(bits, numLong, nextIndex));
+          assertEquals("Next bit set at nextIndex=" + nextIndex
+                  + " so expected bit count diff of 1"
+                  + " (i=" + i + " bitIndex=" + bitIndex + ")",
+              BitUtil.countBitsUpTo(bits, numLong, bitIndex + 1) + 1,
+              BitUtil.countBitsUpTo(bits, numLong, nextIndex + 1));
+        }
+      }
+    }
+  }
+
+  public void testPreviousBitSet() {
+    for (int i = 0; i < 10000; i++) {
+      long[] bits = buildRandomBits();
+      int numLong = bits.length - 1;
+
+      // Verify previousBitSet with countBitsUpTo for all bit indexes.
+      for (int bitIndex = 0; bitIndex <= 64 * numLong; bitIndex++) {
+        int previousIndex = BitUtil.previousBitSet(bits, numLong, bitIndex);
+        if (previousIndex == -1) {
+          assertEquals("No previous bit set, so expected bit count 0"
+                  + " (i=" + i + " bitIndex=" + bitIndex + ")",
+              0, BitUtil.countBitsUpTo(bits, numLong, bitIndex));
+        } else {
+          assertTrue("Expected previous bit set at previousIndex=" + previousIndex
+                  + " (i=" + i + " bitIndex=" + bitIndex + ")",
+              BitUtil.isBitSet(bits, numLong, previousIndex));
+          int bitCount = BitUtil.countBitsUpTo(bits, numLong, Math.min(bitIndex + 1, numLong * Long.SIZE));
+          int expectedPreviousBitCount = bitIndex < numLong * Long.SIZE && BitUtil.isBitSet(bits, numLong, bitIndex) ?
+              bitCount - 1 : bitCount;
+          assertEquals("Previous bit set at previousIndex=" + previousIndex
+                  + " with current bitCount=" + bitCount
+                  + " so expected previousBitCount=" + expectedPreviousBitCount
+                  + " (i=" + i + " bitIndex=" + bitIndex + ")",
+              expectedPreviousBitCount, BitUtil.countBitsUpTo(bits, numLong, previousIndex + 1));
+        }
+      }
+    }
+  }
+
+  private long[] buildRandomBits() {
+    long[] bits = new long[random().nextInt(3) + 2];
+    for (int j = 0; j < bits.length; j++) {
+      // Bias towards zeros which require special logic.
+      bits[j] = random().nextInt(4) == 0 ? 0L : random().nextLong();
+    }
+    return bits;
+  }
+}
diff --git a/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java b/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
index 8f598f6..316cbdf 100644
--- a/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
+++ b/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
@@ -303,7 +303,7 @@ public class TestFSTs extends LuceneTestCase {
   public void testBigSet() throws IOException {
     testRandomWords(TestUtil.nextInt(random(), 50000, 60000), 1);
   }
-  
+
   // Build FST for all unique terms in the test line docs
   // file, up until a doc limit
   public void testRealTerms() throws Exception {
@@ -1078,10 +1078,10 @@ public class TestFSTs extends LuceneTestCase {
             int children = verifyStateAndBelow(fst, new FST.Arc<>().copyFrom(arc), depth + 1);
 
             assertEquals(
-                expanded,
-                (depth <= FST.FIXED_ARRAY_SHALLOW_DISTANCE &&
-                    children >= FST.FIXED_ARRAY_NUM_ARCS_SHALLOW) ||
-                 children >= FST.FIXED_ARRAY_NUM_ARCS_DEEP);
+                (depth <= FST.FIXED_LENGTH_ARC_SHALLOW_DEPTH &&
+                    children >= FST.FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS) ||
+                 children >= FST.FIXED_LENGTH_ARC_DEEP_NUM_ARCS,
+                expanded);
             if (arc.isLast()) break;
           }
 
@@ -1092,8 +1092,8 @@ public class TestFSTs extends LuceneTestCase {
     }
 
     // Sanity check.
-    assertTrue(FST.FIXED_ARRAY_NUM_ARCS_SHALLOW < FST.FIXED_ARRAY_NUM_ARCS_DEEP);
-    assertTrue(FST.FIXED_ARRAY_SHALLOW_DISTANCE >= 0);
+    assertTrue(FST.FIXED_LENGTH_ARC_SHALLOW_NUM_ARCS < FST.FIXED_LENGTH_ARC_DEEP_NUM_ARCS);
+    assertTrue(FST.FIXED_LENGTH_ARC_SHALLOW_DEPTH >= 0);
 
     SyntheticData s = new SyntheticData();
 
@@ -1635,4 +1635,23 @@ public class TestFSTs extends LuceneTestCase {
       // expected
     }
   }
+
+  public void testSimpleDepth() throws Exception {
+    PositiveIntOutputs outputs = PositiveIntOutputs.getSingleton();
+    Builder<Long> builder = new Builder<>(FST.INPUT_TYPE.BYTE1, outputs);
+
+    BytesRef ab = new BytesRef("ab");
+    BytesRef ac = new BytesRef("ac");
+    BytesRef bd = new BytesRef("bd");
+
+    builder.add(Util.toIntsRef(ab, new IntsRefBuilder()), 3L);
+    builder.add(Util.toIntsRef(ac, new IntsRefBuilder()), 5L);
+    builder.add(Util.toIntsRef(bd, new IntsRefBuilder()), 7L);
+
+    FST<Long> fst = builder.finish();
+
+    assertEquals(3, (long) Util.get(fst, ab));
+    assertEquals(5, (long) Util.get(fst, ac));
+    assertEquals(7, (long) Util.get(fst, bd));
+  }
 }
diff --git a/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirect.java b/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirect.java
deleted file mode 100644
index af9f933..0000000
--- a/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirect.java
+++ /dev/null
@@ -1,106 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You under the Apache License, Version 2.0
- * (the "License"); you may not use this file except in compliance with
- * the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.lucene.util.fst;
-
-import java.nio.file.Files;
-import java.nio.file.Paths;
-import java.util.ArrayList;
-import java.util.Arrays;
-import java.util.List;
-import java.util.Locale;
-
-import org.apache.lucene.store.ByteArrayDataInput;
-import org.apache.lucene.store.DataInput;
-import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.IntsRefBuilder;
-import org.apache.lucene.util.LuceneTestCase;
-
-
-public class TestFstDirect extends LuceneTestCase {
-
-  public void testDenseWithGap() throws Exception {
-    List<String> words = Arrays.asList("ah", "bi", "cj", "dk", "fl", "gm");
-    List<BytesRef> entries = new ArrayList<>();
-    for (String word : words) {
-      entries.add(new BytesRef(word.getBytes("ascii")));
-    }
-    final BytesRefFSTEnum<Object> fstEnum = new BytesRefFSTEnum<>(buildFST(entries));
-    for (BytesRef entry : entries) {
-      assertNotNull(entry.utf8ToString() + " not found", fstEnum.seekExact(entry));
-    }
-  }
-
-  public void testDeDupTails() throws Exception {
-    List<BytesRef> entries = new ArrayList<>();
-    for (int i = 0; i < 1000000; i += 4) {
-      byte[] b = new byte[3];
-      int val = i;
-      for (int j = b.length - 1; j >= 0; --j) {
-        b[j] = (byte) (val & 0xff);
-        val >>= 8;
-      }
-      entries.add(new BytesRef(b));
-    }
-    long size = buildFST(entries).ramBytesUsed();
-    // Size is 1664 when we use only list-encoding.  We were previously failing to ever de-dup
-    // arrays-with-gaps, which led this case to blow up.
-    assertTrue(size < 3000);
-    //printf("fst size = %d bytes", size);
-  }
-
-  private FST<Object> buildFST(List<BytesRef> entries) throws Exception {
-    final Outputs<Object> outputs = NoOutputs.getSingleton();
-    final Builder<Object> b = new Builder<>(FST.INPUT_TYPE.BYTE1, 0, 0, true, true, Integer.MAX_VALUE, outputs, true, 15);
-    BytesRef last = null;
-    for (BytesRef entry : entries) {
-      if (entry.equals(last) == false) {
-        b.add(Util.toIntsRef(entry, new IntsRefBuilder()), outputs.getNoOutput());
-      }
-      last = entry;
-    }
-    FST<Object> fst = b.finish();
-    return fst;
-  }
-
-  private static void printf(String format, Object ... values) {
-    System.out.println(String.format(Locale.ROOT, format, values));
-  }
-
-  private static long nsToMs(long ns) {
-    return ns / 1_000_000;
-  }
-
-  public static void main(String... args) throws Exception {
-    byte[] buf = Files.readAllBytes(Paths.get(args[0]));
-    DataInput in = new ByteArrayDataInput(buf);
-    FST<BytesRef> fst = new FST<>(in, ByteSequenceOutputs.getSingleton());
-    BytesRefFSTEnum<BytesRef> fstEnum = new BytesRefFSTEnum<>(fst);
-    int sparseArrayArcCount = 0, directArrayArcCount = 0, listArcCount = 0;
-    while(fstEnum.next() != null) {
-      if (fstEnum.arcs[fstEnum.upto].bytesPerArc() == 0) {
-        listArcCount ++;
-      } else if (fstEnum.arcs[fstEnum.upto].arcIdx() == Integer.MIN_VALUE) {
-        directArrayArcCount ++;
-      } else {
-        sparseArrayArcCount ++;
-      }
-    }
-    System.out.println("direct arcs = " + directArrayArcCount + ", sparse arcs = " + sparseArrayArcCount +
-                       " list arcs = " + listArcCount);
-  }
-
-}
diff --git a/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirectAddressing.java b/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirectAddressing.java
new file mode 100644
index 0000000..f69f813
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/util/fst/TestFstDirectAddressing.java
@@ -0,0 +1,212 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.util.fst;
+
+import java.io.BufferedReader;
+import java.io.IOException;
+import java.nio.charset.StandardCharsets;
+import java.nio.file.Files;
+import java.nio.file.Paths;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Locale;
+import java.util.Set;
+
+import org.apache.lucene.store.ByteArrayDataInput;
+import org.apache.lucene.store.DataInput;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.IntsRefBuilder;
+import org.apache.lucene.util.LuceneTestCase;
+
+public class TestFstDirectAddressing extends LuceneTestCase {
+
+  public void testDenseWithGap() throws Exception {
+    List<String> words = Arrays.asList("ah", "bi", "cj", "dk", "fl", "gm");
+    List<BytesRef> entries = new ArrayList<>();
+    for (String word : words) {
+      entries.add(new BytesRef(word.getBytes(StandardCharsets.US_ASCII)));
+    }
+    final BytesRefFSTEnum<Object> fstEnum = new BytesRefFSTEnum<>(buildFST(entries));
+    for (BytesRef entry : entries) {
+      assertNotNull(entry.utf8ToString() + " not found", fstEnum.seekExact(entry));
+    }
+  }
+
+  public void testDeDupTails() throws Exception {
+    List<BytesRef> entries = new ArrayList<>();
+    for (int i = 0; i < 1000000; i += 4) {
+      byte[] b = new byte[3];
+      int val = i;
+      for (int j = b.length - 1; j >= 0; --j) {
+        b[j] = (byte) (val & 0xff);
+        val >>= 8;
+      }
+      entries.add(new BytesRef(b));
+    }
+    long size = buildFST(entries).ramBytesUsed();
+    // Size is 1648 when we use only list-encoding. We were previously failing to ever de-dup
+    // direct addressing, which led this case to blow up.
+    assertTrue(size <= 1080);
+    //printf("fst size = %d bytes", size);
+  }
+
+  public void testWorstCaseForDirectAddressing() throws Exception {
+    // This test will fail if there is more than 1% memory increase with direct addressing in this worst case.
+    final double MEMORY_INCREASE_LIMIT_PERCENT = 1d;
+    final int NUM_WORDS = 1000000;
+
+    // Generate words with specially crafted bytes.
+    Set<BytesRef> wordSet = new HashSet<>();
+    for (int i = 0; i < NUM_WORDS; ++i) {
+      byte[] b = new byte[5];
+      random().nextBytes(b);
+      for (int j = 0; j < b.length; ++j) {
+        b[j] &= 0xfc; // Make this byte a multiple of 4.
+      }
+      wordSet.add(new BytesRef(b));
+    }
+    List<BytesRef> wordList = new ArrayList<>(wordSet);
+    Collections.sort(wordList);
+
+    // Disable direct addressing and measure the FST size.
+    Builder<Object> builder = createBuilder(-1f);
+    FST<Object> fst = buildFST(wordList, builder);
+    long ramBytesUsedNoDirectAddressing = fst.ramBytesUsed();
+
+    // Enable direct addressing and measure the FST size.
+    builder = createBuilder(Builder.DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR);
+    fst = buildFST(wordList, builder);
+    long ramBytesUsed = fst.ramBytesUsed();
+
+    // Compute the size increase in percents.
+    double directAddressingMemoryIncreasePercent = ((double) ramBytesUsed / ramBytesUsedNoDirectAddressing - 1) * 100;
+
+//    printStats(builder, ramBytesUsed, directAddressingMemoryIncreasePercent);
+
+    // Verify the FST size does not exceed the limit.
+    assertTrue("FST size exceeds limit, size = " + ramBytesUsed
+            + ", increase = " + directAddressingMemoryIncreasePercent + " %"
+            + ", limit = " + MEMORY_INCREASE_LIMIT_PERCENT + " %",
+        directAddressingMemoryIncreasePercent < MEMORY_INCREASE_LIMIT_PERCENT);
+  }
+
+  private static void printStats(Builder<Object> builder, long ramBytesUsed, double directAddressingMemoryIncreasePercent) {
+    System.out.println("directAddressingMaxOversizingFactor = " + builder.getDirectAddressingMaxOversizingFactor());
+    System.out.println("ramBytesUsed = "
+        + String.format(Locale.ENGLISH, "%.2f MB", ramBytesUsed / 1024d / 1024d)
+        + String.format(Locale.ENGLISH, " (%.2f %% increase with direct addressing)", directAddressingMemoryIncreasePercent));
+    System.out.println("num nodes = " + builder.nodeCount);
+    long fixedLengthArcNodeCount = builder.directAddressingNodeCount + builder.binarySearchNodeCount;
+    System.out.println("num fixed-length-arc nodes = " + fixedLengthArcNodeCount
+        + String.format(Locale.ENGLISH, " (%.2f %% of all nodes)",
+        ((double) fixedLengthArcNodeCount / builder.nodeCount * 100)));
+    System.out.println("num binary-search nodes = " + (builder.binarySearchNodeCount)
+        + String.format(Locale.ENGLISH, " (%.2f %% of fixed-length-arc nodes)",
+        ((double) (builder.binarySearchNodeCount) / fixedLengthArcNodeCount * 100)));
+    System.out.println("num direct-addressing nodes = " + (builder.directAddressingNodeCount)
+        + String.format(Locale.ENGLISH, " (%.2f %% of fixed-length-arc nodes)",
+        ((double) (builder.directAddressingNodeCount) / fixedLengthArcNodeCount * 100)));
+  }
+
+  private static Builder<Object> createBuilder(float directAddressingMaxOversizingFactor) {
+    return new Builder<>(FST.INPUT_TYPE.BYTE1, 0, 0, true, true, Integer.MAX_VALUE, NoOutputs.getSingleton(), true, 15)
+        .setDirectAddressingMaxOversizingFactor(directAddressingMaxOversizingFactor);
+  }
+
+  private FST<Object> buildFST(List<BytesRef> entries) throws Exception {
+    return buildFST(entries, createBuilder(Builder.DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR));
+  }
+
+  private static FST<Object> buildFST(List<BytesRef> entries, Builder<Object> builder) throws Exception {
+    BytesRef last = null;
+    for (BytesRef entry : entries) {
+      if (entry.equals(last) == false) {
+        builder.add(Util.toIntsRef(entry, new IntsRefBuilder()), NoOutputs.getSingleton().getNoOutput());
+      }
+      last = entry;
+    }
+    return builder.finish();
+  }
+
+  public static void main(String... args) throws Exception {
+    if (args.length < 2) {
+      throw new IllegalArgumentException("Missing argument");
+    }
+    if (args[0].equals("-countFSTArcs")) {
+      countFSTArcs(args[1]);
+    } else if (args[0].equals("-measureFSTOversizing")) {
+      measureFSTOversizing(args[1]);
+    } else {
+      throw new IllegalArgumentException("Invalid argument " + args[0]);
+    }
+  }
+
+  private static void countFSTArcs(String FSTFilePath) throws IOException {
+    byte[] buf = Files.readAllBytes(Paths.get(FSTFilePath));
+    DataInput in = new ByteArrayDataInput(buf);
+    FST<BytesRef> fst = new FST<>(in, ByteSequenceOutputs.getSingleton());
+    BytesRefFSTEnum<BytesRef> fstEnum = new BytesRefFSTEnum<>(fst);
+    int binarySearchArcCount = 0, directAddressingArcCount = 0, listArcCount = 0;
+    while(fstEnum.next() != null) {
+      if (fstEnum.arcs[fstEnum.upto].bytesPerArc() == 0) {
+        listArcCount ++;
+      } else if (fstEnum.arcs[fstEnum.upto].nodeFlags() == FST.ARCS_FOR_DIRECT_ADDRESSING) {
+        directAddressingArcCount ++;
+      } else {
+        binarySearchArcCount ++;
+      }
+    }
+    System.out.println("direct addressing arcs = " + directAddressingArcCount
+        + ", binary search arcs = " + binarySearchArcCount
+        + " list arcs = " + listArcCount);
+  }
+
+  private static void measureFSTOversizing(String wordsFilePath) throws Exception {
+    final int MAX_NUM_WORDS = 1000000;
+
+    // Read real english words.
+    List<BytesRef> wordList = new ArrayList<>();
+    try (BufferedReader reader = Files.newBufferedReader(Paths.get(wordsFilePath))) {
+      while (wordList.size() < MAX_NUM_WORDS) {
+        String word = reader.readLine();
+        if (word == null) {
+          break;
+        }
+        wordList.add(new BytesRef(word));
+      }
+    }
+    Collections.sort(wordList);
+
+    // Disable direct addressing and measure the FST size.
+    Builder<Object> builder = createBuilder(-1f);
+    FST<Object> fst = buildFST(wordList, builder);
+    long ramBytesUsedNoDirectAddressing = fst.ramBytesUsed();
+
+    // Enable direct addressing and measure the FST size.
+    builder = createBuilder(Builder.DIRECT_ADDRESSING_MAX_OVERSIZING_FACTOR);
+    fst = buildFST(wordList, builder);
+    long ramBytesUsed = fst.ramBytesUsed();
+
+    // Compute the size increase in percents.
+    double directAddressingMemoryIncreasePercent = ((double) ramBytesUsed / ramBytesUsedNoDirectAddressing - 1) * 100;
+
+    printStats(builder, ramBytesUsed, directAddressingMemoryIncreasePercent);
+  }
+}
diff --git a/lucene/core/src/test/org/apache/lucene/util/fst/TestUtil.java b/lucene/core/src/test/org/apache/lucene/util/fst/TestUtil.java
index 5ec163e..2793e7e 100644
--- a/lucene/core/src/test/org/apache/lucene/util/fst/TestUtil.java
+++ b/lucene/core/src/test/org/apache/lucene/util/fst/TestUtil.java
@@ -27,10 +27,10 @@ import org.apache.lucene.util.LuceneTestCase;
 public class TestUtil extends LuceneTestCase {
 
   public void testBinarySearch() throws Exception {
-    // Creates a node with 8 arcs spanning (z-A) = 57 chars that will be encoded as a sparse array (no gaps)
-    // requiring binary search
+    // Create a node with 8 arcs spanning (z-A) and ensure it is encoded as a packed array
+    // requiring binary search.
     List<String> letters = Arrays.asList("A", "E", "J", "K", "L", "O", "T", "z");
-    FST<Object> fst = buildFST(letters, true);
+    FST<Object> fst = buildFST(letters, true, false);
     FST.Arc<Object> arc = fst.getFirstArc(new FST.Arc<>());
     arc = fst.readFirstTargetArc(arc, arc, fst.getBytesReader());
     for (int i = 0; i < letters.size(); i++) {
@@ -47,21 +47,21 @@ public class TestUtil extends LuceneTestCase {
 
   public void testReadCeilArcPackedArray() throws Exception {
     List<String> letters = Arrays.asList("A", "E", "J", "K", "L", "O", "T", "z");
-    verifyReadCeilArc(letters, true);
+    verifyReadCeilArc(letters, true, false);
   }
 
   public void testReadCeilArcArrayWithGaps() throws Exception {
     List<String> letters = Arrays.asList("A", "E", "J", "K", "L", "O", "T");
-    verifyReadCeilArc(letters, true);
+    verifyReadCeilArc(letters, true, true);
   }
 
   public void testReadCeilArcList() throws Exception {
     List<String> letters = Arrays.asList("A", "E", "J", "K", "L", "O", "T", "z");
-    verifyReadCeilArc(letters, false);
+    verifyReadCeilArc(letters, false, false);
   }
 
-  private void verifyReadCeilArc(List<String> letters, boolean allowArrayArcs) throws Exception {
-    FST<Object> fst = buildFST(letters, allowArrayArcs);
+  private void verifyReadCeilArc(List<String> letters, boolean allowArrayArcs, boolean allowDirectAddressing) throws Exception {
+    FST<Object> fst = buildFST(letters, allowArrayArcs, allowDirectAddressing);
     FST.Arc<Object> first = fst.getFirstArc(new FST.Arc<>());
     FST.Arc<Object> arc = new FST.Arc<>();
     FST.BytesReader in = fst.getBytesReader();
@@ -81,9 +81,12 @@ public class TestUtil extends LuceneTestCase {
     assertNull(Util.readCeilArc('Z', fst, arc, arc, in));
   }
 
-  private FST<Object> buildFST(List<String> words, boolean allowArrayArcs) throws Exception {
+  private FST<Object> buildFST(List<String> words, boolean allowArrayArcs, boolean allowDirectAddressing) throws Exception {
     final Outputs<Object> outputs = NoOutputs.getSingleton();
     final Builder<Object> b = new Builder<>(FST.INPUT_TYPE.BYTE1, 0, 0, true, true, Integer.MAX_VALUE, outputs, allowArrayArcs, 15);
+    if (!allowDirectAddressing) {
+      b.setDirectAddressingMaxOversizingFactor(-1f);
+    }
 
     for (String word : words) {
       b.add(Util.toIntsRef(new BytesRef(word), new IntsRefBuilder()), outputs.getNoOutput());