Count Frequent N-grams Efficiently

Tiber Technologies processes large text streams for search and language features. Implement a one-pass algorithm that identifies the most frequent contiguous n-grams while using bounded memory.

Use the Misra-Gries heavy-hitter algorithm. It maintains at most k - 1 candidate n-grams, so its memory usage does not grow with the stream length. Counts returned are candidate estimates, not guaranteed exact counts.

Formal Specification

Implement count_frequent_ngrams(tokens, n, k):

• tokens is an iterable of strings. It may be a list or a one-pass generator.
• n is a positive integer specifying the n-gram length.
• k is an integer greater than 1 specifying the accuracy and candidate capacity.
• Return a list of at most k - 1 items. Each item is [ngram, estimated_count], where ngram is a list of n strings.
• Sort results by decreasing estimated count, then lexicographically by the n-gram.

When a new n-gram arrives, increment its candidate count if present. Otherwise, insert it if capacity remains. If the candidate set is full, decrement every candidate and remove entries that reach zero.