下载文档原格式
滑动窗口算法原理滑动窗口算法（Sliding Window Algorithm）是一种用于解决字符串（或数组）问题的算法。
它通过使用一个固定长度的窗口，在字符串上滑动并保持窗口的大小不变，来寻找满足特定条件的子串（或子数组）。
滑动窗口算法的基本思想是通过两个指针，一个左指针和一个右指针，在给定字符串上移动这两个指针以定位子串。
右指针用于扩展窗口，而左指针用于收缩窗口。
通过不断的移动左右指针，可以在字符串上依次扫描每个可能的子串。
1. 找到满足特定条件的最小子串（Minimum Window Substring）。
2. 找到满足特定条件的最长子串（Longest Substring Without Repeating Characters）。
3. 找到满足特定条件的数组中的最长子数组（Maximum SumSubarray of Size K）。
下面详细解释滑动窗口算法的原理和步骤：1. 定义两个指针，即左指针（left）和右指针（right）。
初始时，左指针指向子串的起始位置，右指针指向子串的结束位置。
2.向右移动右指针，扩展窗口，直到满足特定条件为止。
在扩展窗口的过程中，可以更新一些数据结构来保存所需的信息，比如字符频率的哈希表。
3.当窗口满足特定条件时，开始收缩窗口，即向右移动左指针。
同时，更新所需的信息。
4.在收缩窗口的过程中，不断更新最优解。
如果当前窗口满足最优条件，可以更新最优解。
5.重复步骤2到步骤4，直到右指针到达字符串的末尾。
举个例子来说明滑动窗口算法的应用：问题：给定一个字符串s和一个目标字符串t，在字符串s中找到包含t所有字符的最短子串。
示例输入：s="ADOBECODEBANC",t="ABC"示例输出："BANC"首先，我们可以使用一个哈希表来记录目标字符串t中每个字符的频率。
然后使用两个指针left和right来定义一个窗口，初始时left和right都指向字符串s的第一个位置。
滑动窗⼝算法基本原理与实践学过计算机⽹络的同学，都知道滑动窗⼝协议（Sliding Window Protocol），该协议是的⼀种应⽤，⽤于⽹络数据传输时的流量控制，以避免拥塞的发⽣。
该协议允许发送⽅在停⽌并等待确认前发送多个数据分组。
由于发送⽅不必每发⼀个分组就停下来等待确认。
因此该协议可以加速数据的传输，提⾼⽹络吞吐量。
滑动窗⼝算法其实和这个是⼀样的，只是⽤的地⽅场景不⼀样，可以根据需要调整窗⼝的⼤⼩，有时也可以是固定窗⼝⼤⼩。
滑动窗⼝算法（Sliding Window Algorithm）Sliding window algorithm is used to perform required operation on specific window size of given large buffer or array.滑动窗⼝算法是在给定特定窗⼝⼤⼩的数组或字符串上执⾏要求的操作。
This technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the timecomplexity.该技术可以将⼀部分问题中的嵌套循环转变为⼀个单循环，因此它可以减少时间复杂度。
简⽽⾔之，滑动窗⼝算法在⼀个特定⼤⼩的字符串或数组上进⾏操作，⽽不在整个字符串和数组上操作，这样就降低了问题的复杂度，从⽽也达到降低了循环的嵌套深度。
其实这⾥就可以看出来滑动窗⼝主要应⽤在数组和字符串上。
基本⽰例如下图所⽰，设定滑动窗⼝（window）⼤⼩为 3，当滑动窗⼝每次划过数组时，计算当前滑动窗⼝中元素的和，得到结果 res。
可以⽤来解决⼀些查找满⾜⼀定条件的连续区间的性质（长度等）的问题。
由于区间连续，因此当区间发⽣变化时，可以通过旧有的计算结果对搜索空间进⾏剪枝，这样便减少了重复计算，降低了时间复杂度。
滑动窗口是一种在数组或字符串上解决问题的常见技巧。
它通常适用于需要在给定范围内查找最大或最小值的问题，或需要确定是否存在一种子数组或子字符串满足一定条件的问题。
在Java中，我们可以使用滑动窗口来解决各种问题，但是编写滑动窗口算法可能会比较繁琐和复杂。
为了简化开发人员的工作，我们可以编写一个工具类，封装滑动窗口算法的实现过程，以便在解决问题时轻松调用。
在Java中，我们可以使用以下方法来实现一个滑动窗口工具类：1. 确定滑动窗口的初始状态：- 我们首先需要确定滑动窗口的起始位置和结束位置，通常使用两个指针来表示。
这些指针可以指向数组或字符串的索引位置。
2. 确定滑动窗口的移动规则：- 我们需要确定滑动窗口在移动时的规则，包括何时移动起始指针和结束指针，以及如何更新滑动窗口内的状态。
这些规则通常取决于具体的问题需求，可以是滑动窗口内的值总和达到一定条件，或者满足特定条件的子字符串长度等。
3. 编写滑动窗口的具体实现：- 我们可以将滑动窗口的实现过程封装成一个方法，以便在解决问题时调用。
在该方法中，我们可以使用一个循环来不断移动滑动窗口，根据移动规则来更新滑动窗口内的状态，并根据具体问题需求返回特定的结果。
4. 考虑边界条件和异常情况：- 在编写滑动窗口工具类方法时，我们需要考虑各种边界条件和异常情况，例如数组或字符串为空时的处理方式，指针越界时的处理方式等。
通过以上方法，我们可以编写一个滑动窗口工具类，其中包含一个方法来实现滑动窗口算法的具体实现过程。
这样一来，当我们需要解决问题时，只需调用该工具类的方法即可，无需重复编写滑动窗口算法的实现过程，能够大大提高开发效率。
在使用滑动窗口工具类时，我们需要注意以下几点：1. 确保滑动窗口的初始状态和移动规则符合问题需求；2. 注意处理边界条件和异常情况，以确保方法的健壮性；3. 根据具体问题需求调用滑动窗口工具类的方法，并根据返回结果进行后续处理。
通过以上方法，我们可以编写一个高质量、流畅易读、结构合理的滑动窗口工具类方法，帮助我们更高效地解决各种问题。
⼀种基于滑动窗⼝的流数据聚类算法第⼀个以流数据为分析对象的聚类算法是由Sudipto Guha 等提出的STREAM 算法。
这种算法根据分治原理，使⽤⼀个不断迭代的过程实现有限空间对数据流进⾏K-means聚类，但该算法⽆法处理演化的数据流。
Aggarwal 在总结上述⽅法本质缺陷的基础上提出了⼀个数据流聚类框架Clustream[5]，其核⼼思想是将聚类过程分为在线和离线两个阶段。
在线部分的任务是存储数据流的汇总结果，⽣成⼀种称为微聚类的信息存储结构，并按⾦字塔式时间结构将中间结果进⾏保存。
离线部分既是根据⽤户指定的观察时段及聚类数量，快速⽣成聚类结果的过程。
CluStream 不⾜之处在于需要⽤户指定聚类簇数k，要求强⾏输⼊固定的聚类簇数必然影响真实的聚类形态分布。
同时，算法是以K-means 算法为基础，对⾮凸形状聚类效果不好，⽆法发现任意形状的聚类，且当噪声数据增多时，聚类质量急骤下降。
Aggarwal 等后续提出了专门针对⾼维连续属性数据流的HPStream 算法，该算法引⼊了⼦空间聚类，并提出了具有遗忘特性的聚类结构，使⽤⾼维投影技术和衰减结构来处理⾼维数据流，HPStream 算法对⾼维数据流具有很好的健壮性。
但算法中需要⽤户来指定平均聚类维数，⽤户⼀般并不具备这种领域知识，成为该算法的瓶颈。
Cao 等⼈提出了基于密度的两阶段聚类⽅法,即DenStream 算法，该算法仍然沿⽤CluStream 算法中的双层结构，创造性的引⼊了潜在微聚类簇和孤⽴点微聚类簇结构，具备对孤⽴点的分析能⼒，即随着数据流不断进化，算法可以识别在某⼀时间段有可能演变成聚类簇的孤⽴点或“潜在聚类”，从⽽更加准确的捕获真实的聚类形态。
但由于算法中采⽤全局⼀致的绝对密度作为参数，使得聚类结果对参数⼗分敏感，⽽且它不⽀持指定的时间窗⼝内实时数据流的演化分析。
受到⼴泛关注的3 类⽅法是基于⽹格的数据流聚类技术[6-9]、⼦空间聚类技术[7-9]、混合属性数据流聚类[10]，代表了当前数据流聚类研究的主流⽅向。
动态窗口法算法原理说明什么是动态窗口法算法原理？动态窗口法算法原理是一种针对海量数据处理的方法，通过设置一个固定大小的窗口，在数据流中滑动窗口并不断更新窗口内的状态，以快速计算特定问题的解。
动态窗口法算法可以大幅减少计算量，提高效率，并且不需要事先对整个数据集进行遍历。
动态窗口法算法的使用场景动态窗口法算法广泛应用于实时数据处理、流式数据分析、滑动窗口查询等场景，例如处理实时交易数据、网络流量分析、时间序列分析等。
这些场景中的数据通常是连续不断产生的，传统的遍历或聚合方法在效率和实时性上无法满足要求，而动态窗口法算法恰能满足这一需求。
动态窗口法算法步骤详解下面我们将详细介绍动态窗口法算法的步骤，分为初始化阶段和滑动更新阶段两部分。
1. 初始化阶段在初始化阶段，我们需要确定窗口的大小、定义窗口内的状态以及初始化状态的值。
窗口的大小根据具体问题来设定，可以是固定大小也可以是根据数据特征动态调整。
2. 滑动更新阶段在滑动更新阶段，我们按照窗口大小依次处理数据流中的元素。
具体步骤如下：2.1 更新状态从数据流中取出一个新的元素，并更新窗口内的状态。
状态的更新根据具体问题而定，可以是计算平均值、求和、统计频次等。
2.2 检查窗口范围检查当前窗口的范围是否超过设定的大小。
如果超过，需要对窗口内的状态进行调整，保持窗口的大小不变，并去除掉窗口最旧的元素。
2.3 处理结果根据窗口内的状态计算所需的结果。
这个结果可以是每次窗口滑动时的统计信息，也可以是在滑动过程中得到的特定结果，如最大值、最小值等。
以上就是动态窗口法算法的基本步骤。
通过不断滑动窗口并更新内部状态，我们可以及时获得问题的结果，避免了对整个数据集的遍历或聚合操作，从而提高了计算效率。
动态窗口法算法的优缺点动态窗口法算法具有以下优点：1. 高效性：由于只需要维护窗口内的状态，可以大幅减少计算量，提高处理效率。
2. 实时性：能够及时处理实时数据流，实现实时计算和分析。
常用的限流算法
限流算法是指一种限制流量的技术，主要用于保护系统不被过多的请求拖垮，确保系统的稳定性和可靠性。
常用的限流算法有以下几种：
1. 令牌桶算法：该算法的原理是将请求看作令牌，服务器每隔一段时间会产生一定数量的令牌，并存入令牌桶中。
每次请求需要从令牌桶中取出一个或多个令牌，如果令牌桶中没有足够的令牌，则该请求被拒绝。
该算法的优点是支持突发流量，可以应对短时间内请求量的突然增加。
2. 计数器算法：该算法的原理是对每个用户或客户端设置一个计数器，计数器的初始值为0，每次请求到达时，计数器加1，当计数器的值超过一定的阈值时，后续的请求被拒绝。
该算法简单易懂，适用于请求量比较稳定的场景。
3. 漏桶算法：该算法的原理是将请求看作水滴，服务器像一个漏桶一样处理请求，每次请求到达时，将其放入漏桶中，服务器以固定的速度处理请求，如果漏桶已满，则后续的请求被拒绝。
该算法优点是平滑处理请求，不会因为短时间内大量请求而拖垮系统。
4. 滑动窗口算法：该算法的原理是将请求看作窗口里的点，服务器设置一个固定大小的窗口，每次请求到达时，将其放入窗口中，当窗口中的请求超过一定的阈值时，后续的请求被拒绝。
该算法支持滑动窗口的方式，可以动态调整阈值，
适用于请求量波动较大的场景。
总的来说，不同的限流算法适用于不同的场景，选择合适的算法可以更好地保护系统。
算法学习-滑动窗⼝滑动窗⼝算法1. 概念滑动窗⼝是⼀种基于双指针的⼀种思想，两个指针指向的元素之间形成⼀个窗⼝。
2.分类窗⼝有两类，⼀种是固定⼤⼩类的窗⼝，⼀类是⼤⼩动态变化的窗⼝。
3.应⽤场景利⽤滑动窗⼝获取平滑的数据，如⼀段连续时间的数据平均值，能够有更好的稳定性，如温度监测。
什么情况可以⽤滑动窗⼝来解决实际问题呢？⼀般给出的数据结构是数组或者字符串求取某个⼦串或者⼦序列最长最短等最值问题或者求某个⽬标值时该问题本⾝可以通过暴⼒求解4.算法思想1. 在序列中使⽤双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为⼀个窗⼝。
2. 先不断地增加 right 指针扩⼤窗⼝ [left, right]，直到窗⼝中的序列符合要求。
3. 此时，停⽌增加 right，转⽽不断增加 left 指针缩⼩窗⼝ [left, right]，直到窗⼝中的序列不再符合要求。
同时，每次增加 left前，都要更新⼀轮结果。
4. 重复第 2 和第 3 步，直到 right 到达序列的尽头。
思路其实很简单：第 2 步相当于在寻找⼀个可⾏解，然后第 3 步在优化这个可⾏解，最终找到最优解。
左右指针轮流前进，窗⼝⼤⼩增增减减，窗⼝不断向右滑动。
5.算法模板(1)单循环--适⽤于固定窗⼝⼤⼩def template():# 初始化滑动窗⼝两端left = right = 0# 序列及序列长度seq, seq_len = xx, xx# 滑动窗⼝序列slide_win = []# 结果值rst = xxwhile right < seq_len:slide_win.append(seq[right])# 还没找到⼀个可⾏解if not avaliable(slide_win):# 扩⼤窗⼝right += 1else:# 找到⼀个可⾏解，更新结果值rst = update()# 缩⼩窗⼝left += 1(2)双层循环 -- 适⽤于动态窗⼝def template():# 初始化滑动窗⼝两端# 序列及序列长度seq, seq_len = xx, xx# 滑动窗⼝序列slide_win = []# 结果值rst = xxwhile right < seq_len:slide_win.append(seq[right])# 还没找到⼀个可⾏解if not avaliable(slide_win):# 扩⼤窗⼝right += 1continue# 循环更新可⾏解while avaliable(slide_win):# 找到⼀个可⾏解，更新结果值rst = update()# 缩⼩窗⼝left += 16.实战代码(1) 固定窗⼝vector<int> findAnagrams(string s, string p){//窗⼝:字母和p相同的字串窗⼝⼤⼩ p的长度//当窗⼝⼩于n 则first++//当窗⼝⼤于等于n 则second++////异位词即字母出现相同vector<int> ans=vector<int>(26,0);vector<int> ver=vector<int>(26,0);vector<int> res;for(int i = 0 ;i < p.size();i++){ans[p[i]-'a']++;}for(int i = 0;i <s.size();i++ ){ver[s[i]-'a']++;if(i >= p.size()) ver[s[i-p.size()]-'a']--;if(ans == ver) res.push_back(i-p.size()+1);}return res;}(2) 动态窗⼝string minWindow(string s, string t){//窗⼝:s字串的⼦串能覆盖住t 窗⼝⼤⼩⾄少为t.length()//当窗⼝⼩于 t.length() 则first++//当窗⼝⼤于等于t.length() 若满⾜则second++//覆盖即 s的字符出现数 >= p的字符出现数//当使⽤unordermap 来存储<字符,字符出现次数>string result;if(s.empty()||t.empty()) return result;unordered_map<char,int> map;unordered_map<char,int> window;for(char c:t){map[c]++;}int minlength = INT_MAX;int lettercount =0;for(int slow = 0 ,fast =0;fast < s.length();fast++){char c =s[fast];if(map.find(c) != map.end())//若此字符是⽬标串出现过的字符 {if(window[c]<= map[c])lettercount++;//第⼀次遇到时让count++}if(lettercount >= t.length())//全部的字符已经覆盖到了{while(map.find(s[slow])==map.end() || window[slow]> map[slow]) //slow的字符没在⽬标串中出现的字母或者字符出现次数多与需要//在满⾜基恩本条件下缩⼩窗⼝{window[s[slow]]--;slow++;}if((fast - slow + 1 )< minlength){minlength = fast-slow+1;result = s.substr(slow,minlength);}}}return result;}。
滑动窗口算法是一种常用的算法技术，用于处理连续子数组或子序列的问题。
其基本原理是通过维护一个固定大小的窗口，来处理连续数据流或数组中的子序列。
下面是滑动窗口算法的基本原理：
初始化窗口大小和起始位置：
设置窗口的大小，即所需的连续子序列的长度。
确定起始位置，通常为数组或数据流的开头。
移动窗口：
将窗口从起始位置开始滑动，每次滑动一个位置。
处理当前窗口：
在每个窗口位置，执行特定的操作或处理。
这可能涉及计算子序列的和、平均值、最大值、最小值等，或者进行其他特定的逻辑操作。
更新结果：
根据当前窗口的处理结果，更新所需的输出或结果。
调整窗口大小：
根据问题要求和具体情况，可能需要调整窗口的大小。
例如，在找到满足特定条件的子序列后，可以调整窗口大小以寻找下一个符合条件的子序列。
继续滑动窗口：
重复步骤2至步骤5，直到窗口滑动到数据流或数组的末尾。
滑动窗口算法的优点是它可以在线性时间内解决问题，并且可以减少不必要的计算，因为它只处理每个元素一次。
它在解决连续子数组求和、找到最长连续子串等问题中非常有用。
MATLAB滑动窗口算法代码一、概述MATLAB是一种强大的数学建模和仿真软件，在信号处理和图像处理领域有着广泛的应用。
滑动窗口算法是一种常见的信号处理技术，可以用来进行数据的平滑处理、特征提取等操作。
本文将介绍如何使用MATLAB来实现滑动窗口算法，并给出相应的代码示例。
二、滑动窗口算法原理滑动窗口算法在信号处理和图像处理中有着广泛的应用。
其基本原理是将待处理的数据分成窗口，然后依次移动窗口并对每个窗口中的数据进行相应的处理。
这样可以实现对数据的局部处理，常见的应用包括平滑滤波、特征提取等。
三、MATLAB实现滑动窗口算法在MATLAB中，可以使用循环结构和向量化操作来实现滑动窗口算法。
下面将给出一个简单的示例，演示如何实现滑动窗口平均滤波算法。
1. 定义输入数据假设我们有一个长度为N的输入信号x，我们要对其进行滑动窗口平均滤波处理。
```MATLABx = randn(1,100); 生成一个长度为100的随机信号N = length(x); 获取信号长度```2. 定义窗口大小和滑动步长我们需要定义滑动窗口的大小和滑动步长。
在本例中，我们将窗口大小设为10，滑动步长设为1。
```MATLABwindowSize = 10; 窗口大小stepSize = 1; 滑动步长```3. 实现滑动窗口平均滤波算法我们可以使用循环结构来实现滑动窗口平均滤波算法，具体代码如下所示。
```MATLABy = zeros(1,N); 初始化输出信号for i = 1:N-windowSize+1y(i) = mean(x(i:i+windowSize-1)); 对当前窗口进行平均滤波处理end```4. 绘制结果我们可以绘制原始信号和滤波后的信号，以便进行对比。
```MATLABt = 1:N; 时间索引plot(t,x,'b',t(1:N-windowSize+1),y(1:N-windowSize+1),'r'); 绘制原始信号和滤波后的信号legend('原始信号','滤波后的信号');```四、总结本文介绍了如何使用MATLAB实现滑动窗口算法，并给出了一个简单的滑动窗口平均滤波算法的示例。
mallet算法原理
Mallet算法是一种基于滑动窗口的滤波算法，适用于信号降噪和滤波。
其
基本思想是将输入信号分成一系列重叠的窗口，然后通过对每个窗口应用滤波器来获得输出信号。
具体步骤如下：
1. 定义窗口大小和重叠率：首先，需要确定窗口的大小和窗口之间的重叠率。
窗口大小决定了每个窗口中包含的信号点数，而重叠率决定了相邻窗口之间的重叠部分。
2. 分割输入信号：将输入信号分割成一系列重叠的窗口。
每个窗口的大小由步骤1中定义的窗口大小确定，而窗口之间的重叠部分由重叠率确定。
3. 应用滤波器：对于每个窗口，应用所选的滤波器来滤波窗口中的信号。
滤波器可以是任何合适的滤波算法，例如FIR滤波器或IIR滤波器。
4. 重叠相加：将滤波后的窗口在重叠部分进行相加，以获得最终的输出信号。
通过重叠相加的操作，保证了输出信号的平滑过渡，减少了窗口分割带来的伪像。
此外，Mallet算法还可以用于执行离散小波变换，这是一种信号的分解方法。
通过使用两个互补的滤波器产生A和D两个信号，其中A表示近似值，D表示细节值。
在小波分析中，趋势项值是在按照大缩放因子进行变换时产生的系数，此系数值是低频分量系数。
而细节项值是在按照小缩放因子进行
变换时产生的系数，此系数值是高频分量系数。
离散小波变换可以表示成由低通滤波器和高通滤波器组成的一棵树。
原始信号通过这样一组低高通滤波器进行分解叫做一次分解，同样的也可以进行多次分解（只进行一次分解成为一级分解）。
以上信息仅供参考，如有需要建议查阅相关文献或咨询专业人士。
滑动窗口算法1. 滑动窗口算法滑动窗口算法工作过程如下。
首先，发送方为每1帧赋一个序号（sequence number），记作S e q N u m。
现在，让我们忽略S e q N u m 是由有限大小的头部字段实现的事实，而假设它能无限增大。
发送方维护3个变量：发送窗口大小（send window size），记作S W S，给出发送方已经发送但未确认的帧数的上界；L A R表示最近收到的确认帧（last acknowledgement re c e i v e d）的序号；L F S表示最近发送的帧（last frame sent）的序号，发送方还维持如下的不变式：LAR-LFR≤RWS当一个确认到达时，发送方向右移动L A R，从而允许发送方发送另一帧。
同时，发送方为所发的每个帧设置一个定时器，如果定时器在A C K到达之前超时，则重发此帧。
注意：发送方必须存储最多S W S个帧，因为在它们得到确认之前必须准备重发。
接收方维护下面3个变量：接收窗口大小（receive window size），记为RW S/* 对应允许接受的数据包*/，给出接收方所能接收的无序帧数目的上界；L A F表示可接收帧（largest acceptable frame）的序号；L F R表示最近收到的帧（last frame re c e i v e d）的序号。
接收方也维持如下不变式：LFS-LAR≤SWS(NFE为等待下一帧的序号)当一个具有顺序号S e q N u m的帧到达时，接收方采取如下行动：如果S e q N u m≤L F R或S e q N u m > L A F，那么帧不在接收窗口内，于是被丢弃；如果L F R＜Se q N u m≤L A F，那么帧在接收窗口内，于是被接收。
现在接收方需要决定是否发送一个A C K。
设SeqNumToACK表示未被确认帧的最大序号，则序号小于或等于SeqNumToACK的帧都已收到。
即使已经收到更高序号的分组，接收方仍确认SeqNumToACK的接收。
这种确认被称为是累积的（c u m u l a t i v e）。
然后它设置L F R = S e q N u m To A c k，并调整L A F = L F R + RW S。
例如，假设L F R= 5（即，上次接收方发送的A C K是为了确认顺序号5的），并且RWS = 4。
这意味着L A F = 9。
如果帧7和8到达，则存储它们，因为它们在接收窗口内。
然而并不需要发送A C K，因为帧6还没有到达。
帧7和8被称为是错序到达的。
（从技术上讲，接收方可以在帧7和8到达时重发帧5的A C K。
）如果帧6当时到达了（或许它在第一次丢失后又重发从而晚到，或许它只是被延迟了），接收方确认帧8，L F R置为8，L A F置为1 2。
如果实际上帧6丢失了，则出现发送方超时，重发帧6。
我们看到，当发生超时时，传输数据量减少，这是因为发送方在帧6确认之前不能向前移动窗口。
这意味着分组丢失时，此方案将不再保证管道满载。
注意：分组丢失时间越长，这个问题越严重。
注意，在这个例子中，接收方可以在帧7刚一到达时就为帧6发送一个认帧N A K（negative acknowl edgment）。
然而，由于发送方的超时机制足以发现这种情况，发送N A K反而为发送方增加了复杂性，因此不必这样做。
正如我们已提到的，当帧7和8到达时为帧5发送一个额外的A C K是合理的；在某些情况下，发送方可以使用重复的A C K作为一个帧丢失的线索。
这两种方法都允许早期的分组丢失检测，有助于改进性能。
关于这个方案的另一个变种是使用选择确认（selective acknowledgements）。
即，接收方能够准确地确认那些已收到的帧，而不只是确认按顺序收到最高序号的帧。
因此，在上例中，接收方能够确认帧7、8的接收。
如果给发送方更多的信息，就能使其较容易地保持管道满载，但增加了实现的复杂性。
发送窗口大小是根据一段给定时间内链路上有多少待确认的帧来选择的；对于一个给定的延迟与带宽的乘积，S W S是容易计算的。
另一方面，接收方可以将RW S设置为任何想要的值。
通常的两种设置是：RW S= 1，表示接收方不存储任何错序到达的帧；RW S=S W S，表示接收方能够缓存发送方传输的任何帧。
由于错序到达的帧的数目不可能超过S W S个，所以设置RWS >S W S没有意义。
2. 有限顺序号和滑动窗口现在我们再来讨论算法中做过的一个简化，即假设序号是可以无限增大的。
当然，实际上是在一个有限的头部字段中说明一个帧的序号。
例如，一个3比特字段意味着有8个可用序号0 ~ 7。
因此序号必须可重用，或者说序号能回绕。
这就带来了一个问题：要能够区别同一序号的不同次发送实例，这意味着可用序号的数目必须大于所允许的待确认帧的数目。
例如，停止等待算法允许一次有1个待确认帧，并有2个不同的序号。
假设序号空间中的序号数比待确认的帧数大1，即S W S ≤ M A a x S e q N u m -1 ，其中M a x Seq N u m 是可用序号数。
这就够了吗？答案取决于RW S 。
如果RW S = 1，那么MaxSeqNum≥SWS+1是足够了。
如果RW S等于S W S，那么有一个只比发送窗口尺寸大1的M a x S e q N u m是不够的。
为看清这一点，考虑有8个序号0 ~ 7的情况，并且S W S = RW S = 7。
假设发送方传输帧0 ~ 6，并且接收方成功接收，但A C K丢失。
接收方现在希望接收帧7，0 ~ 5，但发送方超时，然后发送帧0 ~ 6。
不幸的是，接收方期待的是第二次的帧0 ~ 5，得到的却是第一次的帧0 ~ 5。
这正是我们想避免的情况。
结果是，当RW S = S W S时，发送窗口的大小不能大于可用序号数的一半，或更准确地说，SWS<(Maxseqnum+1)/2直观地，这说明滑动窗口协议是在序号空间的两半之间变换，就像停止等待协议的序号是在0和1之间变换一样。
唯一的区别是，它在序号空间的两半之间连续滑动而不是离散的变换。
注意，这条规则是特别针对RW S = S W S的。
我们把确定适用于RW S和S W S的任意值的更一般的规则留做一个练习。
还要注意，窗口的大小和序号空间之间的关系依赖于一个很明显以至于容易被忽略的假设，即帧在传输中不重新排序。
这在直连的点到点链路上不能发生，因为在传输过程中一个帧不可能赶上另一个帧。
然而，我们将在第5章看到用在一个不同环境中的滑动窗口算法，并且需要设计另一条规则。
3. 滑动窗口的实现下面的例程说明我们如何实现滑动窗口算法的发送和接收的两个方面。
该例程取自一个正在使用的协议，称为滑动窗口协议S W P （Sliding Window Pro t o c o l）。
为了不涉及协议图中的邻近协议，我们用H L P（高层协议）表示S W P上层的协议，用L I N K（链路层协议）表示S W P下层的协议。
我们先定义一对数据结构。
首先，帧头部非常简单：它包含一个序号（S e q N u m）和一个确认号（ A c k N u m）。
它还包含一个标志（ F l a g s）字段，表明帧是一个A C K帧还是携带数据的帧。
其次，滑动窗口算法的状态有如下结构。
对于协议发送方，该状态包括如上所述的变量L A R和L F S，以及一个存放已发出但尚未确认的帧的队列（s e n d Q）。
发送方状态还包含一个计数信号量（counting semaphore），称为s e n d Wi n d o w N o t F u l l。
下面我们将会看到如何使用它，但一般来说，信号量是一个支持s e m Wa i t和s e m S i g n a l操作的同步原语。
每次调用S e m S i g n a l，信号量加1，每次调用S e m Wa i t，信号量减1。
如果信号量减小，导致它的值小于0，那么调用进程阻塞（挂起）。
一旦执行了足够的s e m S i g n a l操作而使信号量的值增大到大于0，在调用s e m Wa i t的过程中阻塞的进程就允许被恢复。
对于协议的接收方，如前所述，该状态包含变量L F R ，加上一个存放已收到的错序帧的队列（r e c v Q）。
最后，虽然未显示，发送方和接收方的滑动窗口的大小分别由常量S W S和RW S表示。
S W P的发送方是由s e n d S W P过程实现的。
这个例程很简单。
首先，s e m Wa i t使这个进程在一个信号量上阻塞，直到它可以发另一帧。
一旦允许继续，s e n d S W P设置帧头部中的顺序号，将此帧的拷贝存储在发送队列（s e n d Q）中，调度一个超时事件以便处理帧未被确认的情况，并将帧发给低层协议。
值得注意的一个细节是刚好在调用m s g A d d H d r之前调用s t o r e _ s w p _ h d r。
该例程将存有S W P头部的C语言结构（s t a t e - > h d r）转化为能够安全放在消息前面的字节串（h b u f）。
该例程（未给出）必须将头部中的每一个整数字段转化为网络字节顺序，并且去掉编译程序加入C语言结构中的任意填充。
7 . 1节将详细讨论字节顺序的问题，但现在，假设该例程将多字整数中最高有效位放在最高地址字节就足够了。
这个例程的另一个复杂性是使用s e m Wa i t 和s e n dW i n d o w N o t F u l l 信号量。
S e n dWi n d o w N o t F u l l被初始化为发送方滑动窗口的大小S W S（未给出这一初始化）。
发送方每传输一帧，s e m Wa i t操作将这个数减1，如果减小到0，则阻塞发送方进程。
每收到一个A C K，在d e l i v e r S W P中调用s e m S i g n a l操作（见下面）将此数加1，从而激活正在等待的发送方进程。
在继续介绍S W P的接收方之前，需要调整一个看上去不一致的地方。
一方面，我们说过，高层协议通过调用s e n d操作来请求低层协议的服务，所以我们就希望通过S W P发送消息的协议能够调用s e n d（S W P, p a c k e t）。
另一方面，用来实现S W P的发送操作的过程叫做s e n d S W P，并且它的第一个参数是一个状态变量（S w p S t a t e）。
结果怎样呢？答案是，操作系统提供了粘结代码将对s e n d的一般调用转化为对s e n d S W P的特定协议调用的粘结代码。
这个粘结代码将s e n d的第一个参数（协议变量S W P）映射为一个指向s e n d S W P的函数指针和一个指向S W P工作时所需的协议状态的指针。
