一種極值查找算法在區域自動站資料質量控制中的應用

楊遠恒，田 蘭，卜英竹，鄒 蓓

(貴州省氣象信息中心，貴州 貴陽 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-)，女，工程師，主要從事氣象數據處理工作。