Ordngrams

Ordngrams are a variant of n-grams that encode only the relative order of elements within a fixed-length window of a sequence. Instead of recording the exact tokens or values, ordngrams preserve the order relations among the items in each window. This makes ordngrams invariant to monotone transformations of the data and useful for analyzing patterns that depend on structure rather than content, such as stylistic or rhythmic patterns in text, music, or event logs.

Formally, let S = s1, s2, ..., sN be a sequence and let k be the window length. For each i with i+k-1 ≤ N, the ordn-gram of length k starting at i is the rank-pattern r_i = (r1, ..., rk), where r_j is the rank of s_{i+j-1} within the window W_i = {s_i, ..., s_{i+k-1}}. Rankings are produced by a stable order: items with equal values receive the same rank, and ties are broken by the original position to yield a deterministic pattern. Example: the window (7, 3, 9) has ranks (2, 1, 3); the window (4, 4, 6) becomes (1, 1, 3).

Ordngrams can be compared by their rank patterns, and standard data structures such as hashing or trie-like maps can be used to count or index them. They are used as features in text classification and authorship analysis, as well as in time-series and sequence mining tasks where the exact symbol values are less informative than their relative ordering. They also complement traditional n-grams by capturing recurring local order motifs that would be missed when focusing on content alone.

Limitations include loss of content information, sensitivity to window size and tie-handling, and potentially high dimensionality if many distinct patterns appear. Applications typically require domain-informed choices of k and robust smoothing. See also n-gram, order isomorphism, permutation patterns.