這篇文章講講如何在知識圖譜數據集上構建索引進行查詢。
倒排索引是一種數據結構，它表示了這樣一種映射，以字或詞或數字為關鍵字進行索引，映射到出現這個字或詞的所有文檔或者資料庫文件。
它大概由三部分組成term index、term dictionary 和posting list（倒排表）。
索引過程，首要需要找到term（關鍵詞）索引的位置。term index就是用於找到關鍵詞term在term dictionary（詞典）中的位置。term index有很多種詞典結構，比如哈希表，B樹、B+、FST。
B樹B-樹（Balance Tree）是一種多路平衡查找樹，他的每一個節點最多包含M個孩子，M就是B樹的階。樹的分叉多使得高度足夠低,於是和磁碟的I0次數就會減少。
B+樹相比B樹，其區別體現在：
父節點的元素都會出現在子節點,因此葉子節點包含所有元素信息。
從左邊開始，每一個葉子節點帶有指向下一個葉子節點的指針,形成一個有序鍊表，便於範圍查詢。而B-樹做範圍查詢，只能依靠繁瑣的中序遍歷。
B+樹非葉節點沒有衛星數據（索引元素所指向的數據記錄），磁碟頁可以容納更多節點元素，其高度會比B樹矮，查詢的IO會更少。
B+樹的查詢必須抵達葉子節點，查找性能更穩定
FSTFST（Finite State Transducer）原理是有限狀態機原理構造的一個有向無環圖。我們今天使用的Lucene就採用了FST的索引結構來構建詞典。FST將關鍵詞拆分為前綴和後綴，並在前綴部分構造了一個有向無環圖進行索引。
FST其特點是非常節省內存，缺點是結構複雜、更新麻煩
Lucene是Apache軟體基金會支持和提供的一套用於全文檢索和搜索的開放源碼程序庫。用Java編寫，為需要全文搜索的應用程式提供了一個簡單卻強大的接口，分布式檢索分析系統Solr和ElasticSearch底層就是基於Lucene實現。
FST索引結構
Elasticsearch檢索比mysql快的原因就是，相比Mysql以B樹方式將term index和term dictionary存儲在磁碟上，lucene的term index以FST的形式緩存在內存中。從term index查到關鍵詞對應的term dictionary的塊位置之後，再去磁碟上找term，大大減少了磁碟的IO次數。
Lucene索引文件結構
DBpedia知識圖譜我們可以使用Lucene基於我們知識圖譜具體的需求來構建倒排索引。這裡使用的數據集是英文百科類知識圖譜數據集DBpedia，其中大部分內容是從維基百科詞條進行結構化得到的。我們對其中每個實體進行節點編號，將每個節點上的非實體屬性文本作為每個節點的文檔，就得到下面形式的文件：節點和文本
構建索引document是Lucene索引和搜索的原子單位。document為包含一個或多個域，每個域都有一個名稱,當你將document加入到索引中時,可以通過一系列選項來控制 Lucene的行為。你需要將需要被索引的數據轉換成 Lucene所能識別的document和域。
這裡我們以知識圖譜上的一個節點上的內容作為一個文檔，包括三個域：
Document doc=new Document();
doc.add(new TextField("keywords", keywords, Field.Store.NO, Field.Index.ANALYZED));
doc.add(new IntPoint("nodeId",nodeId));
doc.add(new StoredField("nodeId", nodeId));
TextField為文本域，包含節點的文本內容，我們需要對其進行分詞然後再建立到排索引，Field.Store.NO指定是否要在正向文檔中保存這個域值，Field.Index.ANALYZED用於指定是否分詞
Analyzer analyzer = new StandardAnalyzer();
directory = FSDirectory.open(Paths.get(indexStorePath));
IndexWriterConfig iwc = new IndexWriterConfig(analyzer);
IndexWriter indexWriter = new IndexWriter(directory, iwc);
// 建立doc這個文檔的索引
indexWriter.addDocument(doc);
在構造索引寫入器的時候，可以指定用於分詞的工具analyzer，
Lucene比較常用的幾種英文分析器，他們之間存在一些區別：
SimpleAnalyzer：空格及各種符號分割
StandardAnalyzer：混合分割,包括了去掉停止詞，並且具備一定中文分詞的功能
WhitespaceAnalyzer ：空格分割
StopAnalyzer：空格及各種符號分割,去掉停止詞，停止詞包括 is,are,in,on,the等無實際意義的詞
Elasticsearch內置的分詞器就包含了上面這些。
另外還有許多用於中文分詞的分詞器如ik-analyzer、結巴中文分詞等，可以根據需要進行配置。
搜索Lucene的查詢調用的是 Indexsearcher類中的search方法,調用時傳人 Query類型作為參數。可以使用 QueryParser類將查詢詞轉換成 Query類型。hitNum可以限制你要拿到的目標文檔數。
IndexReader indexReader = DirectoryReader.open(directory);
IndexSearcher searcher = new IndexSearcher(indexReader);
QueryParser parser = new QueryParser("worsIdStr", new StandardAnalyzer());
Query query = parser.parse("aKeyword");
TopDocs tds = searcher.search(query, hitNum);
ScoreDoc[] sds = tds.scoreDocs;
這樣，就可以找到這個查詢詞所在的文檔id,也即查詢詞所在的知識圖譜的圖節點編號。
☆☆☆為方便大家查閱，小編已將知識圖譜實戰專欄系列文章統一整理到公眾號底部菜單欄，同步更新中，關注公眾號，點擊左下方「系列文章」，如圖：
歡迎大家和我一起沿著知識圖譜實戰專欄這條路線，一起鞏固機器學習算法基礎。（添加微信：mthler，開啟打怪升級的學習之旅。）