Sliding Window

Sliding Window (с англ. — «скользящее окно») — это концепция или метод обработки данных, при котором анализируется или вычисляется некий показатель на подмножестве (окне) последовательности данных, причём это окно последовательно перемещается по всей последовательности с определённым шагом. В информатике и математической статистике sliding window является фундаментальным подходом, используемым для решения задач, связанных с массивами, строками, временными рядами и сетевыми протоколами. Основная идея заключается в поддержании актуального состояния только для текущего фрагмента данных, что позволяет значительно снизить вычислительную сложность по сравнению с полным пересчётом для каждой новой позиции.

История и происхождение

Концепция скользящего окна имеет корни в нескольких дисциплинах. В статистике и обработке сигналов метод скользящего среднего (moving average) применялся с начала XX века для сглаживания временных рядов. В компьютерных сетях механизм sliding window был формализован в 1970-х годах для управления потоком данных в протоколах TCP/IP (Transmission Control Protocol). В алгоритмике, как отдельный класс задач, sliding window получил широкое распространение в 2000-х годах с ростом популярности соревнований по программированию (например, TopCoder, Codeforces) и необходимостью эффективной обработки больших объёмов данных.

Классификация

По типу окна

1. Фиксированное окно (Fixed-size window). Размер окна (количество элементов) остаётся постоянным на протяжении всего прохода. Пример: вычисление суммы каждых трёх последовательных элементов массива.
2. Динамическое окно (Variable-size window). Размер окна может изменяться в зависимости от условий задачи. Часто используется для поиска подмассива, удовлетворяющего определённому критерию (например, минимальная длина подмассива с суммой, большей заданного числа).

По направлению движения

1. Однонаправленное (Forward). Окно движется только вперёд по последовательности, не возвращаясь назад. Это наиболее распространённый тип.
2. Двунаправленное (Two-pointer). Используется два указателя (левый и правый), которые могут двигаться в разных направлениях, расширяя или сужая окно. Это частный случай динамического окна.

По области применения

1. Алгоритмическое (Array/String). Применяется для задач на массивах и строках: поиск подстрок, максимальных сумм, подсчёт уникальных элементов.
2. Сетевое (Network Protocol). Используется в протоколах передачи данных для управления потоком и предотвращения перегрузок.
3. Статистическое (Time Series). Применяется для анализа временных рядов: скользящее среднее, скользящая дисперсия, скользящая корреляция.
4. Графическое (Computer Vision). Используется в обработке изображений для свёртки, детекции объектов (например, sliding window в архитектуре R-CNN).

Принцип работы

Алгоритмический подход

В классическом алгоритмическом варианте sliding window работает следующим образом:

1. Инициализация. Устанавливаются два указателя: left (начало окна) и right (конец окна). Обычно оба указывают на первый элемент последовательности.
2. Расширение окна. Указатель right сдвигается вправо, добавляя новые элементы в окно. При каждом добавлении обновляется состояние (например, сумма, количество уникальных символов).
3. Сужение окна. Если текущее окно перестаёт удовлетворять условию (например, превышен максимальный размер или нарушен критерий), указатель left сдвигается вправо, удаляя элементы из окна. Состояние также обновляется.
4. Фиксация результата. На каждом шаге или при достижении определённого состояния фиксируется текущий результат (например, максимальная длина подмассива, найденная подстрока).

Сетевой протокол (TCP)

В протоколе TCP sliding window используется для управления потоком данных между отправителем и получателем. Размер окна определяет, сколько байт отправитель может передать без получения подтверждения (ACK). Принцип:

• Отправитель передаёт данные в пределах окна.
• Получатель отправляет подтверждение, указывая, сколько байт он готов принять (размер окна может динамически изменяться).
• Окно «скользит» вперёд по мере получения подтверждений, позволяя передавать новые данные.

Применение

В алгоритмических задачах

Sliding window является одной из ключевых техник для решения задач на собеседованиях в IT-компании (например, в Яндекс, Google, Amazon). Типичные задачи:

• Максимальная сумма подмассива фиксированной длины. Найти подмассив из k элементов с максимальной суммой.
• Наименьший подмассив с суммой больше заданного числа. Используется динамическое окно.
• Поиск анаграмм. Найти все вхождения анаграммы строки-шаблона в строке-тексте.
• Самая длинная подстрока без повторяющихся символов. Классическая задача на динамическое окно.

В обработке сигналов и статистике

• Скользящее среднее (Moving Average). Используется для сглаживания шумов в финансовых данных (цены акций), метеорологии (температура), сенсорах.
• Скользящая дисперсия и стандартное отклонение. Применяется для оценки волатильности.
• Скользящая корреляция. Используется для анализа взаимосвязи двух временных рядов во времени.

В компьютерном зрении

• Детекция объектов. Изображение разбивается на множество перекрывающихся окон фиксированного размера. Каждое окно подаётся на вход классификатора (например, SVM или нейронной сети), который определяет, содержит ли оно объект интереса. Этот метод был основой для ранних систем детекции (например, Viola-Jones для лиц).

В сетевых технологиях

• TCP (Transmission Control Protocol). Механизм sliding window является основой для управления потоком и контроля перегрузок в TCP.
• Протоколы канального уровня. Например, в Ethernet используется для управления потоком кадров.

Примеры реализации

Пример 1: Фиксированное окно (сумма каждых трёх элементов)

Дано: массив [1, 2, 3, 4, 5, 6]. Размер окна k = 3.

• Шаг 1: окно [1, 2, 3], сумма = 6.
• Шаг 2: окно [2, 3, 4], сумма = 9. Вычисляется как 6 - 1 + 4 = 9.
• Шаг 3: окно [3, 4, 5], сумма = 12.
• Шаг 4: окно [4, 5, 6], сумма = 15.

Пример 2: Динамическое окно (наименьший подмассив с суммой ≥ 10)

Дано: массив [2, 1, 3, 4, 5]. Целевая сумма = 10.

• Начало: left = 0, right = 0, окно [2], сумма = 2.
• Расширение: right = 1, окно [2, 1], сумма = 3.
• Расширение: right = 2, окно [2, 1, 3], сумма = 6.
• Расширение: right = 3, окно [2, 1, 3, 4], сумма = 10. Длина = 4. Фиксируем.
• Сужение: left = 1, окно [1, 3, 4], сумма = 8. Условие не выполнено.
• Расширение: right = 4, окно [1, 3, 4, 5], сумма = 13. Длина = 4.
• Сужение: left = 2, окно [3, 4, 5], сумма = 12. Длина = 3. Фиксируем (лучше).
• Сужение: left = 3, окно [4, 5], сумма = 9. Условие не выполнено.
• Результат: минимальная длина = 3 (подмассив [3, 4, 5]).

Преимущества и недостатки

Преимущества

• Высокая эффективность. Временная сложность большинства алгоритмов на основе sliding window составляет O(n), где n — длина последовательности. Это значительно быстрее, чем наивные подходы с O(n²) или O(n*k).
• Экономия памяти. Требуется хранить только состояние текущего окна, а не всю последовательность.
• Простота реализации. Алгоритм легко кодируется и отлаживается.

Недостатки

• Ограниченная применимость. Метод эффективен только для задач, где состояние окна может быть обновлено инкрементально (добавление/удаление одного элемента). Для задач, требующих полного пересчёта при каждом сдвиге, sliding window не даёт выигрыша.
• Чувствительность к порядку данных. Окно работает только с последовательными данными. Если порядок не важен, метод неприменим.
• Сложность с динамическими условиями. Для некоторых задач с несколькими условиями (например, несколько ограничений на сумму, длину и уникальность) реализация может стать громоздкой.

Интересные факты

• В 1970-х годах механизм sliding window в TCP был предложен Винтоном Серфом и Робертом Каном, создателями протокола.
• В русскоязычной литературе термин «скользящее окно» часто используется в контексте обработки сигналов и статистики, в то время как в алгоритмике чаще применяют английское название «Sliding Window».
• В некоторых задачах (например, поиск максимальной суммы подмассива) sliding window может быть заменён алгоритмом Кадане, который также использует идею инкрементального обновления, но не требует явного окна.
• В компьютерном зрении метод sliding window был основой для первых систем распознавания лиц (Viola-Jones, 2001), но в современных нейросетевых подходах (YOLO, SSD) он заменён на более эффективные методы, не требующие полного перебора окон.

Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (Introduction to Algorithms), 3-е издание.
• Седжвик Р., Уэйн К. «Алгоритмы на Java» (Algorithms), 4-е издание.
• RFC 793 — Transmission Control Protocol, DARPA Internet Program, 1981.
• Viola P., Jones M. «Rapid object detection using a boosted cascade of simple features», CVPR 2001.
• Статьи на ресурсах GeeksforGeeks, LeetCode, Codeforces по теме «Sliding Window».