pg寻龙探宝电子游戏

書名：自己動手寫分布式搜索引擎
作者名：羅剛
本章字數： 1724字
更新時間： 2020-11-28 15:52:52

3.5.2 索引原理

為了方便索引大量的文檔，可以將Lucene中的一個索引分成若干個子索引，稱為段(segment)。段中包含一些可搜索的文檔。在給定的段中可以快速遍歷任何給定索引詞在所有文檔中出現的頻率和位置。IndexWriter收集在內存中的多個文檔，然后在某個時間點把這些文檔寫入一個新的段，寫入點可以通過Lucene內部的配置類或者外部程序控制。這些文檔組成的段將保持不動，直到Lucene把它合并進大的段。MergePolicy控制Lucene如何合并段。

索引文檔時，首先對文檔分詞后建立正排索引，然后建立倒排索引。在索引優化階段，會把小的段合并成大的段。其中可能用到的算法有：合并兩個排好序的數組成為一個大的排好序的數組。

為了提高性能，索引首先緩存在內存中，如果緩存達到預定的內存數量，就會寫入硬盤。然而，即使IndexWriter從緩存中把這些文檔的索引寫入硬盤，在沒有提交之前IndexReader也不能看到這些新加入的文檔。如果頻繁地調用IndexWriter.commit就會降低索引的通量。所以不要過于頻繁地提交索引。可以通過測試來決定具體加入多少篇文檔后再提交索引。索引文件的邏輯視圖如圖3-15所示。

圖3-15 索引文件的邏輯視圖

Lucene把一個文檔寫入索引時，首先生成這個文檔的倒排索引，然后再把文檔的倒排索引合并到段的倒排索引中。先看一下最簡單的統計一個文檔中所有單詞出現頻次的例子：

        //單詞和對應的次數
        HashMap<String, Integer> postingTable = new HashMap<String, Integer>();


        StringTokenizer st = new StringTokenizer(inputStr);
        while(st.hasMoreTokens()){ //按空格切分輸入串
          String word = st.nextToken();
        //檢查單詞是否在HashMap中
        if (postingTable.containsKey(word)) {
            //取得單詞出現次數，加1后放回去
            postingTable.put(word, postingTable.get(word) + 1);
        } else {
            //第一次看到這個單詞，設置次數為1次
            postingTable.put(word, 1);
        }
      }

描述單個文檔的Posting表由Posting類組成的數組構成：

        final class Posting {    // 一個文檔中的一個詞相關的信息
          Term term;              // 詞
          int freq;           // 這個詞在文檔中的頻率
          int[] positions;        // 詞出現的位置
        }

生成文檔的倒排索引的簡略代碼如下：

        final void addDocument(Document doc)
                throws IOException {
            //使用散列表緩存詞和位置對應關系
            Hashtable<Term, Posting> postingTable = new Hashtable<Term, Posting>();


          //invertDocument對文檔倒排，具體執行的工作有：
          //對文檔內容分詞，然后把每個詞放入postingTable
          //postingTable.put(term, new Posting(term, position, offset));
          invertDocument(doc);


          //對postingTable排序后放入數組
          Posting[] postings = sortPostingTable();
        }

首先按列讀入每個文檔，然后處理同名的列。之后，把每個新列中的數據寫到緩存。

textStart也是用來區分詞的唯一值，但是這個值太大了，不方便存儲，所以要重新生成一個連續編號的termID。

postingsArray用來記錄一個詞之前有沒有看到過。如果以前沒看到過，就調用newTerm(termID)方法，否則就調用addTerm(termID)方法。

        if(! postingsArray.textStarts.contains(textStart)){
          int termID = numPostings++;
          postingsArray.textStarts[termID] = textStart;
          consumer.newTerm(termID);
        }else{
          consumer.addTerm(termID);
        }

postingsHash數組用來加快這個判斷過程。可以把它看成散列表中的數組表。并行數組postingsArray中的textStarts則用來判斷是否包含當前詞。

在reset()方法中，把postingsHash中的初始值設置成-1。

        Arrays.fill(postingsHash, 0, numPostings, -1);

初始化的原理代碼如下：

        int postingsHashSize = 4;
        int[] postingsHash = new int[postingsHashSize];
        int postingsHashMask = postingsHashSize-1;

根據詞所在的位置來找槽的位置。值是詞編號。使用二次探測再散列法解決沖突。

        int code = textStart;


        int hashPos = code & postingsHashMask;


        // 定位散列表中的RawPostingList
        int termID = postingsHash[hashPos];


        if (termID ! = -1 && postingsArray.textStarts[termID] ! = textStart) {
          // Conflict: keep searching different locations in
          // the hash table.
          final int inc = ((code>>8)+code)|1;
          do {
            code += inc;
            hashPos = code & postingsHashMask;
            termID = postingsHash[hashPos];
          } while (termID ! = -1 && postingsArray.textStarts[termID] ! = textStart);
        }

如果發現一個詞沒有在postingsHash存過，就在postingsHash中記錄這個詞的編號。

        int numPostings = 0;
        int termID = numPostings++;


        int code = 100; //詞所在的位置
        int hashPos = code & postingsHashMask;
        postingsHash[hashPos] = termID;

然后壓縮掉沒有用到的位置。

        private void compactPostings() {
          int upto = 0; //記錄已經填實的位置
          for(int i=0; i<postingsHashSize; i++) { //從前往后遍歷postingsHash中的每一個值
            if (postingsHash[i] ! = -1) { //如果不是初始值
              if (upto < i) { //而且中間有空位
              postingsHash[upto] = postingsHash[i]; //壓縮
              postingsHash[i] = -1; //標志這個位置已經空了
              }
              upto++; //已經填實的位置標志加1
          }
        }
      }

得到的是一個詞編號序列。

倒排索引在FreqProxTermsWriter類的appendPostings()方法中創建，基于從文檔中統計出的信息，例如詞頻、文檔頻率、詞位置等。

DocumentsWriter中包含一個索引鏈。

Consumer是一個定義接口的抽象類。索引時，在不同的層次，有不同的Consumer類。例如DocConsumer處理整個文檔。DocFieldConsumer處理不同的列，每次處理一個。

InvertedDocConsumer消耗產生的詞序列。

TermsHashConsumer寫和它自己相關的字節到內存中的posting lists(投遞列表)。posting lists以字節切片存儲，按詞索引。

DocumentsWriter*.java更簡單了，它只和DocConsumer打交道，并不知道Consumer在做什么。

DocConsumer下面是做實際工作的索引鏈。

● NormsWriter在內存中記錄歸一化信息，然后把這些信息寫入_X.nrm。

● FreqProxTermsWriter在內存中記錄postings數據，然后寫入_X.frq/prx。

● StoredFieldsWriter負責寫入列存儲的值信息，把內存中的值信息寫入_X.fdx/fdt。

● TermVectorsTermsWriter把內存中的詞向量信息寫入_X.tvx/tvf/tvd。

DocumentsWriter雖然沒有做具體的事情，但是仍然管理一些事情，例如清空一個段，關閉文檔儲存，緩存和使刪除生效，釋放內存，當需要的時候中止整個過程，等等。

DocInverterPerField得到位置信息。

FieldInvertState記錄要加入索引的詞數量。通過FieldInvertState的attributeSource屬性取得最后坐標，也就是字段長度。

為了讓posting list中的文檔序列壓縮后更小，可以把相似的文檔聚類，讓前后兩個文檔的編號值盡可能小。

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

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

3.5.2 索引原理