Skip to content

Main content
Bookmark this: tool.io/trie/node-terminal-count-table

Prefix Trie Node Terminal Count Table

Bounded explicit prefix trie with root ID 0, unique sibling UTF-16 code-unit edges and terminal flags; count terminal descendants including self at every node; trie terminals are distinct words, not observation counts.

Loading tool…

Description

Count terminal descendants including self at every node; trie terminals are distinct words, not observation counts.

A trie stores literal words as root-to-node character paths, with terminal flags marking complete words. A terminal can also have children, and an existing prefix path need not be a stored word. This family uses one UTF-16 code unit per ordinary edge, so code-unit length differs from a displayed character or Unicode code-point count.

Count terminal descendants including self at every node; trie terminals are distinct words, not observation counts.

When to use this tool

Use this tool to count terminal descendants including self at every node; trie terminals are distinct words, not observation counts.

How to use the tool and how it works

  1. Enter nodesJson using the definitions below. Serialize JSON text fields in the decoded shape shown below.
  2. Run the operation. Resolve input-format errors before interpreting an output.
  3. Read result.counts, using the stated boundary, ordering, sign and absence conventions.

For every node reconstruct its prefix and count terminal words beginning with it. Return {id,count} in source node order, counting the node itself when terminal.1

Input fieldMeaning and unitsAccepted input
nodesJsonJSON array of {id,parent,character,terminal} nodes under the complete root-zero trie rules below.Text, at most 8,192 UTF-16 code units; narrower grammar/range rules also apply.

These decoded structures show the examples inside JSON text fields. Supply their serialized JSON strings as input.

json
{
  "nodesJson": [
    {
      "id": 0,
      "parent": null,
      "character": "",
      "terminal": false
    },
    {
      "id": 1,
      "parent": 0,
      "character": "a",
      "terminal": true
    },
    {
      "id": 2,
      "parent": 1,
      "character": "b",
      "terminal": true
    },
    {
      "id": 3,
      "parent": 0,
      "character": "b",
      "terminal": true
    }
  ]
}
Output fieldInterpretation
resultObject containing the fields below.
result.countsSource-order {id,count} terminal completion totals, including self when terminal.
json
{
  "input": {
    "nodesJson": "[{\"id\": 0, \"parent\": null, \"character\": \"\", \"terminal\": false}, {\"id\": 1, \"parent\": 0, \"character\": \"a\", \"terminal\": true}, {\"id\": 2, \"parent\": 1, \"character\": \"b\", \"terminal\": true}, {\"id\": 3, \"parent\": 0, \"character\": \"b\", \"terminal\": true}]"
  },
  "output": {
    "result": {
      "counts": [
        {
          "id": 0,
          "count": 3
        },
        {
          "id": 1,
          "count": 2
        },
        {
          "id": 2,
          "count": 1
        },
        {
          "id": 3,
          "count": 1
        }
      ]
    }
  }
}

Limitations and assumptions

  • Counts include the empty word when the root is terminal and do not represent stored occurrence frequencies.
  • Ordinary node tables have at most 128 nodes with distinct IDs 0–127, one root ID 0 with empty character and null parent, unique parent/character edges, complete acyclic parent links and a boolean terminal flag. Every nonroot character is exactly one UTF-16 code unit.
  • Every declared outer field is required and unknown outer fields are rejected. Strings and JSON text have size limits, lists are bounded to 128 entries, and JSON nesting/node counts are bounded. Tighter operation-specific bounds stated above take precedence.
  • Ordinary numeric outputs must be finite and within safe-integer magnitude. Exact large lengths/counts use decimal strings. Original record indexes and code-unit positions are zero-based; span ends are exclusive unless stated otherwise.

Alternative or Complementary methods

Choose word membership, prefix existence, completion or ranking according to the question. Normalize text separately if needed; these operations preserve exact code units and caller order.

References

  1. Tool behavior and example: Prefix Trie Node Terminal Count Table — tool.io

Similar or alternative tools

  • Prefix Trie Literal Prefix Completion Count

    Bounded explicit prefix trie with root ID 0, unique sibling UTF-16 code-unit edges and terminal flags; count distinct terminal completions, not duplicate original word observations or inferred dictionary frequencies.

  • Prefix Trie Terminal Membership Bit List

    Bounded explicit prefix trie with root ID 0, unique sibling UTF-16 code-unit edges and terminal flags; test exact terminal word membership for each supplied query, preserving empty queries and repeated occurrences.

Support Tool.io