一种极值查找算法在区域自动站资料质量控制中的应用

杨远恒，田 兰，卜英竹，邹 蓓

(贵州省气象信息中心，贵州 贵阳 550002)

一种极值查找算法在区域自动站资料质量控制中的应用

杨远恒，田 兰，卜英竹，邹 蓓

(贵州省气象信息中心，贵州 贵阳 550002)

在区域自动气象站两要素资料的质量控制研究中，根据两要素资料的特点，实现一种极值查找算法，快速的定位极值数据，提高查找的效率。该文着重分析该查找算法的实现，以供探讨。

区域自动站质量控制;极值查找;算法

1 引言

在区域自动气象站两要素资料的质量控制研究中，利用历史极值检查方法进行实时资料质量控制时，需要将实时观测值与历史极端值进行比较，以便过滤出可疑值。因此，在进行实时质量控制时，需要在极端历史资料文件中查找到极端历史值。一般方法是将每一个台站的实时观测值和所有台站的历史极值进行逐一的比较，以便查找到台站的历史极值。这种方法处理效率较低，不能满足质量控制实时业务需求。为保证两要素资料质量控制的实时处理，避免因查找极端历史值耗时，本文根据两要素资料的特点，实现一种数据查找算法，以提高历史极值检查的效率。

2 算法设想

由于区域两要素站是近年来才新建的台站，其历史极端要素值是根据常规地面观测站的历史极端要素值，通过两要素台站与地面观测站之间区域的对应关系，实现两要素台站极值的初始化。在新生成的每个两要素极值文件中，每个台站对应一条历史极值记录，例如，月极端最低温度记录如下：

R1101-78-66-35 1 76 104 121 142 81 34-24-66

其中，每条极值记录包含了台站编号(如R1101)以及1—12月的极端值。

两要素台站编号是5位数编码，其中，“R”是固定标识，R后第1位数字代表地区、第2位数字代表县、第3、4位数字代表该县的第几个两要素站。

按照台站编码的规则，可以将台站编号(staID)分别按照“地区级编码”和“县级编码”分成不同的台站类别(stasort)。若按照“地区级编码”，贵阳地区台站类别为“R1＊＊＊”，遵义地区的台站类别为“R2＊＊＊”，等等。同理，若按照“县级编码”，如贵阳地区又可以划分为8种台站类别：“R11＊＊、R12＊＊、R13＊＊、R14＊＊、R15＊＊、R16＊＊、R17＊＊、R18＊＊”，其他地区依次类推。因此，当初始化两要素极值文件时，首先，每条极值记录以台站编号为索引，然后根据“县级编码”进行台站类别归类，每个台站类别的台站编号再按照第3、4位数字进行排序，同时存储到文件中，为实现历史极值检查算法做前期准备。

通常，在资料的处理过程中，根据记录的台站编号，采取遍历极值记录的方式就可以查找到极值记录，这种查找方式使得每一条实时记录都需要循环遍历极值数组。随着两要素台站的不断新建，处理两要素资料的数据量不断加大，为了提供更快更好的气象服务，两要素资料的质量控制处理需要具备较高的实时性，采取常规的查找方式，增加了算法的时间复杂度，在一定程度上降低了资料质量控制处理的实时性。

为了能够减少频繁循环遍历极值记录，比较快的查找到极值，考虑对极值记录进行预处理，通过预处理的辅助帮助来实现快速定位极值的目的。也就是说，从极值文件中读取记录初始化极值数组时，预先对极值记录按台站类别进行统计，结果存放在辅助数组中，当查找极值时，由实时资料记录的台站编号，通过辅助数组计算，就可以缩小在极值数组中查找的范围，提高了查找效率。并且存在一种特殊情况，如果台站编号的第3、4位数字编码是顺序递增编码，那么可以直接计算出该台站的历史记录的准确位置，从而实现更加快捷的查找到极值记录。

3 具体实现

第一步，预处理实现辅助数组的初始化。在初始化极值数组(extremum)的同时，按照“县级编码”统计出每种台站类别的台站个数，并存放到一个辅助数组(assistant)中。首先获得极值记录中的staID所属的台站类别，如果当前记录的staID所属的台站类别(curstasort)不等于前一条记录台站类别(prestasort)，则表明前一个类别的台站个数统计结束，开始统计下一个台站类别的台站个数。

第二步，准确查找到极值数据。当接收到实时数据记录时，根据记录的staID，准确计算出对应的极值在极值数组中的位置。例如：staID为R1303，通过辅助数组可以得知，在台站类别“R13＊＊”之前存在“R11＊＊、R12＊＊”2个台站类别，“R13*＊”类别的初始位置(INITPOS)为前2个类别的统计数之和，即：

INITPOSR13＊＊=INITPOSR11＊＊+INITPOSR12＊＊

考虑特殊情况：如果staID的第3、4位数字编码是顺序递增，那么可以知道，“R1303”在“R13＊＊”类别的位置是在第3个：N3，则“R1303”在极值数组中的位置POS为：

其中x为staID在某一类台站类别中的第几个台站个数。当计算出具体的位置，那么可以直接从数组中取出相应的极值，达到了快速的找到极值的目的，优化了程序的运行。

但是，如果两要素的台站编号的第3、4位编码不是按照顺序递增编码，而是随机编码，通过以上计算就不能确定该台站在该类别中的位置，而需要在同一个类别中，通过极值记录的台站编号(ext-StaID)和当前记录的台站编号(curStaID)判断而获得极值。

通过判断，缩小了查找极值数据的范围，同样实现了快速的定位极值的目的，优化了程序的运行。

4 总结

通过辅助数组的方式查找气象极值记录，其辅助数组和极值记录一一对应，当极值文件中的记录发生变化时，相应的辅助数组中统计数也会发生变化。同时，该算法在实现查找极值的过程中降低了算法的时间复杂度，但增加一个辅助数组的开销，增加了算法的空间复杂度。在区域自动站实时质量控制处理时，能够简单、快速的查找到极值记录，提高了两要素实时资料质量控制处理的效率，能够满足区域自动站实时质量控制实时业务需求。

［1］ 吴伟民，严蔚敏.数据结构(C语言版)［M］.北京：清华大学出版社，2009.

P413

B

1003-6598(2011)03-0050-02

2010-06-11

杨远恒(1979-)，女，工程师，主要从事气象数据处理工作。