如何提供最佳搜尋結果：深入了解全文搜尋引擎

搜尋欄是瀏覽網路不可或缺的一部分。無論我們是購買衣服、享受音樂或計劃假期，總是有一個專用的搜尋引擎在工作，以簡化我們的生活。您是否曾想過這些搜尋引擎實際上是如何運作的？在本文中，我們將深入研究其中一個搜尋引擎的內部運作：Meilisearch。

索引時間：從資料到文件

索引是一個基本過程，包含收集、解析和儲存資料以供後續檢索。它在使搜尋引擎能夠提供快速且相關的結果方面發揮著至關重要的作用。

高效能的儲存引擎

Meilisearch 以稱為「文件」的離散記錄形式儲存資料，這些記錄組合在一起形成稱為「索引」的集合。在底層，Meilisearch 使用 LMDB（Lightning 記憶體映射資料庫）鍵值儲存，該儲存已在資料庫應用程式中證明了穩定性和廣泛的使用。顧名思義，鍵值儲存是以鍵值對集合形式組織資料的儲存系統。

鍵值條目範例

鍵值儲存提供彈性、快速的存取時間和高效能，有助於使用者進行快速且反應靈敏的互動。透過一次僅允許一個寫入處理，LMDB 避免了與同步相關的問題。因此，它使無限的並行讀取器能夠快速存取最新的、一致的資料。

在將資料儲存在其鍵值儲存中之前，Meilisearch 必須徹底預先處理它。這就是分詞化的用武之地。

從詞語到權杖

分詞化涉及兩個主要流程：分段和正規化。

分段包括將句子或詞組分割成稱為權杖的較小單元。

Meilisearch 使用（並維護）名為 Charabia 的開放原始碼分詞器。分詞器負責從文件欄位中檢索所有詞語（或權杖）。

然後是正規化。詞語根據每種語言的特殊性進行正規化。對於法語等羅曼語系語言，此流程包括將詞語設定為小寫字母並移除變音符號，例如重音符號。例如，像「Le café de Nicolas」這樣的句子會轉換為「le cafe de nicolas」。

分詞化流程中分段和正規化階段的範例

在分段和正規化詞語後，引擎需要對它們進行分類。使用適當的資料結構來組織權杖對於效能至關重要。這將在稍後允許快速檢索最相關的搜尋結果。

儲存權杖

像 Meilisearch 這樣的現代全文搜尋引擎具有前綴搜尋、錯字容錯和地理搜尋等功能。每個資料結構都有其自身的優缺點。在設計搜尋引擎時，我們的團隊仔細選擇了最適合啟用這些功能，而不會影響速度的資料結構。

在本節中，我們將探討哪些資料結構為 Meilisearch 提供支援。

倒排索引

首先，我們需要談談倒排索引。毫無疑問，它是以其重要性而著稱的資料結構。Meilisearch 使用它來在搜尋時快速返回文件。

倒排索引將文件中的每個詞語映射到該詞語出現的文件集合，以及文件中的位置等其他資訊。

從給定文件產生的倒排索引的說明，展示了關鍵字到文件 ID 的映射

透過將詞語儲存一次並將它們與它們出現的文件相關聯，倒排索引利用了文件中詞語的冗餘。因此，Meilisearch 不需要瀏覽所有文件即可找到給定的詞語，從而實現更快的搜尋。

Meilisearch 為每個文件索引建立大約 20 個倒排索引，使其成為實例數量最多的資料結構之一。實際上，為了提供隨打即搜尋體驗，引擎需要在索引時預先計算大量內容：詞語前綴、包含可篩選屬性的文件等。為了更好地了解倒排索引的工作原理，請閱讀更多關於[索引最佳實務](/blog/best-practices-for-faster-indexing/）的資訊

Roaring 位元圖

Roaring 位元圖是經過壓縮的資料結構，旨在有效率地表示和操作整數集合。

Meilisearch 在其倒排索引中廣泛使用 Roaring 位元圖來表示文件 ID。Roaring 位元圖提供了一種節省空間的方式來儲存大量的整數集合，並執行集合運算，例如聯集、交集和差集。這些運算在透過允許根據特定文件與其他文件的關係來包含或排除特定文件，從而改進搜尋結果方面發揮著至關重要的作用。

有限狀態轉換器

有限狀態轉換器 (FST) 是一種結構化的資料表示形式，非常適合執行字串比對運算。它表示按從小到大排序的狀態序列，其中詞語按詞彙順序排列。

有限狀態轉換器也稱為詞語字典，因為它包含索引中存在的所有詞語。Meilisearch 依賴於兩個 FST 的使用：一個用於儲存資料集的所有詞語，另一個用於儲存最常見的前綴。

FST 很實用，因為它們支援壓縮和延遲解壓縮技術，從而優化了記憶體使用和儲存。此外，透過使用自動機（例如正規表示式），它們可以檢索符合特定規則或模式的詞語子集。此外，這使得可以檢索以特定前綴開頭的所有詞語，從而實現快速、全面的搜尋功能。

FST 以其緊湊的設計，具有比倒排索引更小的資料結構的額外優勢。正如我們稍後將看到的，這有助於更快、更有效率的讀取運算。您可以在這篇關於有限狀態縮減器的綜合文章中了解更多關於此主題的資訊。

R 樹

R 樹是一種用於索引多維或空間資訊的樹。Meilisearch 利用 R 樹來支援其地理搜尋功能。

R 樹將地理座標與其所屬文件的識別碼相關聯。透過以這種方式組織座標，它使 Meilisearch 能夠以卓越的效率執行空間查詢。這些查詢允許使用者尋找附近的點、特定區域內的點或與其他空間物件相交的點。

搜尋時間：查詢處理

現代搜尋體驗僅需要您開始輸入即可獲得結果。為了實現這種隨打即搜尋體驗，Meilisearch 會預先計算最常用前綴的清單。

為了容許錯字，Meilisearch 結合了有限狀態轉換器 (finite-state transducers) 和 Levenshtein 演算法。此演算法會計算 Levenshtein 距離，可以把它想成是將一個字串轉換成另一個字串的成本。換句話說，它量化了一個詞轉換成另一個詞所需的轉換次數。

在 Levenshtein 演算法的上下文中，可能的轉換為：

• 插入，例如 hat -> chat
• 刪除，例如 tiger -> tier
• 替換，例如 cat -> hat
• 移位或交換，例如 scared -> sacred

FST 會產生指定編輯距離內一個詞的所有可能變體，使引擎能夠計算 Levenshtein 距離，並透過比較使用者輸入與有效詞字典來準確偵測錯字。

顯而易見的是，在處理搜尋請求時，需要考慮許多因素。使用者是否已完成輸入？查詢中是否有錯字？哪些文件應該在搜尋結果中優先顯示？

讓我們討論 Meilisearch 如何處理搜尋查詢，以及它如何精煉和排序搜尋結果。

查詢圖

每次收到搜尋查詢時，Meilisearch 都會建立一個查詢圖，表示該查詢及其可能的變體。

為了計算這些變體，Meilisearch 會對查詢詞彙應用串聯和分割演算法。考量的變體還包括潛在的錯字和同義詞（如果使用者設定它們）。舉例來說，我們來檢視一下查詢：the sun flower。Meilisearch 也會搜尋以下查詢：

• the sunflower：串聯
• the sun flowe**d**：替換
• the sun flower**s**：添加

現在考慮一個更複雜的查詢：the sun flower is facing the su，查詢圖應該看起來像這樣：

使用我們的內部除錯工具產生視覺圖，由 D2 提供技術支援，展示搜尋請求的執行過程

如上圖所示，該圖表示對搜尋查詢的不同解釋。引擎會預先計算每個查詢詞彙的字詞變體（及其成本）。此外，它會偵測最後一個查詢詞彙是否為前綴（後面沒有空格），從而發出需要查閱前綴資料庫的訊號。

那麼引擎如何利用查詢圖呢？

如我們稍早所見，在索引處理期間，Meilisearch 會識別所有具有可篩選屬性的文件，例如 genre。隨後，它會產生與每個屬性值（如 comedy 或 horror）相關聯的文件 ID 清單。首先，當套用篩選器時，Meilisearch 會將潛在的結果縮減為符合篩選條件的文件 ID。

接下來，它會使用查詢字詞和查詢圖中產生的變體，並在有限狀態轉換器（即我們的詞彙字典）中搜尋匹配的字詞。如果該字詞被視為前綴，它也會在前綴 FST 中查詢它。

當在 FST 中遇到字詞時，它會在反向索引中搜尋它們（其中包含字詞到文件 ID 的對應），以擷取相應的文件 ID。

最後，引擎會執行交集，以識別查詢圖中包含字詞且符合篩選條件的文件。

讓我們以一個範例來更好地理解查詢處理：假設您有一個歌曲資料集。搜尋查詢是 John Lennon。使用者希望僅擷取 1957 年至 1975 年之間發行的歌曲。

首先，Meilisearch 會擷取該時間範圍內歌曲的文件 ID。然後，在 FST 中檢查查詢圖中的字詞是否存在後，Meilisearch 會擷取包含 John、Lennon 或兩者的文件 ID。它也會擷取可能的變體，但為了簡潔起見，我們不會在本範例中加入它們。

圖表說明根據使用者查詢擷取文件所涉及的操作。

最後，取兩個文件 ID 集的交集（圖表中的紫色區域）。這表示僅保留兩個集合中都出現的文件 ID。換句話說，Meilisearch 會保留 1957 年至 1975 年之間發行，且包含 John、Lennon 或兩者的歌曲文件 ID。

當多個文件符合搜尋查詢時，會發生什麼？引擎如何決定先傳回哪個文件？哪個文件更相關？讓我們探索讓 Meilisearch 能夠決定如何對結果進行排序的規則。

相關性

如我們稍早所討論的，查詢圖包含字詞的可能變體。因此，Meilisearch 也會傳回藝術家名稱（例如 John Lebon）作為搜尋結果一部分的文件。

幸運的是，查詢圖不僅考慮字詞變體，還會為它們指定 Levenshtein 成本，這在其他因素中，有助於 Meilisearch 判斷搜尋結果的相關性。

Meilisearch 使用桶排序來排序搜尋結果中的文件。此演算法允許根據一組連續規則對文件進行排名。依預設，Meilisearch 會按以下順序優先處理規則：

1. 字詞：根據匹配的查詢詞彙數量來排序文件，包含所有查詢詞彙的文件會優先排名
2. 錯字：根據錯字數量來排序文件，匹配較少錯字查詢詞彙的文件會優先排名
3. 鄰近度：根據匹配的查詢詞彙之間的距離來排序文件。查詢詞彙彼此靠近且與查詢字串順序相同的文件會優先排名
4. 屬性：根據屬性的排名順序來排序文件。在更重要的屬性中包含查詢詞彙的文件會優先排名。在屬性開頭包含查詢字詞的文件會被認為比在屬性結尾包含查詢字詞的文件更相關
5. 排序：根據查詢時設定的使用者定義參數來排序文件（如果已啟動）
6. 精確度：根據匹配字詞與查詢字詞的相似度來排序文件

Meilisearch 會依序套用這些規則，逐步排序結果。如果兩個文件在一個規則之後並列，則它會使用下一個規則來打破僵局。

依預設，Meilisearch 每次搜尋最多傳回 1000 個文件，優先提供最相關的結果，而不是所有匹配的結果。換句話說，Meilisearch 會優先考慮效率和相關性，而不是詳盡的結果，以確保最佳化的搜尋體驗。

結論

搜尋引擎是複雜的系統，包含多個相互連接的元件，所有元件協同工作，以提供無縫的搜尋體驗。雖然搜尋引擎之間的內部運作方式可能有所不同，但我們已探索現代搜尋引擎的底層機制。

Meilisearch 目前正在探索廣泛的語義搜尋領域。AI 驅動的搜尋正在重塑我們理解查詢和文件的方式，開闢新的可能性和使用案例。如果您渴望親身體驗它，我們邀請您試用我們的向量搜尋原型 — 您的意見回饋將非常寶貴！

Meilisearch 是一個開放原始碼搜尋引擎，不僅為終端使用者提供最先進的體驗，還提供簡單直觀的開發人員體驗。您想看看 Meilisearch 的實際運作嗎？請試用我們的示範。您也可以在本機執行它或在Meilisearch Cloud 上建立帳戶。

如需更多關於 Meilisearch 的資訊，您可以加入Discord 上的社群或訂閱電子報。您可以查看路線圖並參與產品討論，以了解更多關於產品的資訊。