Internal Architecture of tree_regions_system: Queue-Based Region Detection in BetterHTMLChunking

The tree_regions_system module in carlosplanchon/betterhtmlchunking uses a breadth-first queue traversal to partition HTML documents into size-constrained Regions of Interest (ROIs), deferring oversized nodes for deeper processing while preserving document order.

The tree_regions_system is the core engine of the carlosplanchon/betterhtmlchunking repository responsible for intelligently chunking HTML documents. By implementing a queue-based processing architecture, it transforms a hierarchical DOM tree into flat, manageable regions that respect maximum length constraints without breaking document semantics.

Three-Layer Architecture of tree_regions_system

The internal design separates concerns across three distinct layers that work together to process HTML documents:

Layer	Responsibility	Main Types / Functions
Tree representation	Parses raw HTML, builds a treelib.Tree where each node stores text and HTML lengths.	DOMTreeRepresentation (see betterhtmlchunking/tree_representation.py)
ROI construction	Given a node and its direct children, groups children into chunks that do not exceed max_node_repr_length. Handles oversized children by enqueuing them for deeper processing.	ROIMaker, RegionOfInterest (see betterhtmlchunking/tree_regions_system.py lines 57-89)
Queue-driven traversal	Performs a breadth-first walk over the tree, repeatedly invoking ROIMaker. The queue ensures that large sub-trees are revisited after their parent has been processed.	TreeRegionsSystem.start() (see betterhtmlchunking/tree_regions_system.py lines 42-68)

Queue-Based Breadth-First Traversal

The TreeRegionsSystem class implements the main processing loop using Python's queue.Queue to manage nodes awaiting inspection. This approach avoids deep recursion and ensures predictable memory usage when processing deeply nested HTML documents.

The system initializes the queue with a root xpath (either explicitly supplied, /html, or the first xpath in the representation):

subtrees_queue = queue.Queue()
subtrees_queue.put(root_xpath)

A classic while-loop dequeues one xpath at a time, processes the node, gathers its children, and may push additional child xpaths back onto the queue:

while not subtrees_queue.empty():
    node_xpath = subtrees_queue.get()
    # …process node…

    for child_tag in region_of_interest_maker.children_to_enqueue:
        subtrees_queue.put(child_tag)

Why a queue? Breadth-first order preserves document order for the final ROI list, and it allows the algorithm to postpone processing of oversized children until the parent's ROI has been emitted. This avoids deep-recursive calls and keeps memory usage predictable when handling complex DOM structures.

ROI Creation with ROIMaker

For each dequeued node, the system instantiates an ROIMaker that groups direct children into RegionOfInterest objects respecting the max_node_repr_length constraint.

The ROIMaker._process_children method (lines 14-21 in betterhtmlchunking/tree_regions_system.py) walks the child list, accumulating their representation length:

node_length = self.get_node_repr_length(node)

Whenever the accumulated length would exceed the budget, the current RegionOfInterest is closed and a new one started. If a single child alone exceeds the budget, that child is not placed in any region; instead it is appended to self.children_to_enqueue so that it will be processed as a new root later.

When a node has no children or all children fit into a single region, _check_node_as_roi collapses the whole node into a single ROI, marking it with node_is_roi = True (lines 46-57 in betterhtmlchunking/tree_regions_system.py).

Collecting and Ordering Final Regions

All ROIs produced by each ROIMaker instance are appended to self.regions_of_interest_list. After the queue is empty, the list is sorted by document order using the helper order_regions_of_interest_by_pos_xpath, which leverages the original pos_xpaths_list from the representation to compute a deterministic order (lines 71-89 in betterhtmlchunking/tree_regions_system.py).

If no ROI satisfies the size constraint, the algorithm falls back to a single ROI that covers the whole document (lines 150-170 in betterhtmlchunking/tree_regions_system.py).

The final sorted mapping (self.sorted_roi_by_pos_xpath) is stored as an indexed dictionary for easy downstream consumption.

Practical Usage Examples

Basic ROI Extraction

from betterhtmlchunking.tree_representation import DOMTreeRepresentation
from betterhtmlchunking.tree_regions_system import TreeRegionsSystem

# Load raw HTML

html = """<html><body>
    <p>First paragraph.</p>
    <p>Second paragraph with <img src="a.png"/> a picture.</p>
    <div>Some <span>nested</span> content.</div>
</body></html>"""

# Build tree representation

tree_repr = DOMTreeRepresentation(website_code=html)

# Create regions system with a 200-character budget (HTML length)

regions = TreeRegionsSystem(
    tree_representation=tree_repr,
    max_node_repr_length=200,
    repr_length_compared_by="html_length"
)

# Retrieve ordered ROIs

for idx, roi in regions.sorted_roi_by_pos_xpath.items():
    print(f"ROI #{idx+1}:")
    print("  XPaths :", roi.pos_xpath_list)
    print("  Length :", roi.repr_length)
    print("  Whole node ROI ?", roi.node_is_roi)

Adjusting Budget Constraints

# Use a stricter budget of 100 characters based on text length

regions_small = TreeRegionsSystem(
    tree_representation=tree_repr,
    max_node_repr_length=100,
    repr_length_compared_by="text_length"
)

# The queue will now enqueue many deeper nodes, producing finer-grained chunks

print("Number of ROIs:", len(regions_small.sorted_roi_by_pos_xpath))

These examples demonstrate the three-step workflow: (1) parse → (2) queue-driven ROI generation → (3) ordered output.

Summary

• TreeRegionsSystem implements a queue-based breadth-first traversal using queue.Queue to process HTML documents iteratively rather than recursively.
• The architecture separates concerns into three layers: tree representation (DOMTreeRepresentation), ROI construction (ROIMaker), and queue-driven traversal (TreeRegionsSystem).
• Oversized nodes are deferred via children_to_enqueue, allowing the system to break large DOM subtrees into smaller chunks without breaking document order.
• Final regions are sorted by document position using order_regions_of_interest_by_pos_xpath to ensure deterministic, sequential output.
• The implementation resides primarily in betterhtmlchunking/tree_regions_system.py with supporting types in betterhtmlchunking/tree_representation.py.

Frequently Asked Questions

How does tree_regions_system handle deeply nested HTML documents without recursion?

The tree_regions_system avoids Python's recursion limit by using a queue.Queue to manage nodes awaiting processing. When TreeRegionsSystem.start() encounters a child that exceeds max_node_repr_length, it appends that child to children_to_enqueue rather than recursing. After the current node's regions are emitted, these children are added to the queue for subsequent iteration. This breadth-first approach keeps memory usage predictable and prevents stack overflow errors on deeply nested DOM structures.

What is the difference between text_length and html_length in the queue processing?

The repr_length_compared_by parameter determines which metric ROIMaker uses to calculate node sizes during queue processing. When set to "text_length", the system measures only the visible text content of nodes, ignoring HTML tags and attributes. When set to "html_length", it counts the full HTML serialization including tags, attributes, and whitespace. This choice affects which nodes get enqueued for deeper processing: a node with heavy HTML markup but little text might exceed the budget under html_length but pass under text_length, triggering different queue traversal patterns.

How does the system ensure regions are returned in document order?

After the queue empties, TreeRegionsSystem calls order_regions_of_interest_by_pos_xpath (lines 71-89 in betterhtmlchunking/tree_regions_system.py) to sort the collected regions. This function uses the original pos_xpaths_list from DOMTreeRepresentation, which maps each xpath to its document position index. By comparing these indices, the system produces a deterministic ordering that matches the original HTML document sequence, even though the breadth-first queue processing might have generated regions in a different temporal order.

What happens when no regions satisfy the size constraint?

If the queue processing completes without producing any valid regions (for example, when the entire document exceeds max_node_repr_length and cannot be split further), the system implements a fallback mechanism in lines 150-170 of betterhtmlchunking/tree_regions_system.py. It creates a single RegionOfInterest covering the entire document tree, ensuring that the caller always receives at least one region even when the chunking constraints cannot be strictly satisfied. This prevents empty results and ensures downstream consumers always have content to process.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}