Does Sequitur need labeled examples?

Its basic grammar construction does not. It finds repetition in a supplied symbolic sequence, though evaluating the usefulness of the result may require annotations.

How does it differ from Re-Pair?

Sequitur updates a grammar as symbols arrive while enforcing its constraints. Re-Pair repeatedly selects frequent pairs over an input or block. Their strategies need not produce the same grammar.

Can it directly understand continuous sensor values?

The basic input is discrete symbols. A chosen representation or discretization is needed, and that choice can lose information or alter apparent repetition.

AI Glossary / MLOps and deployment / Intermediate

Sequitur algorithm

Definition

Sequitur is an incremental algorithm that discovers repeated structure in a sequence of discrete symbols by building a hierarchical grammar. It replaces repeated adjacent patterns with reusable rules while maintaining constraints that prevent duplicate pairs and rules with insufficient reuse.

What it means

A sequence can contain smaller patterns repeated inside larger patterns. A rule might name a short sequence, while another incorporates that name into a longer sequence. Expanding the start rule reconstructs the input exactly.

Here, grammar means a set of rewriting rules for that particular sequence. It does not automatically mean the grammar of a human language, nor does the result necessarily generate sensible new examples. Its connection to AI lies in discovering structure from observations; interpreting that structure still requires domain knowledge and evaluation.

How it works

Append each new input symbol to the start rule. If this creates a repeated non-overlapping adjacent pair, replace the occurrences with a reference to a rule for that pair. Reuse an existing rule when its complete right-hand side already matches; otherwise create a new one.

Sequitur also enforces rule utility: each subsidiary rule must be referenced at least twice in the grammar. If a rule is left with only one reference, expand it at that location and remove the unnecessary rule. This can lengthen other rules and expose further repeated pairs.

These updates maintain digram uniqueness and rule utility. Efficient indexes and local updates matter; repeatedly rescanning everything would not achieve the published algorithm's efficiency.

Three practical examples

1. Event-sequence analysis: recurring sequences of symbolic actions can become rules that analysts inspect as candidate workflow patterns. The rule's recurrence is evidence of repetition, not proof of a business process boundary.

2. Text compression research: the grammar provides a reversible representation of repeated text fragments. A complete compressor must also encode the rules and references efficiently.

3. Structured sequence exploration: a researcher can discretize observations into symbols and inspect hierarchical repetition. The choice of symbols affects what the algorithm can discover, so that preprocessing decision must remain visible.

Think of it this way

Think of introducing abbreviations whenever an instruction pair recurs. If an abbreviation later appears in only one place, replace it there with its full wording to avoid maintaining an unnecessary definition.

The analogy stops at meaning: Sequitur uses exact symbol matches and structural rules, rather than deciding which instructions a person considers related. Its hierarchy can be useful without being a semantic explanation.

Worked example

Feed the symbols x, y, x, y, z, x, y in order. After the first three symbols, the start rule is S→xyx, with no repeated non-overlapping pair to replace.

Adding the fourth symbol gives xyxy. The pair xy occurs twice, so create A→xy and replace both occurrences. The grammar becomes S→AA and A→xy. Rule A has two references, satisfying utility.

Append z and then x, giving S→AAzx. When the final y arrives, the new xy matches the complete existing rule A. Replace it with A, leaving S→AAzA and A→xy. Expanding S gives xyxyzxy, exactly the seven-symbol input.

The start rule has four symbols and A's right-hand side has two, for six right-hand-side symbols overall. That structural count does not mean the file is six bytes: identifiers and rule serialization also matter.

To see utility separately, suppose a valid intermediate representation contains S→BB, B→Ac and A→xy, with A referenced only once. Inlining A yields B→xyc and removes A without changing the expanded string. The rule-utility count concerns references in the grammar, not the number of times a pattern appears after full expansion.

Illustrative case study

Fictional case: TraceFold analyses sequences of actions from an internal tool. Sequitur identifies a frequently reused rule that spans the end of one user's session and the start of another.

The repetition is real in the concatenated data, but the inferred unit is not a meaningful individual workflow. The team revises its input design, preserving session boundaries and checking how boundary markers affect rule formation.

Analysts then inspect candidate rules against individual sessions before assigning workflow labels. This fictional case shows that exact pattern discovery can be technically correct while an interpretation is wrong because the input representation omitted an important boundary.

Common misconceptions and mistakes

“Sequitur always creates the smallest possible grammar.” Its constraints guide incremental construction; they do not establish global minimum grammar size.

“Every repeated adjacent pair can be replaced, even if occurrences overlap.” The two appearances of xx in xxx overlap. Treating them as independent substitutions would reuse an input symbol.

“Every rule is a meaningful concept.” Rules reflect exact repetition under the chosen symbolization. Human-readable meaning is an additional interpretation.

“Incremental means old rules never change.” New input can cause rule creation, reuse and removal. The current grammar continues to represent the input seen so far, but its organization can evolve.

Business use

Sequitur can support exploratory analysis when a business has long symbolic sequences and wants to understand repeated structure. It is most useful when the team can explain how events became symbols and how sequence boundaries were handled.

Evaluate whether discovered patterns are stable across time periods and useful to analysts. For storage, measure complete encoded size, memory use and reconstruction speed. For predictive use, test a separately defined prediction method on held-out data; the grammar alone is not a validated forecasting system. Keep the raw sequence or a verified reversible representation so interpretation can be revisited.

Check your understanding

A rule occurs only once in the grammar but its enclosing rule is expanded many times. Does that automatically satisfy Sequitur's rule-utility requirement?

Answer: No. Utility counts the rule's references in the grammar. A singly referenced subsidiary rule is expanded at its reference and removed.

Related terms

Grammar induction
Re-Pair
Lossless compression
grammar-based compression
digram
symbolic sequence
pattern discovery

Learn next

Trace rule creation and reuse on a short sequence, then practice removing singly referenced rules. Compare the resulting hierarchy with Re-Pair and inspect how different symbolizations or session boundaries change the patterns discovered.

Re-Pair

Sources

Primary research: Craig G. Nevill-Manning and Ian H. Witten, “Identifying Hierarchical Structure in Sequences: A linear-time algorithm,” particularly Section 2 and the implementation discussion: https://ml.cms.waikato.ac.nz/publications/1997/NM-IHW-Hierarch97.pdf . The walkthrough and fictional session-analysis case are original illustrations.

Previous: Sequentially ordered organization Next: Seriation (statistics)