> For the complete documentation index, see [llms.txt](https://boinc-ai.gitbook.io/transformers.js/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://boinc-ai.gitbook.io/transformers.js/api-reference/utilities/data-structures.md).

# Data Structures

## utils/data-structures

Custom data structures.

These are only used internally, meaning an end-user shouldn’t need to access anything here.

* [utils/data-structures](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures)
  * *static*
    * [.PriorityQueue](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue)
      * [`new PriorityQueue(comparator)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#new_module_utils/data-structures.PriorityQueue_new)
      * [`.size`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+size)
      * [`.isEmpty()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+isEmpty) ⇒ `boolean`
      * [`.peek()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+peek) ⇒ `any`
      * [`.push(...values)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+push) ⇒ `number`
      * [`.extend(values)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+extend) ⇒ `number`
      * [`.pop()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+pop) ⇒ `any`
      * [`.replace(value)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+replace) ⇒ `*`
    * [.CharTrie](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.CharTrie)
      * [`.extend(texts)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.CharTrie+extend)
      * [`.push(text)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.CharTrie+push)
      * [`.commonPrefixSearch(text)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.CharTrie+commonPrefixSearch)
    * [.TokenLattice](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice)
      * [`new TokenLattice(sentence, bosTokenId, eosTokenId)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#new_module_utils/data-structures.TokenLattice_new)
      * [`.insert(pos, length, score, tokenId)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice+insert)
      * [`.viterbi()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice+viterbi) ⇒ `Array.<TokenLatticeNode>`
      * [`.piece(node)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice+piece) ⇒ `string`
      * [`.tokens()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice+tokens) ⇒ `Array`
      * [`.tokenIds()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice+tokenIds) ⇒ `Array`
  * *inner*
    * [\~CharTrieNode](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures..CharTrieNode)
      * [`new CharTrieNode(isLeaf, children)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#new_module_utils/data-structures..CharTrieNode_new)
      * [`.default()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures..CharTrieNode.default) ⇒ `CharTrieNode`
    * [\~TokenLatticeNode](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures..TokenLatticeNode)
      * [`new TokenLatticeNode(tokenId, nodeId, pos, length, score)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#new_module_utils/data-structures..TokenLatticeNode_new)
      * [`.clone()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures..TokenLatticeNode+clone) ⇒ `TokenLatticeNode`

***

### utils/data-structures.PriorityQueue

Efficient Heap-based Implementation of a Priority Queue. It uses an array-based binary heap, where the root is at index `0`, and the children of node `i` are located at indices `2i + 1` and `2i + 2`, respectively.

Adapted from the following sources:

* <https://stackoverflow.com/a/42919752/13989043> (original)
* <https://github.com/belladoreai/llama-tokenizer-js> (minor improvements)

**Kind**: static class of [`utils/data-structures`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures)

* [.PriorityQueue](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue)
  * [`new PriorityQueue(comparator)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#new_module_utils/data-structures.PriorityQueue_new)
  * [`.size`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+size)
  * [`.isEmpty()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+isEmpty) ⇒ `boolean`
  * [`.peek()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+peek) ⇒ `any`
  * [`.push(...values)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+push) ⇒ `number`
  * [`.extend(values)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+extend) ⇒ `number`
  * [`.pop()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+pop) ⇒ `any`
  * [`.replace(value)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue+replace) ⇒ `*`

***

#### new PriorityQueue(comparator)

Create a new PriorityQueue.

| Param      | Type       | Description                                                       |
| ---------- | ---------- | ----------------------------------------------------------------- |
| comparator | `function` | Comparator function to determine priority. Defaults to a MaxHeap. |

***

#### priorityQueue.size

The size of the queue

**Kind**: instance property of [`PriorityQueue`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue)

***

#### priorityQueue.isEmpty() ⇒ \<code> boolean \</code>

Check if the queue is empty.

**Kind**: instance method of [`PriorityQueue`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue)\
**Returns**: `boolean` - `true` if the queue is empty, `false` otherwise.

***

#### priorityQueue.peek() ⇒ \<code> any \</code>

Return the element with the highest priority in the queue.

**Kind**: instance method of [`PriorityQueue`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue)\
**Returns**: `any` - The highest priority element in the queue.

***

#### priorityQueue.push(...values) ⇒ \<code> number \</code>

Add one or more elements to the queue.

**Kind**: instance method of [`PriorityQueue`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue)\
**Returns**: `number` - The new size of the queue.

| Param     | Type  | Description                        |
| --------- | ----- | ---------------------------------- |
| ...values | `any` | The values to push into the queue. |

***

#### priorityQueue.extend(values) ⇒ \<code> number \</code>

Add multiple elements to the queue.

**Kind**: instance method of [`PriorityQueue`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue)\
**Returns**: `number` - The new size of the queue.

| Param  | Type          | Description                        |
| ------ | ------------- | ---------------------------------- |
| values | `Array.<any>` | The values to push into the queue. |

***

#### priorityQueue.pop() ⇒ \<code> any \</code>

Remove and return the element with the highest priority in the queue.

**Kind**: instance method of [`PriorityQueue`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue)\
**Returns**: `any` - The element with the highest priority in the queue.

***

#### priorityQueue.replace(value) ⇒ \<code> \* \</code>

Replace the element with the highest priority in the queue with a new value.

**Kind**: instance method of [`PriorityQueue`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.PriorityQueue)\
**Returns**: `*` - The replaced value.

| Param | Type | Description    |
| ----- | ---- | -------------- |
| value | `*`  | The new value. |

***

### utils/data-structures.CharTrie

A trie structure to efficiently store and search for strings.

**Kind**: static class of [`utils/data-structures`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures)

* [.CharTrie](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.CharTrie)
  * [`.extend(texts)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.CharTrie+extend)
  * [`.push(text)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.CharTrie+push)
  * [`.commonPrefixSearch(text)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.CharTrie+commonPrefixSearch)

***

#### charTrie.extend(texts)

Adds one or more `texts` to the trie.

**Kind**: instance method of [`CharTrie`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.CharTrie)

| Param | Type             | Description                     |
| ----- | ---------------- | ------------------------------- |
| texts | `Array.<string>` | The strings to add to the trie. |

***

#### charTrie.push(text)

Adds text to the trie.

**Kind**: instance method of [`CharTrie`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.CharTrie)

| Param | Type     | Description                    |
| ----- | -------- | ------------------------------ |
| text  | `string` | The string to add to the trie. |

***

#### charTrie.commonPrefixSearch(text)

Searches the trie for all strings with a common prefix of `text`.

**Kind**: instance method of [`CharTrie`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.CharTrie)

| Param | Type     | Description                      |
| ----- | -------- | -------------------------------- |
| text  | `string` | The common prefix to search for. |

***

### utils/data-structures.TokenLattice

A lattice data structure to be used for tokenization.

**Kind**: static class of [`utils/data-structures`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures)

* [.TokenLattice](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice)
  * [`new TokenLattice(sentence, bosTokenId, eosTokenId)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#new_module_utils/data-structures.TokenLattice_new)
  * [`.insert(pos, length, score, tokenId)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice+insert)
  * [`.viterbi()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice+viterbi) ⇒ `Array.<TokenLatticeNode>`
  * [`.piece(node)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice+piece) ⇒ `string`
  * [`.tokens()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice+tokens) ⇒ `Array`
  * [`.tokenIds()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice+tokenIds) ⇒ `Array`

***

#### new TokenLattice(sentence, bosTokenId, eosTokenId)

Creates a new TokenLattice instance.

| Param      | Type     | Description                         |
| ---------- | -------- | ----------------------------------- |
| sentence   | `string` | The input sentence to be tokenized. |
| bosTokenId | `number` | The beginning-of-sequence token ID. |
| eosTokenId | `number` | The end-of-sequence token ID.       |

***

#### tokenLattice.insert(pos, length, score, tokenId)

Inserts a new token node into the token lattice.

**Kind**: instance method of [`TokenLattice`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice)

| Param   | Type     | Description                         |
| ------- | -------- | ----------------------------------- |
| pos     | `number` | The starting position of the token. |
| length  | `number` | The length of the token.            |
| score   | `number` | The score of the token.             |
| tokenId | `number` | The token ID of the token.          |

***

#### tokenLattice.viterbi() ⇒ \<code> Array. < TokenLatticeNode > \</code>

Implements the Viterbi algorithm to compute the most likely sequence of tokens.

**Kind**: instance method of [`TokenLattice`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice)\
**Returns**: `Array.<TokenLatticeNode>` - The array of nodes representing the most likely sequence of tokens.

***

#### tokenLattice.piece(node) ⇒ \<code> string \</code>

**Kind**: instance method of [`TokenLattice`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice)\
**Returns**: `string` - The array of nodes representing the most likely sequence of tokens.

| Param | Type               |
| ----- | ------------------ |
| node  | `TokenLatticeNode` |

***

#### tokenLattice.tokens() ⇒ \<code> Array \</code>

**Kind**: instance method of [`TokenLattice`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice)\
**Returns**: `Array` - The array of nodes representing the most likely sequence of tokens.

***

#### tokenLattice.tokenIds() ⇒ \<code> Array \</code>

**Kind**: instance method of [`TokenLattice`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures.TokenLattice)\
**Returns**: `Array` - The array of nodes representing the most likely sequence of tokens.

***

### utils/data-structures\~CharTrieNode

Represents a node in a character trie.

**Kind**: inner class of [`utils/data-structures`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures)

* [\~CharTrieNode](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures..CharTrieNode)
  * [`new CharTrieNode(isLeaf, children)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#new_module_utils/data-structures..CharTrieNode_new)
  * [`.default()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures..CharTrieNode.default) ⇒ `CharTrieNode`

***

#### new CharTrieNode(isLeaf, children)

Create a new CharTrieNode.

| Param    | Type                         | Description                                                                                           |
| -------- | ---------------------------- | ----------------------------------------------------------------------------------------------------- |
| isLeaf   | `boolean`                    | Whether the node is a leaf node or not.                                                               |
| children | `Map.<string, CharTrieNode>` | A map containing the node's children, where the key is a character and the value is a `CharTrieNode`. |

***

#### CharTrieNode.default() ⇒ \<code> CharTrieNode \</code>

Returns a new `CharTrieNode` instance with default values.

**Kind**: static method of [`CharTrieNode`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures..CharTrieNode)\
**Returns**: `CharTrieNode` - A new `CharTrieNode` instance with `isLeaf` set to `false` and an empty `children` map.

***

### utils/data-structures\~TokenLatticeNode

**Kind**: inner class of [`utils/data-structures`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures)

* [\~TokenLatticeNode](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures..TokenLatticeNode)
  * [`new TokenLatticeNode(tokenId, nodeId, pos, length, score)`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#new_module_utils/data-structures..TokenLatticeNode_new)
  * [`.clone()`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures..TokenLatticeNode+clone) ⇒ `TokenLatticeNode`

***

#### new TokenLatticeNode(tokenId, nodeId, pos, length, score)

Represents a node in a token lattice for a given sentence.

| Param   | Type     | Description                                         |
| ------- | -------- | --------------------------------------------------- |
| tokenId | `number` | The ID of the token associated with this node.      |
| nodeId  | `number` | The ID of this node.                                |
| pos     | `number` | The starting position of the token in the sentence. |
| length  | `number` | The length of the token.                            |
| score   | `number` | The score associated with the token.                |

***

#### tokenLatticeNode.clone() ⇒ \<code> TokenLatticeNode \</code>

Returns a clone of this node.

**Kind**: instance method of [`TokenLatticeNode`](https://huggingface.co/docs/transformers.js/api/utils/data-structures#module_utils/data-structures..TokenLatticeNode)\
**Returns**: `TokenLatticeNode` - A clone of this node.