Concept

Visited set — where it appears

The record a queue-based traversal keeps of what it has already produced, so that nothing is reported twice. A traversal whose order guarantees each item is reached once needs none, which is the same substitution a left-first walk makes on a document listing.

Named by 3 essays across 3 fields — each of them below, with the objects they name alongside it.

Every copy points right

A greedy self-referential parse chooses each phrase's source from text already produced, so an occurrence copied from another lies strictly to its right. That one fact removes a visited set from a propagation, exactly as a left-first walk removed an array one strand ago.

structures · Parse

The same occurrences, less bookkeeping

Two traversals examine identically many phrases and report identically many occurrences. What differs is that one holds every occurrence found so far in a set and the other holds an ordered list and a cursor.

indexes · Parse

A constant factor, not a term

The substitution was expected to remove a quantity proportional to the answer. Both traversals hold a quantity proportional to the answer, and what it removes is a factor of 1.6 that shrinks as the collection grows.

wrong · Parse

Named alongside it

The objects these essays reach for when they reach for this one.

Phrase index Propagation Secondary occurrence Lempel ziv parse Traversal order Working memory Index size Previous occurrence chain Space accounting

All concepts