>>>  新興科技、社會發展等人文科學探討  >>>

簡體     傳統

---

　　作者 張進，武漢大學圖書情報學院教授，武漢，430072；
　　 陳遠，武漢大學圖書情報學院講師，武漢，430072。
　　關鍵詞 脫機批處理系統算法 聯機檢索算法 比較研究
　　提要 文章從算法角度對聯機情報檢索系統與脫機批處理系統進行了討論，分析了它們在對邏輯非算子的處理、檢索周期、處理最佳終止點、比較時主次方、文檔結構，以及提問邏輯式機內等價形式對效率影響等方面的差異。
　　 ＊ ＊ ＊
　　脫機檢索系統與聯機檢索系統是情報檢索系統的兩大主要類型。在了解兩大類型檢索系統的算法運作及原理的同時，從算法處理角度對它們進行對比性分析研究，這對從理論上全面掌握其工作原理以及于實踐中將其進一步改進，都是極有價值的。
　　雖然脫機檢索系統與聯機檢索系統都是對用戶提問式進行處理，并給用戶提供命中文獻結果，但由于二者目的不同，處理對象的數據結構及內部處理機制也不同。為了加深對兩大檢索系統算法的本質理解，我們抽出其核心部分，進行對比分析。
　　1.兩種算法對提問式的處理不同。我們知道，任意一個提問邏輯式都可以經過一定的變換轉化為標準的析取范式：A=B[,1]+B[,2]+…B[,i]+…B[,n](B[,i],i≤n是一子合取式）。
　　脫機批處理檢索算法，無論是菊池敏典算法，還是歐美算法，或是改進SDI算法，在算法的執行過程中均是以提問詞與文獻記錄中標引詞進行匹配。只要提問表達式中有一個子合取式成立，即該子合取式中各檢索詞與一個文獻記錄中的標引詞分別匹配成功，那么，算法就可以中止。這是因為在算法的一個處理周期中，它只是鑒別一個文獻記錄是否滿足該提問式，而對聯機檢索算法來講，它的每一個處理周期中需要確定的則是所有數據庫中滿足提問式的一批文獻記錄。因此，它必須對提問邏輯式中所有可能滿足條件的子合取式進行處理，以確定一組文獻記錄。
　　2.算法執行過程中最佳終止點的確定問題。脫機批處理菊池敏典算法展開表技術的一個最大特點，就是在算法執行中對提問式中各提問詞的匹配處理一旦滿足終止條件，決不多做任何多余的匹配工作，立即終止算法的執行，輸出結果。正如前面所指出的那樣，一旦有一個子合取式成立，再對其它子合取式中檢索提問詞的繼續匹配處理就是多余的。因此，在脫機批處理算法中存在著匹配過程最佳終止點的選定問題，這是對脫機批處理算法的一個特殊要求，聯機檢索算法不存在這種問題。
　　3.算法的掃描執行次數問題。在脫機批處理系統中，如果被檢索的順序文獻數據庫中有N篇文獻記錄，那么，算法將執行N次。這是因為脫機批處理算法在一個周期的執行過程中，提問文檔每次僅為一個文獻記錄中的標引詞進行匹配處理，以決定該文獻記錄的取舍。聯機檢索算法在對提問式處理時，僅執行一次，每次不是針對一篇文獻記錄。這是因為倒排文檔中，每個檢索提問詞后所附屬的文獻地址集合，是針對整個文獻數據庫的，一次性處理后，就可以決定最終命中文獻集合。
　　4.檢索時主次比較方的確定問題。在檢索時，提問文檔中的提問詞與文獻主文檔中標引詞進行比較，這里存在著比較雙方的主次問題。在脫機批處理算法中，既可以以提問文檔為比較的主方，文獻主文檔為比較的次方；也可以以文獻主文檔為主方，以提問文檔為次方。由于提問文檔和文獻主文檔在比較過程中所處的主次地位不同，由此可以劃分為歐美算法流派和東方算法流派（這主要是指菊池敏典算法）。在聯機檢索執行過程中，只能以提問文檔一方為比較時的主方，倒排文檔一方為次方。聯機檢索在比較時文獻主文檔一方就是整個倒排文檔，其入口詞的數目是相當大的一個數N。假設以倒排文檔為比較時的主方，提問文檔一方為次方，并且同時假設提問文檔中有m個提問詞，顯然有m＜＜N次。若按順序搜查找方法，對整個提問式的處理要比較m×N次。以提問文檔為主，由于整個倒排文檔的入口詞已進行排序處理，在搜集時可以用二分查找算法，其比較次數為m×log[,2]N。兩者比較起來，顯然后者比較次數要少得多。這就是為什么聯機檢索算法中以提問文檔為主方的原因。脫機批處理算法處理中，算法每執行一個處理周期，提問文檔僅與一個文獻記錄中的標引詞進行比較，它們的數量是有限的，比起整個文獻數據庫的文獻量要小得多。因此，以提問文檔或文獻主方檔中任何一方作為比較時的主方都不妨大局。
　　5.提問式中提問詞倒排文檔的建立問題。在脫機批處理算法的執行過程中，提問式往往是成批的。在各提問式中很可能存在相同的提問詞。無論是以提問文檔還是以文獻主文檔為比較時的主方，建立這樣的提問詞倒排文檔，可以減少提問詞與文獻標引詞的匹配次數，提高算法效率。聯機檢索軟件一般只處理一個提問式，并且對各提問詞是順序執行的，沒有建立提問詞倒排文檔的必要。
　　6.為了提高查找效率，聯機檢索的主文檔——倒排文檔，由于詞最大，往往配有字順索引，這樣做雖然用去了一些空間，但可大大提高查找速度。脫機檢索系統沒有建立這種索引的必要。這是因為如果要建立這樣的索引，必須給每篇文獻記錄中的標引詞建立索引，建立這樣的索引對提高速度作用不十分大，相比之下，又占用大量空間，顯然是不合算的，故一般情況下脫機檢索系統的主文檔各記錄內數據不建索引。
　　7.文獻文檔結構的差異。脫機檢索系統中的文獻組織結構是順排結構。它以每一篇文獻為組織信息的單元。在一個文獻記錄之下，按一定方式將描述該文獻內容特征、外表特征的所有標引項集中加以管理。而在聯機檢索系統中，每篇文獻下各標引詞分散在數據庫中各處加以管理。在這樣的結構下，按每一個標引詞為組織信息的基本單元，在每一個有檢索意義的標引詞后，附屬著所有相關文獻號，即文獻是按某一特征加以集中的。
　　8.兩種檢索系統對提問邏輯式格式限制不同。脫機檢索系統和聯機檢索系統均采用布爾邏輯作為提問表達的手段，然而兩者在使用布爾邏輯作為信息提問表達手段時，均有一定的局限，不能完全等同于布爾邏輯。一般情況下，脫機檢索系統在使用邏輯算子時，邏輯非只能作用在提問詞上，不能作用在子表達式上。
　　聯機檢索系統對邏輯非的使用也有一定的限制，它不允許邏輯非以及它所作用的因子作為析取因子出現在提問式中。例如：A+NOTB+C是不允許的；有的系統不允許邏輯非以及它所作用的因子出現在提問式的開頭。例如：NOTA*B*C，上式必須轉化為B*NOTA*C或B*C*NOTA后方能處理。
　　9.兩種檢索算法處理對象的范圍不同。從宏觀上看，脫機批處理算法在整個算法執行完畢以后，對順排文檔中所有的記錄均進行了一次查詢，其檢索結果是針對整個數據庫文獻記錄的。但是具體到脫機檢索算法的檢索過程，每一個處理周期只能確定一個特定記錄是否與一個特定提問之間滿足檢索條件，然后決定是否將該記錄放入命中文獻文檔中。這樣的處理過程從順排文檔的第一記錄開始一直進行到順排文檔的最后一個記錄為止。
　　與脫機檢索系統在此問題上的一個明顯差異是，聯機檢索算法在每一個處理周期確定一個命中文獻記錄的集合，而不是一個文獻記錄。進行操作的集合個數取決于提問表達式的提問詞個數。由于倒排文檔中每一個入口款項，也就是每一個關鍵詞所對應的文獻記錄號集合是相對于整個文獻記錄的，因此，最終的集合運算結果也是針對整個文獻記錄而言的。從這個意義上講，聯機檢索在檢索時的高效率是以建立倒排文檔的額外存貯開銷為代價的。
　　10.脫機批處理算法和聯機處理算法在將提問邏輯表達式轉化為機器等價形式的過程中，對檢索時間效率的影響是截然不同的。脫機批處理算法，無論是菊池敏典算法，還是歐美算法，從整個檢索過程上看，可以分為兩大步驟：第一步，算法將用戶提出的各種提問轉化為機器內部的等價邏輯形式，例如菊池敏典算法的提問展開表等。這些機器內部的提問邏輯式的等價形式一旦形成以后，可以長期保存，多次使用。也就是說在實際檢索開始之前，它們已經形成并存貯在計算機內部，第二步檢索時，再調用它們。因此，脫機批處理算法中將提問表達式轉化為機器內部等價形式的過程不直接影響檢索時間效率。
　　對于聯機檢索算法來講，情況則大不一樣。由于聯機檢索在檢索過程中，提問式形式的轉化以及檢索過程都是實時進行的，因此，第一步將提問式轉化為機器內部等價邏輯形式的過程和第二步利用它們進行檢索的過程是合并在一起的，兩者的時間之和便是整個檢索時間，也即將提問邏輯表達式轉化為機器內部等價形式的過程將直接影響聯機檢索的時間效率。
　　參考文獻：
　　1 張進：《對菊池敏典算法邏輯非處理的討論》，載《現代圖書情報技術》1991年第2期。
　　2 張進：《布爾邏輯與提問邏輯的差異分析》，載《圖書情報知識》1992年第4期。
　　 （責任編輯 張琳）
　　［＊］本論文受國家社會科學基金（青年）項目資助
　　
　　
　　
武漢大學學報：哲社版114-116G9圖書館學、信息科學、資料工作張進/陳遠19971997 作者：武漢大學學報：哲社版114-116G9圖書館學、信息科學、資料工作張進/陳遠19971997

網載 2013-09-10 21:33:24

驗證：