Real-Time Sliding Window N-Grams

HardPython

Problem

Google Search and Vertex AI pipelines may need real-time statistics over the most recent tokens. Given a finite list that represents an incoming token stream, emit the exact top k n-grams after every complete sliding window.

An n-gram is a contiguous sequence of n tokens. The active window contains the most recent window_size tokens. For each window, return at most k n-grams ordered by decreasing frequency, breaking ties by lexicographic order of their space-joined text.

Implement an online algorithm: when a token arrives, update counts by adding only n-grams newly created at the right boundary and removing only n-grams that leave at the left boundary. Do not recompute every n-gram in the full window.

Formal Specification

Implement process_ngram_stream(tokens, window_size, n, k). The input is a list of strings and three positive integers. Return a list of snapshots. Each snapshot is a list of [phrase, count] pairs for one complete window, ordered as specified. Return an empty list if the stream never reaches window_size tokens.

Constraints

1 <= n <= window_size <= len(tokens) <= 10^5
1 <= k <= 50
Each token is a non-empty string of at most 30 characters
Return one snapshot for every complete window
Order by decreasing frequency, then lexicographic phrase order

Function Signature

def process_ngram_stream(tokens, window_size, n, k):