Search via Sliding Window in 1D Array

Understand the technique of search using sliding windows in a 1-D array.

We'll cover the following

In this lesson, we will explore the phenomenon of traversing (1D) arrays via a specific fixed-sized window.

Given a jump of any specific number of cells (let’s call it stride), we can both mutually exclusively and inclusively slide a fixed-sized window over the array.

Sliding window traversal

We’ll start with the mutually inclusive windows first. By the mutually inclusive window, we mean some values of the previous window are also present in the next window.

Look at the illustration to see what we mean by mutually inclusive.

The animation above shows a window of size 33 and a stride of 11. The sliding window with these two values (window size and stride) moves forward by 1 cell in each iteration, and the maximum number of times it can slide forward is bounded so that the window should not go beyond the array size.

Except for the first window, every other window’s first two cells are the same as the last two cells from the previous window. For example, the first and second cells of the first window are the same as the second and third cells of the first window.

In 5 iterations, we have iterated the entire array of size 7 with window size 3.

Take a moment to make sure you’ve correctly understood the problem. The quiz below will help you to reinforce your learning of the concept above:

The total number of sliding windows

1

How many windows are possible if the window size is 5 and the array is of size 10? Assume the stride is of size 1.

A)

10

B)

5

C)

6

Question 1 of 30 attempted

Implementation for sliding window

Explore the following program by changing the values in “SW.txt” in the first line, especially the parameters of the array’s dimension, window size, and stride size, respectively.

Press + to interact
main.cpp
SW.txt
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
#define Capacity 100
void load(const char fileName[], int M[], int &size, int &wSize,
	int &stride)
{
	ifstream Rdr(fileName);
	Rdr >> size >> wSize >> stride;	// LOADING: array, window and stride sizes
	for (int i = 0; i < size; i++)	// loading array 
		Rdr >> M[i];
}
void displayArray(const char Msg[], int M[], int size)
{
	cout << Msg << " {";	// printing the message before printing the array
	for (int i = 0; i < size; i++)
	{
		cout << setw(4) << M[i] << " ";	// printing the original array on which 
	}	// window will slide
	cout << "}\n";
}
void displayAWindow(int M[], int ws, int wSize)
{
	// Displaying a window anchored at[ws] 
	cout << "\t{";
	for (int i = 0; i < wSize; i++)	// the window is of wSize
	{
		cout << setw(3) << M[ws + i] << " ";
		// anchored at[ws] hence shifted by[ws+i]
	}
	cout << "}";
}
void displayAllWindows(int M[], int size, int wSize, int stride = 1)
{
	cout << "______________________________________________________\n\n";
	cout << "All the windows of: \t" << wSize << "\nAnd stride of: \t\t" << stride << endl << endl;
	for (int i = 0; 
			i + wSize <= size;	// one window is of wSize, hence no further stride
								// or i+(wsize-1) <= size - 1 equivalent to i+wSize<=size
				i += stride)	// anchorpoint should be incremented by +=stride
	{
		cout << "Anchored At[" << i << "]: ";
		displayAWindow(M, i, wSize);
		// anchored at M[i] and of the size wSize
		cout << endl << endl;
	}
}
int main()
{
	int M[Capacity], size, wSize, stride;
	load("SW.txt", M, size, wSize, stride);
	displayArray("\n\nThe array is: ", M, size);
	displayAllWindows(M, size, wSize, stride);
	return 0;
}

The code above first loads the data from a text file “SW.txt” into the program, which includes the array, the size of the window, and the stride size. It then displays the original array and all the windows of a certain size that slide over the array with a certain stride size. The window size and stride size can be adjusted, and the program will display all the windows accordingly. The function displayAllWindows() displays all the windows anchored at different positions and displayAWindow() displays a window anchored at a specific position. The program is a simple implementation of the sliding window algorithm.

Instruction: Change the content of “SW.txt” with

SW.txt
------
10 3 2 
5 -20 15 16 -35 -1 1 2 3 4

Sample output:
All the windows of: 3
And stride of: 	    2

Anchored At[0]: 	{  5 -20  15 }
Anchored At[2]: 	{ 15  16 -35 }
Anchored At[4]: 	{-35  -1   1 }
Anchored At[6]: 	{  1   2   3 }

In the first line of “SW.txt” above, 10 represents the array size, 3 represents the window size, and 2 represents the stride size.

This strategy of traversing in the sliding window has several applications.

For example, using this strategy, we can find the maximum or minimum, or even average, of the values within a window, depending on what we need to find.

Exercise: Finding the maximum in each window

Given an array, a window of size 3, and a stride of 1, find the maximum in each sliding window. Look at the following sample program:

Input: 5 -20 15 16 -3 5 -1
Output: 15 16 16 16 5

Implementation direction

In the two animations below, we have explained the working of the proposed algorithm with window size and stride as 3 and 1, respectively.

Here is another example with window size 3 and stride equal to 2:

If the stride is equal to 3, how would our window move?

With a window size of 3 and stride of 3, our windows will move mutually exclusively, i.e., the values of the previous window will not be included in the next window.

Your implementation playground

Write the code in the coding playground below for computing the maximum in each window.

Press + to interact
main.cpp
SW.txt
int findingMaxInEachWindow(int M[], int size, int wSize, int stride, 
                                int Maxes[], int &maxSize)
{
    // Write code here. 
}

Why use sliding window

Sliding window techniques are commonly used in various fields, such as computer vision, image processing, natural language processing, and signal processing.

In 1-D arrays, sliding window techniques can be used for:

  • Moving average and running sum calculation.
  • Substring search and matching.
  • Signal processing and filtering.
  • Text segmentation and language model training.

In 2-D arrays, sliding window techniques can be used for:

  • Object detection and recognition in images and videos.
  • Image segmentation and feature extraction.
  • Image denoising and super-resolution.
  • Object tracking in videos.
  • Medical image analysis and diagnoses.
  • Human-computer interaction and gesture recognition.

In general, sliding window techniques can be used to analyze and extract featuresSpecific characteristics or attributes of the data that are extracted for further analysis or processing. from data locally and efficiently. The window is moved over the data in a defined manner, and the features are extracted at each window position. These techniques are widely used in computer vision, image processing, natural language processing, and many other fields.