天天看點
傳回

關于Lucene的詞典FST深入剖析

作者：閃念基因

搜尋引擎為什麼能查詢速度那麼快？

核心是在于如何快速的依據查詢詞快速的查找到所有的相關文檔，這也是反向索引（Inverted Index）的核心思想。那麼如何設計一個快速的(常量，或者1)定位詞典的資料結構就顯得尤其重要。簡單來說，我們可以采用HashMap， TRIE， Binary Search Tree， Tenary Search Tree等各種資料結構來實作。

那麼開源的搜尋引擎包Lucene是怎麼來設計的呢？Lucene采用了一種稱為FST（Finite State Transducer）的結構來建構詞典，這個結構保證了時間和空間複雜度的均衡，是Lucene的核心功能之一。

關于FST（Finite State Transducer）

FST類似一種TRIE樹。

使用FSM(Finite State Machines)作為資料結構

FSM(Finite State Machines)有限狀态機: 表示有限個狀态（State）集合以及這些狀态之間轉移和動作的數學模型。其中一個狀态被标記為開始狀态，0個或更多的狀态被标記為final狀态。

一個FSM同一時間隻處于1個狀态。FSM很通用，可以用來表示多種處理過程，下面的FSM描述了《小貓咪的一天》。

關于Lucene的詞典FST深入剖析

其中“睡覺”或者“吃飯”代表的是狀态,而“提供食物”或者“東西移動”則代表了轉移。圖中這個FSM是對小貓活動的一個抽象（這裡并沒有刻意寫開始狀态或者final狀态），小貓咪不能同時的即處于“玩耍”又處于“睡覺”狀态，并且從一個狀态到下一個狀态的轉換隻有一個輸入。“睡覺”狀态并不知道是從什麼狀态轉換過來的，可能是“玩耍”，也可能是”貓砂窩”。

如果《小貓咪的一天》這個FSM接收以下的輸入:

  • 提供食物
  • 有大聲音
  • 安靜
  • 消化食物

那麼我們會明确的知道，小貓咪會這樣依次變化狀态： 睡覺->吃飯->躲藏->吃飯->貓砂窩.

以上隻是一個現實中的例子，下面我們來看如何實作一個Ordered Sets,和Map結構。

Ordered Sets

Ordered Sets是一個有序集合。通常一個有序集合可以用二叉樹、B樹實作。無序的集合使用hash table來實作. 這裡，我們用一個确定無環有限狀态接收機（Deterministric acyclic finite state acceptor, FSA）來實作。

FSA是一個FSM(有限狀态機)的一種，特性如下:

  • 确定：意味着指定任何一個狀态，隻可能最多有一個轉移可以通路到。
  • 無環： 不可能重複周遊同一個狀态
  • 接收機：有限狀态機隻“接受”特定的輸入序列，并終止于final狀态。

下面來看，我們如何來表示隻有一個key：”jul“ 的集合。FSA是這樣的：

關于Lucene的詞典FST深入剖析

當查詢這個FSA是否包含“jul”的時候，按字元依序輸入。

  • 輸入j，FSA從0->1
  • 輸入u, FSA從1->2
  • 輸入l，FSA從2->3

這個時候，FSA處于final狀态3，是以“jul”是在這個集合的。

設想一下如果輸入“jun”，在狀态2的時候無法移動了，就知道不在這個集合裡了。

設想如何輸入“ju”, 在狀态2的時候，已經沒有輸入了。而狀态2并不是final狀态，是以也不在這個集合裡。

值得指出的是，查找這個key是否在集合内的時間複雜度，取決于key的長度，而不是集合的大小。

現在往FSA裡再加一個key. FSA此時包含keys:”jul”和“mar”。

關于Lucene的詞典FST深入剖析

start狀态0此時有了2個轉移：j和m。是以，輸入key:”mar”,首先會跟随m來轉移。 final狀态是“jul”和“mar”共享的。這使得我們能用更少的空間來表示更多的資訊。

當我們在這個FSA裡加入“jun”，那麼它和“jul”有共同的字首“ju”:

關于Lucene的詞典FST深入剖析

這裡變化很小，沒有增加新的狀态，隻是多了一個轉移而已。

下面來看一下由“october”，“november”,”december”構成的FSA.

關于Lucene的詞典FST深入剖析

它們有共同的字尾“ber”，是以在FSA隻出現了1次。 其中2個有共同的字尾”ember”，也隻出現了1次。

那麼我們如何來周遊一個FSA表示的所有key呢，我們以前面的”jul”，“jun”,”mar”為例：

關于Lucene的詞典FST深入剖析

周遊算法是這樣的：

  • 初始狀态0， key=””
  • ->1, key=”j”
  • ->2, key=”ju”
  • ->3, key=”jul”, 找到jul
  • 2<-, key=”ju”
  • ->3, key=”jun”, 找到jun
  • 2<-, key=”ju”
  • 1<-, key=”j”
  • 0<-, key=””
  • ->4, key=”m”
  • ->5, key=”ma”,
  • ->3, key=”mar”,找到mar

這個算法時間複雜度O(n),n是集合裡所有的key的大小, 空間複雜度O(k),k是結合内最長的key字段length。

Ordered maps

Ordered maps就像一個普通的map，隻不過它的key是有序的。我們來看一下如何使用确定無環狀态轉換器（Deterministic acyclic finite state transducer， FST）來實作它。

FST是也一個有限狀态機（FSM）,具有這樣的特性：

  • 确定：意味着指定任何一個狀态，隻可能最多有一個轉移可以周遊到。
  • 無環： 不可能重複周遊同一個狀态
  • transducer：接收特定的序列，終止于final狀态，同時會輸出一個值。

FST和FSA很像，給定一個key除了能回答是否存在，還能輸出一個關聯的值。

下面來看這樣的一個輸入：“jul:7”, 7是jul關聯的值，就像是一個map的entry.

關于Lucene的詞典FST深入剖析

這和對應的有序集合基本一樣，除了第一個0->1的轉換j關聯了一個值7. 其他的轉換u和l,預設關聯的值是0,這裡不予展現。

那麼當我們查找key:”jul”的時候，大概流程如下：

  • 初始狀态0
  • 輸入j, FST從0->1， value=7
  • 輸入u, FST從1->2， value=7+0
  • 輸入l，FST從2->3, value=7+0+0

此時，FST處于final狀态3，是以存在jul，并且給出output是7.

我們再看一下，加入mar:3之後，FST變成什麼樣：

關于Lucene的詞典FST深入剖析

同樣的很簡單，需要注意的是mar自帶的值3放在了第1個轉移上。這隻是為了算法更簡單而已，事實上，可以放在其他轉移上。

如果共享字首，FST會發生什麼呢？這裡我們繼續加入jun:6。

關于Lucene的詞典FST深入剖析

和sets一樣，jun和jul共享狀态3， 但是有一些變化。

  • 0->1轉移，輸出從7變成了6
  • 2->3轉移，輸入l，輸出值變成了1。

這個輸出變化是很重要的，因為他改變了查找jul輸出值的過程。

  • 初始狀态0
  • 輸入j, FST從0->1， value=6
  • 輸入u， FST從1->2， value=6+0
  • 輸入l，FST從2->3, value=6+0+1

最終的值仍舊是7，但是走的路徑卻是不一樣的。

那查找jun是不是也是正确的呢？

  • 初始狀态0
  • 輸入j, FST從0 -> 1， value=6
  • 輸入u，FST從1 -> 2， value=6+0
  • 輸入n，FST從2 -> 3, value=6+0+0

從上可知，jun的查詢也是正确的。FST保證了不同的轉移有唯一的值，但同時也複用了大部分的資料結構。

實作共享狀态的關鍵點是：每一個key,都在FST中對應一個唯一的路徑。是以，對于任何一個特定的key，總會有一些value的轉移組合使得路徑是唯一的。我們需要做的就是如何來在轉移中配置設定這些組合。

key輸出的共享機制同樣适用于共同字首和共同字尾。比如我們有tuesday:3和thursday:5這樣的FST:

關于Lucene的詞典FST深入剖析

2個key有共同的字首t，共同字尾sday。關聯的2個value同樣有共同的字首。3可以寫做3+0，而5可以寫作：3+2。 這樣很好的讓實作了關聯value的共享。

上面的這個例子，其實有點簡單化，并且局限。假如這些關聯的value并不是int呢？ 實際上，FST對于關聯value(outputs)的類型是要求必須有以下操作（method）的。

  • 加（Addition）
  • 減 (Subtraction)
  • 取字首 (對于整數來說，就是min)

FST的建構

前面，一直沒有提到如何建構FST。建構相對于周遊來說，還是有些複雜的。

為了簡單化，我們假設set或者map裡的資料是按字典序加入的。這個假設是很沉重的限制，不過我們會講如何來緩解它。

為了建構FSM，我們先來看看TRIE樹是如何建構的。

TRIE樹的建構

TRIE可以看做是一個FSA,唯一的一個不同是TRIE隻共享字首，而FSA不僅共享字首還共享字尾。

假設我們有一個這樣的Set: mon,tues,thurs。FSA是這樣的：

關于Lucene的詞典FST深入剖析

相應的TRIE則是這樣的，隻共享了字首。

關于Lucene的詞典FST深入剖析

TRIE有重複的3個final狀态3，8，11. 而8，11都是s轉移，是可以合并的。

建構一個TRIE樹是相當簡單的。插入1個key，隻需要做簡單的查找就可以了。如果輸入先結束，那麼目前狀态設定為final；如果無法轉移了，那麼就直接建立新的轉移和狀态。不要忘了最後一個建立的狀态設定為final就可以了。

FST的建構

建構FST在很大程度上和建構FSA是一樣的，主要的不同點是，怎麼樣在轉移上放置和共享outputs。

仍舊使用前面提到的例子，mon,tues和thurs，并給他們關聯相應的星期數值2，3和5.

從第1個key, mon:2開始：

關于Lucene的詞典FST深入剖析

這裡虛線代表，在後續的insert過程中，FST可能有變化。

需要關注的是，這裡隻是把2放在了第1個轉移上。技術上說，下面這樣配置設定也是正确的。

關于Lucene的詞典FST深入剖析

隻不過，把output放在靠近start狀态的算法更容易寫而已。

下面繼續把thurs:5插入：

關于Lucene的詞典FST深入剖析

就像FSA的insert一樣，插入thurs之後，我們可以知道FST的mon部分（藍色）就不會再變了。

由于mon和thurs沒有共同的字首，隻是簡單的2個map中的key. 是以他們的output value可以直接放置在start狀态的第1個轉移上。

下面，繼續插入tues:3，

關于Lucene的詞典FST深入剖析

這引起了新的變化。有一部分被凍住了，并且知道以後不會再修改了。output value也出現了重新的配置設定。因為tues的output是3，并且tues和thurs有共同的字首t, 是以5和3的prefix操作得出的結果就是3. 狀态0->狀态4的value被配置設定為3，狀态4->狀态5設定為2。

我們再插入更多的key, 這次插入tye:99看發生什麼情況：

關于Lucene的詞典FST深入剖析

插入tye，導緻”es”部分被凍住，同時由于共享字首t, 狀态4->狀态9的輸出是99-3=96。

最後一步，結束了，再執行一次凍住操作。

最終的FST長這樣：

關于Lucene的詞典FST深入剖析

Lucene FST

上一部分，對于FST的概念以及建構進行了詳細的介紹。本部分将對Lucene FST的實作以及具體進行詳細的分析。

Lucene關于FST相關的代碼在package:org.apache.lucene.util.fst。

從org.apache.lucene.util.fst.Builder看起，這個是建構FST的Builder：

關于Lucene的詞典FST深入剖析

Builder通過泛型T，進而可以建構包含不同類型的FST。我們重點關注屬性。

從其中插入資料add()方法看起：

/** Add the next input/output pair.  The provided input
   *  must be sorted after the previous one according to
   *  {@link IntsRef#compareTo}.  It's also OK to add the same
   *  input twice in a row with different outputs, as long
   *  as {@link Outputs} implements the {@link Outputs#merge}
   *  method. Note that input is fully consumed after this
   *  method is returned (so caller is free to reuse), but
   *  output is not.  So if your outputs are changeable (eg
   *  {@link ByteSequenceOutputs} or {@link
   *  IntSequenceOutputs}) then you cannot reuse across
   *  calls. */
  public void add(IntsRef input, T output) throws IOException {

    ...
    // prefixLenPlus1是計算出input和lastInput具有公共字首的位置
    final int prefixLenPlus1 = pos1+1;

     // 1.新插入的節點放到frontier數組，UnCompileNode表明是新插入的，以後還可能會變化，還未放入FST内。
    if (frontier.length < input.length+1) {
      final UnCompiledNode<T>[] next = ArrayUtil.grow(frontier, input.length+1);
      for(int idx=frontier.length;idx<next.length;idx++) {
        next[idx] = new UnCompiledNode<>(this, idx);
      }
      frontier = next;
    }

    // minimize/compile states from previous input's
    // orphan'd suffix

    // 2.從prefixLenPlus1, 進行freeze冰凍操作, 添加并建構最小FST
    freezeTail(prefixLenPlus1);

    // init tail states for current input
    // 3.将目前input剩下的部分插入，建構arc轉移（字首是共用的，不用添加新的狀态）。
    for(int idx=prefixLenPlus1;idx<=input.length;idx++) {
      frontier[idx-1].addArc(input.ints[input.offset + idx - 1],
                             frontier[idx]);
      frontier[idx].inputCount++;
    }

    final UnCompiledNode<T> lastNode = frontier[input.length];
    if (lastInput.length() != input.length || prefixLenPlus1 != input.length + 1) {
      lastNode.isFinal = true;
      lastNode.output = NO_OUTPUT;
    }

    // push conflicting outputs forward, only as far as
    // needed
    // 4.如果有沖突的話，重新配置設定output值
    for(int idx=1;idx<prefixLenPlus1;idx++) {
      final UnCompiledNode<T> node = frontier[idx];
      final UnCompiledNode<T> parentNode = frontier[idx-1];

      final T lastOutput = parentNode.getLastOutput(input.ints[input.offset + idx - 1]);
      assert validOutput(lastOutput);

      final T commonOutputPrefix;
      final T wordSuffix;

      if (lastOutput != NO_OUTPUT) {
        // 使用common方法，計算output的共同字首
        commonOutputPrefix = fst.outputs.common(output, lastOutput);
        assert validOutput(commonOutputPrefix);
        // 使用subtract方法，計算重新配置設定的output
        wordSuffix = fst.outputs.subtract(lastOutput, commonOutputPrefix);
        assert validOutput(wordSuffix);
        parentNode.setLastOutput(input.ints[input.offset + idx - 1], commonOutputPrefix);
        node.prependOutput(wordSuffix);
      } else {
        commonOutputPrefix = wordSuffix = NO_OUTPUT;
      }
      output = fst.outputs.subtract(output, commonOutputPrefix);
      assert validOutput(output);
    }

    ...
  }

通過注釋，我們看到input是經過排序的，也就是ordered。否則生成的就不是最小的FST。另外如果NO_OUTPUT就退化為FSA了，不用執行第4步重新配置設定output了。

其中freezeTail 方法就是将不再變化的部分進行冰凍，又叫compile，把UnCompileNode，給建構進FST裡。進入到FST是先進行compileNode, 然後addNode進去的。

總結以下，加入節點過程：

  • 1)新插入input放入frontier，這裡還沒有加入FST
  • 2)依據目前input, 對上次插入資料進行freezeTail操作, 放入FST内
  • 3)建構input的轉移（Arc）關系
  • 4)解決Output沖突，重新配置設定output，保證路徑統一(NO_OUTPUT,不執行)

最後在finish方法裡，執行freezeTail(0), 把所有的input建構進FST内。

另外，值得注意的是Lucene裡定義的Outputs類型：

關于Lucene的詞典FST深入剖析

其中3個method是Outputs接口定義的，有11個不同類型的實作:

  • T add(T prefix, T output); 加
  • T subtract(T output, T inc); 減
  • T common(T output1, T output2) 字首

完全滿足我們上個部分的限制，可見就是基于之前算法的一個完整的實作。

除了在Term詞典這塊有應用，FST在整個lucene内部使用的也是很廣泛的，基本把hashmap進行了替換。

場景大概有以下：

  • 自動聯想：suggester
  • charFilter: mappingcharFilter
  • 同義詞過濾器
  • hunspell拼寫檢查詞典

總結

FST，不但能共享字首還能共享字尾。不但能判斷查找的key是否存在，還能給出響應的輸入output。 它在時間複雜度和空間複雜度上都做了最大程度的優化，使得Lucene能夠将Term Dictionary完全加載到記憶體，快速的定位Term找到響應的output（posting倒排清單）。

參考文檔：

Burst Tries

Direct Construction of Minimal Acyclic Subsequential Transducers

Index 1,600,000,000 Keys with Automata and Rust

DFA minimization WikiPedia

Smaller Representation of Finite State Automata

Using Finite State Transducers in Lucene

您的支援是我原創的動力！

Donate

  • Post author: 申豔超
  • Post link: https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/
上一篇: 【硬核科普】如何開發一款字型
下一篇: HBase Meta 元資訊表修複實踐