苏州bb电子底薪多少

書名：自己動手寫分布式搜索引擎
作者名：羅剛
本章字?jǐn)?shù)： 1116字
更新時間： 2020-11-28 15:52:42

2.4 查詢

查詢一個詞時，將直接把對應(yīng)的文檔編號列表找出來，然后按相關(guān)度返回文檔列表。如果內(nèi)存不能完全存下所有的文檔列表，可以把用戶最經(jīng)常查詢的詞的文檔列表放到內(nèi)存中，不常查詢的詞的文檔列表放到文件中。

查詢兩個詞“NBA視頻”時，則對“NBA”這個詞對應(yīng)的文檔編號列表和“視頻”這個詞對應(yīng)的文檔編號列表做交集(Intersection)運算后返回。例如，在倒排索引表中檢索出包含“NBA”一詞的文檔列表為docList(“NBA”)=(1, 5, 9, 12)，表示這4個文檔編號的文檔含有“NBA”這個詞。包含“視頻”的文檔列表為docList(“視頻”)= (5, 7, 9, 11)。這樣同時包含“NBA”和“視頻”這兩個詞的文檔為docList(“NBA”)∩docList(“視頻”)=(5, 9)。這里的“∩”表示文檔列表集合求交集運算。

計算過程類似歸并排序，如圖2-5所示。

圖2-5 文檔列表集合求交集

多文檔列表求交集計算的示例代碼如下。

        public ArrayList<Integer> intersection(int[] docListA, int[] docListB) {
            ArrayList<Integer> ret = new ArrayList<Integer>();
            int aindex = 0;
            int bindex = 0;
            while (aindex < docListA.length && bindex < docListB.length) {
                if (docListA[aindex] == docListB[bindex]) {
                    // 找到在兩個數(shù)組中都出現(xiàn)的值
                    ret.add(docListA[aindex]);
                    aindex++;
                    bindex++;
                } else if (docListA[aindex] < docListB[bindex]) {
                    aindex++;
                } else {
                    bindex++;
                }
            }
            return ret;
        }

使用構(gòu)建好的倒排索引和文檔索引執(zhí)行搜索。

        public class IndexSearcher {
            InvertedIndex index; //倒排索引
            DocumentIndex docIndex; //文檔索引
        }

根據(jù)一個或者多個查詢詞執(zhí)行搜索，可以指定最多返回的搜索結(jié)果數(shù)量。如果不指定返回結(jié)果數(shù)量，則返回全部相關(guān)的文檔。

只需要使用浮點數(shù)就能夠區(qū)分相關(guān)文檔和不太相關(guān)的文檔，所以把score定義成float類型。

        /** 用于搜索的輔助類。支持對文檔按相關(guān)度排序 */
        public class ScoreDoc implements Comparable<ScoreDoc> {
            DocumentData doc; //文檔相關(guān)的信息，包括文檔編號等
            public float score; //表示這個文檔和查詢詞有多相關(guān)


            public ScoreDoc(DocumentData d, float b) { //構(gòu)造方法
                doc = d;
                score = b;
            }


            public int compareTo(ScoreDoc other) { // 按相關(guān)度排序
                // 返回值并不重要，保證需要的順序就行
                ScoreDoc o =  other;
                return (o.score == score) ? (0) : ((score > o.score) ? (-1) : (1));
            }


            public String toString() { //格式化輸出
                return doc.filename + ":\t" + doc.docid + "\n" + score;
            }
        }

如果要對一個大的索引庫排序，而且一個詞有很多結(jié)果，則對所有這些結(jié)果排序然后分頁顯示會很慢。

搜索時要排序，但實際上并不需要對所有的結(jié)果排序。如果只要第1頁，就只對前10個結(jié)果排序。排序是和顯示頁相關(guān)的。前10個結(jié)果是怎么得到的呢？是用最小堆得到的，須先構(gòu)建最小堆。

按相關(guān)度排序簡介如下。

用優(yōu)先隊列記錄前n 個評分最高的文檔。優(yōu)先隊列用最小堆實現(xiàn)。把前n 個評分最高的文檔放到一個最小堆中。堆雖然是一個二叉樹，但是一般使用數(shù)組實現(xiàn)，不需要元素之間的指針，如圖2-6所示。

圖2-6 二叉堆

heap[0]左邊的子元素是heap[1]，右邊的子元素是heap[2]。heap[1]左邊的子元素是heap[3]，右邊的子元素是heap[4]。heap[2]左邊的子元素是heap[5]，右邊的子元素是heap[6]。則heap[i]左邊的子元素是heap[2i+1]，右邊的子元素是heap[2i+2]。

如果要簡化計算，第一個位置可以不用，則根節(jié)點位于heap[1], heap[1]左邊的子元素是heap[2]，右邊的子元素是heap[3]。則heap[i]左邊的子元素是heap[2i]，右邊的子元素是heap[2i+1]。

因為沒有使用第0個位置，所以數(shù)組要多分配一個位置。

        private final T[] heap;


        public PriorityQueue(int maxSize) {
          int heapSize = maxSize + 1;
          heap = (T[]) new Object[heapSize];  // 沒有用heap[0]
        }

建立容量為n的最小堆，記錄前n個評分最高的文檔。對于每個和查詢詞相關(guān)的文檔，如果它比堆頂文檔的相關(guān)度更高，則刪除堆頂元素，把當(dāng)前文檔插入堆中，然后自頂向下調(diào)節(jié)，維護(hù)最小堆。如果它比堆頂文檔相關(guān)度低，則直接扔掉。遍歷完整個相關(guān)文檔集合，堆中的文檔就是最相關(guān)的n個文檔了。

        public T insertWithOverflow(T element) {
          if (size < maxSize) {
            add(element);
            return null;
          } else if (size > 0 && ! lessThan(element, heap[1])) {
            //堆中最小的元素用更大的元素替換了
            T ret = heap[1];
            heap[1] = element;
            updateTop();
            return ret;
          } else {
            return element;
          }
        }

要在堆中增加一個元素，必須執(zhí)行一個upHeap。可以用add(element) 方法調(diào)用upHeap。要從最小堆中取得最小的元素就需要從堆中刪除根節(jié)點，這叫作downHeap。可以用pop()方法調(diào)用downHeap。

最后把最小堆中的文檔放入ScoreDoc。

        final ScoreDoc[] scoreDocs = new ScoreDoc[hq.size()];
        for (int i = hq.size() -1; i >= 0; i--) // 把最相關(guān)的文檔放入數(shù)組
          scoreDocs[i] = hq.pop(); //先取出來最不相關(guān)的文檔

官术网_书友最值得收藏!

自己動手寫分布式搜索引擎

2.4 查詢