Hyphenopoly

If your codebase cannot handle asynchronous code, you can enable synchronous mode by setting "sync": true in the configuration object.

When sync is true:

1. hyphenopoly.config() returns a Map of hyphenator functions directly (instead of a Map of Promises).
2. You must provide a loaderSync function instead of a loader function.
3. Note that loaderSync cannot use inherently asynchronous methods like fetch or https.

import hyphenopoly from "hyphenopoly";
import {readFileSync} from "node:fs";

function loaderSync(file, patDir) {
    return readFileSync(new URL(file, patDir));
}

const hyphenator = hyphenopoly.config({
    "exceptions": {
        "en-us": "en-han-ces"
    },
    "hyphen": "•",
    loaderSync,
    "require": ["de", "en-us"],
    "sync": true
});

// hyphenator is a Map of functions
const hy1 = hyphenator.get("en-us")("hyphenation enhances justification.");
const hy2 = hyphenator.get("de")("Silbentrennung verbessert den Blocksatz.");

console.log(hy1);
console.log(hy2);

To navigate the Succinct Trie without expanding it, the implementation relies on two fundamental bitwise operations:

1. rank1(bitmap, position): Returns the number of set bits (1) up to a specific position in the bitmap.
2. select0(bitmap, count): Returns the smallest position such that the number of unset bits (0) up to that position equals count. It also returns the number of set bits following that position.

Pattern Lookup Algorithm

To find a pattern (e.g., ba) within the Trie:

1. Start with the first character (b).
2. Find the first 0 in the bitmap to identify the current node's scope.
3. Count the following 1s to determine the number of child nodes.
4. Iterate through the child nodes by checking if the character in sTrie chars matches the target character. If no match is found, the pattern does not exist.
5. If sTrie hasVal is 1 for the current node, extract the hyphenation values using rank1 and select0 on the values bitmask.
6. Use the number of the child node and the position of the current 0 to find the next 0 in the bitmap.
7. Repeat for the next character in the pattern.

// Example of rank1 and select0 behavior
// bitmap: 101101011101100100000

rank1(101101011101100100000, 3) -> 3
select0(101101011101100100000, 3) -> 6, 3

Hyphenopoly uses a Succinct Trie to store hyphenation patterns. Unlike traditional approaches that require expanding patterns into a large in-memory Trie (which can consume significant RAM), a Succinct Trie allows the algorithm to run directly on the compressed data. This reduces memory usage to approximately 10% of traditional methods.

Core Components

The structure is composed of several bitstreams and arrays:

• sTrie bitmap: A bitmask representing the tree structure. For each node, it stores the number of children by setting a sequence of 1s followed by a 0.
• sTrie chars: An array of characters representing the labels of the nodes in the Trie.
• sTrie hasVal: A bitmask indicating whether a specific node contains hyphenation values (split points).
• Compressed Hyphenation Values: A separate structure for the actual split points (digits from the TeX patterns). These are compressed by:
  1. Calculating the offset of leading zeros.
  2. Storing values in a compact format where two values (each < 16) fit into a single byte.
  3. Storing the pattern length in a bitmask.

Advantages and Trade-offs

• Pros: Extremely low memory footprint; no expensive expansion phase required; near information-theoretic minimum storage.
• Cons: Slightly larger .wasm file size due to the more complex logic required to traverse the bitstreams; slightly more complex code for pattern lookup.