探討Android全文檢索技術

寫在前面

客戶端本地儲存資料一般使用的儲存方式是：檔案、SharedPreference、資料庫（SQLite）

如果我們要做一些查詢的操作，對於檔案的方式，通過序列化和反序列化來進行資料的增刪改查操作，表示效率低且繁瑣到力不從心。

要實現高效的全文檢索，必然需要使用到資料庫，而對於手機客戶端而言，SQLite支援FTS當然身先士卒

全文檢索主要工作原理是：先建立索引，然後再對索引進行搜尋

建立索引和搜尋索引一般都是根據實際的業務進行相關設計的，沒有全能的，只有相對和針對；至於優化，更是根據相關場景和資料量進行查詢測試和分析的。

所以下面主要還是以介紹檢索功能為出發點，來看看在實現全文檢索的過程中，我們會遇到哪些知識分子，以及我們該如何吸收他們產出的能量。

通過這個篇文章你可以瞭解到：1. 全文檢索是如何實現的

2. 全文檢索涉及到的索引、倒排索引、B-樹等等相關知識概念

3. 在Android端如何去使用全文檢索功能

Sqlite FTS Extension

SQLite FTS Extension 是SQLite實現全文檢索功能的外掛。

目前一共有5個版本，其中FTS1、FTS2已經被廢棄了，可用的版本為FTS3、FTS4、FTS5。

FTS3從SQLite 3.5.0版本開始支援

FTS4從SQLite 3.7.4版本開始支援

FTS5從SQLite 3.9.0版本開始支援

Sqlite在Android平臺上對應的版本關係如下：

鑑於版本相容，FTS5在Android 7.0及之後纔開始支援，而目前市場上還有很大一部分機器是在7.0以下的，所以對於APP我們應該考慮使用FTS4。

那麼下面我們主要以FTS4的身份，去分析和實現全文檢索的功能

FTS 概要

FTS是SQLite資料庫的虛擬表模組，提供全文檢索的功能。

其基本增刪改查操作方式如下：

//建立虛擬表fts_test

CREATEVIRTUALTABLEfts_test USING fts4(title, body, tokenize=unicode61);

//插入資料

INSERTINTOfts_test(title, body)VALUES(‘標題1′,’Java是全世界最好的程式語言’);

//更新資料

UPDATEfts_testSETtitle =’標題1修正’WHERErowid = 1;

//根據rowid查詢資料

SELECT*FROMfts_testWHERErowid = 1;

//全文檢索資料

SELECT*FROMfts_testWHEREfts_test MATCH’java*’;

//刪除表資料

DELETEFROMfts_test;

//刪除表結構

DROPTABLEfts_test;

FTS工作原理

其基本的工作原理如下：

其中分詞器和倒排索引是關鍵

分詞器

FTS4提供了四種系統分詞器：simple、porter、icu、unicode61

型別

描述

simple根據單詞進行分詞，不區分大小寫且不支援中文porter與simple一樣，但是不區分單詞語義（搜尋do時，能搜索到do、did、does）icu將輸入文字根據ICU規則尋找單詞邊界和丟棄任何標記，支援中文，可拓展unicode61根據空格和標點符號進行分詞，依賴於Unicode Version 6.1標準，支援中文

使用方式：

CREATE VIRTUAL TABLE fts_test USING fts4(title, body, tokenize=unicode61);

當然也可以自定義分詞器，這個需要在C層實現。

索引

是幫助MySQL高效獲取資料的數據結構。提取句子主幹，就可以得到索引的本質：索引是一種數據結構。

索引會增加表的體積，其實是在改變表的儲存結構

主鍵是聚集索引，將表的儲存結構變成了平衡樹

建立其他索引會新增其他獨立的索引結構，每次通過索引查詢時，都會先去索引結構中查詢到對應的主鍵，然後在通過主鍵去查詢對應的內容

覆蓋索引，即在多個欄位上建立索引，這樣可以通過索引直接查詢到欄位內容，加快了速度

索引雖然有效的提高的查詢速度，但是也會影響資料的增刪操作，所以需要根據具體情況做相關的決斷

倒排索引

倒排索引源於實際應用中需要根據屬性的值來查詢記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由於不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。

它是一種索引方法，被用來儲存在全文搜尋下某個單詞在一個文件或者一組文件中的儲存位置的對映。它是文件檢索系統中最常用的數據結構。通過倒排索引，可以根據單詞快速獲取包含這個單詞的文件列表。倒排索引主要由兩個部分組成：「單詞詞典」和「倒排檔案」。

倒排檔案

用記錄的非主屬性值（也叫副鍵）來查詢記錄而組織的檔案叫倒排檔案，即次索引。倒排檔案中包括了所有副鍵值，並列出了與之有關的所有記錄主鍵值，主要用於複雜查詢。

單詞詞典（難點）

是由文件集合中出現過的所有單詞構成的字串集合，單詞詞典內每條索引項記載單詞本身的一些資訊以及指向「倒排列表」的指標。（常用的數據結構包含雜湊加連結串列和樹形詞典結構）

倒排列表

記載了出現過某個單詞的所有文件的文件列表及單詞在該文件中出現的位置資訊，通過它可獲知哪些文件包含某個單詞

工作原理分析：

建立表的程式碼：

** Create the backing store tables (%_content, %_segments and %_segdir)

** required by the FTS3 table passed as the only argument. This is done

** as part of the vtab xCreate method.

** If the p->bHasDocsize boolean is true (indicating that this is an

** FTS4 table, not an FTS3 table) then also create the %_docsize and

** %_stat tables required by FTS4.

staticintfts3CreateTables(Fts3Table *p){

intrc = SQLITE_OK; /* Return code */

inti; /* Iterator variable */

sqlite3 *db = p->db; /* The database connection */

if( p->zContentTbl==0 ){

constchar*zLanguageid = p->zLanguageid;

char*zContentCols; /* Columns of %_content table */

/* Create a list of user columns for the content table */

zContentCols = sqlite3_mprintf(“docid INTEGER PRIMARY KEY”);

for(i=0; zContentCols && inColumn; i++){

char*z = p->azColumn[i];

zContentCols = sqlite3_mprintf(“%z, ‘c%d%q'”, zContentCols, i, z);

}

if( zLanguageid && zContentCols ){

zContentCols = sqlite3_mprintf(“%z, langid”, zContentCols, zLanguageid);

}

if( zContentCols==0 ) rc = SQLITE_NOMEM;

/* Create the content table */

fts3DbExec(&rc, db,

“CREATE TABLE %Q.’%q_content'(%s)”,

p->zDb, p->zName, zContentCols

);

sqlite3_free(zContentCols);

}

/* Create other tables */

fts3DbExec(&rc, db,

“CREATE TABLE %Q.’%q_segments'(blockid INTEGER PRIMARY KEY, block BLOB);”,

p->zDb, p->zName

);

fts3DbExec(&rc, db,

“CREATE TABLE %Q.’%q_segdir'(“

“level INTEGER,”

“idx INTEGER,”

“start_block INTEGER,”

“leaves_end_block INTEGER,”

“end_block INTEGER,”

“root BLOB,”

“PRIMARY KEY(level, idx)”

“);”,

p->zDb, p->zName

);

if( p->bHasDocsize ){

fts3DbExec(&rc, db,

“CREATE TABLE %Q.’%q_docsize'(docid INTEGER PRIMARY KEY, size BLOB);”,

p->zDb, p->zName

);

}

assert( p->bHasStat==p->bFts4 );

if( p->bHasStat ){

sqlite3Fts3CreateStatTable(&rc, p);

}

returnrc;

}

1. 建立虛擬表並插入資料

sqlite> CREATE VIRTUAL TABLE fts_test USING fts4(title, body, tokenize=’unicode61′);

sqlite> INSERT INTO fts_test(title, body) VALUES(‘標題1′,’Java是全世界最好的變成語言’);

sqlite> INSERT INTO fts_test(title, body) VALUES(‘標題2′,’Android是最牛逼的手機系統’);

sqlite> INSERT INTO fts_test(title, body) VALUES(‘標題3′,’Java是Android應用層的主要程式語言’);

2. 通過sqlite3檢視表結構和表資料插入過程

sqlite> .table

看到共建立瞭如下6個表：

fts_test、fts_test_content、fts_test_segments、fts_test_segdir、fts_test_stat、fts_test_docsize

sqlite> SELECT * FROM sqlite_master WHERE type = “table”;

可以看到表結構如下：

table|fts_test|fts_test|0|CREATE VIRTUAL TABLE fts_test using fts4(title, body)

table|fts_test_content|fts_test_content|5|CREATE TABLE ‘fts_test_content'(docid INTEGER PRIMARY KEY, ‘c0title’, ‘c1body’)

table|fts_test_segments|fts_test_segments|6|CREATE TABLE ‘fts_test_segments'(blockid INTEGER PRIMARY KEY, block BLOB)

table|fts_test_segdir|fts_test_segdir|7|CREATE TABLE ‘fts_test_segdir'(level INTEGER,idx INTEGER,start_block INTEGER,leaves_end_block INTEGER,end_block INTEGER,root BLOB,PRIMARY KEY(level, idx))

table|fts_test_docsize|fts_test_docsize|9|CREATE TABLE ‘fts_test_docsize'(docid INTEGER PRIMARY KEY, size BLOB)

table|fts_test_stat|fts_test_stat|10|CREATE TABLE ‘fts_test_stat'(id INTEGER PRIMARY KEY, value BLOB)

sqlite> .dump

看到其插入資料的過程：

PRAGMA foreign_keys=OFF;

BEGIN TRANSACTION;

CREATE TABLE android_metadata (locale TEXT);

INSERT INTO android_metadata VALUES(‘zh_CN’);

PRAGMA writable_schema=ON;

INSERT INTO sqlite_master(type,name,tbl_name,rootpage,sql)VALUES(‘table’,’fts_test’,’fts_test’,0,’CREATE VIRTUAL TABLE fts_test using fts4(title, body)’);

CREATE TABLE IF NOT EXISTS ‘fts_test_content'(docid INTEGER PRIMARY KEY, ‘c0title’, ‘c1body’);

INSERT INTO fts_test_content VALUES(1,’標題1′,’Java是全世界最好的程式語言’);

INSERT INTO fts_test_content VALUES(2,’標題2′,’Android是最牛逼的手機系統’);

INSERT INTO fts_test_content VALUES(3,’標題3′,’Java是Android應用層的主要程式語言’);

CREATE TABLE IF NOT EXISTS ‘fts_test_segments'(blockid INTEGER PRIMARY KEY, block BLOB);

CREATE TABLE IF NOT EXISTS ‘fts_test_segdir'(level INTEGER,idx INTEGER,start_block INTEGER,leaves_end_block INTEGER,end_block INTEGER,root BLOB,PRIMARY KEY(level, idx));

INSERT INTO fts_test_segdir VALUES(0,0,0,0,’0 58′,X’00256a617661e698afe585a8e4b896e7958ce69c80e5a5bde79a84e58f98e68890e8afade8a8800501010102000007e6a087e9a2983103010200′);

INSERT INTO fts_test_segdir VALUES(0,1,0,0,’0 55′,X’0022616e64726f6964e698afe69c80e7899be980bce79a84e6898be69cbae7b3bbe7bb9f0502010102000007e6a087e9a2983203020200′);

INSERT INTO fts_test_segdir VALUES(0,2,0,0,’0 65′,X’002c6a617661e698af616e64726f6964e5ba94e794a8e5b182e79a84e4b8bbe8a681e7bc96e7a88be8afade8a8800503010102000007e6a087e9a2983303030200′);

CREATE TABLE IF NOT EXISTS ‘fts_test_docsize'(docid INTEGER PRIMARY KEY, size BLOB);

INSERT INTO fts_test_docsize VALUES(1,X’0101′);

INSERT INTO fts_test_docsize VALUES(2,X’0101′);

INSERT INTO fts_test_docsize VALUES(3,X’0101′);

CREATE TABLE IF NOT EXISTS ‘fts_test_stat'(id INTEGER PRIMARY KEY, value BLOB);

INSERT INTO fts_test_stat VALUES(0,X’0303038801′);

PRAGMA writable_schema=OFF;

COMMIT;

3. 表結構和內容分析

fts_test_content：儲存的是完整的資料資訊，預設會建立一個docid的主鍵

CREATE TABLE IF NOT EXISTS ‘fts_test_content'(docid INTEGER PRIMARY KEY, ‘c0title’, ‘c1body’);

sqlite> select * from fts_test_content;

內容如下：

docid|c0title|c1body

1|標題1|Java是全世界最好的變成語言

2|標題2|Android是最牛逼的手機系統

3|標題3|Java是Android應用層的主要程式語言

fts_test_stat：儲存的是FTS table的行數，以及表中所有行和列的符號總數

CREATE TABLE IF NOT EXISTS ‘fts_test_stat'(id INTEGER PRIMARY KEY, value BLOB);

sqlite> select * from fts_test_stat;

內容如下：

id|value

0|0303038801

fts_test_docsize：儲存的是docid以及每一行對列的tokens的數量（docid對應資料的所有符號數）

CREATE TABLE IF NOT EXISTS ‘fts_test_docsize'(docid INTEGER PRIMARY KEY, size BLOB);

INSERT INTO fts_test_docsize VALUES(1,X’0101′);

INSERT INTO fts_test_docsize VALUES(2,X’0101′);

INSERT INTO fts_test_docsize VALUES(3,X’0101’);

sqlite> select * from fts_test_docsize;

內容如下：

docid|size

1|0101

2|0101

3|0101

fts_test_segments：儲存B-樹的非根節點（儲存的是全文索引）

CREATE TABLE IF NOT EXISTS ‘fts_test_segments'(blockid INTEGER PRIMARY KEY, block BLOB);

sqlite> select * from fts_test_segments;

內容無

fts_test_segdir：儲存B-樹的根節點（儲存的是全文索引）

CREATE TABLE IF NOT EXISTS ‘fts_test_segdir'(level INTEGER,idx INTEGER,start_block INTEGER,leaves_end_block INTEGER,end_block INTEGER,root BLOB,PRIMARY KEY(level, idx));

對應的欄位含義如下：

插入資料的語句：

INSERT INTO fts_test_segdir VALUES(0,0,0,0,’0 58′,X’00256a617661e698afe585a8e4b896e7 958ce69c80e5a5bde79a84e58f98e68890e8afade8a8800501010102000007e6a087e9a2983103010200′);

INSERT INTO fts_test_segdir VALUES(0,1,0,0,’0 55′,X’0022616e64726f6964e698afe69c80e7

899be980bce79a84e6898be69cbae7b3bbe7bb9f0502010102000007e6a087e9a2983203020200′);

INSERT INTO fts_test_segdir VALUES(0,2,0,0,’0 65′,X’002c6a617661e698af616e64726f6964e5ba94e7

94a8e5b182e79a84e4b8bbe8a681e7bc96e7a88be8afade8a8800503010102000007e6a087e9a2983303030200′);

sqlite> select * from fts_test_segdir;

0|0|0|0|0 58|00256a617661e698afe585a8e4b896e7

0|1|0|0|0 55|0022616e64726f6964e698afe69c80e7

0|2|0|0|0 65|002c6a617661e698af616e64726f6964

在Android中的使用姿勢

DataDB

packagecom.mob.demo.ftsdb;

importandroid.content.ContentValues;

importandroid.content.Context;

importandroid.database.Cursor;

importandroid.database.DatabaseErrorHandler;

importandroid.database.sqlite.SQLiteDatabase;

importandroid.database.sqlite.SQLiteOpenHelper;

importandroid.text.TextUtils;

importjava.util.ArrayList;

importjava.util.List;

publicclassDataDBextendsSQLiteOpenHelper {

privateSQLiteDatabase db;

publicDataDB(Context context) {

super(context,”db_test_fts.db”,null,1,newDatabaseErrorHandler {

publicvoidonCorruption(SQLiteDatabase sqLiteDatabase) {

//TODO

}

});

db = getWritableDatabase;

}

publicvoidonCreate(SQLiteDatabase sqLiteDatabase) {

//建立虛擬表

sqLiteDatabase.execSQL(“CREATE VIRTUAL TABLE fts_test USING fts4(title, body);”);

db = sqLiteDatabase;

//插入資料

bulkInsert(newString{“標題1″,”標題2″,”標題3”},newString{“Java是全世界最好的變成語言”,”Android是最牛逼的手機系統”,”Java是Android應用層的主要程式語言”});

}

publicvoidonUpgrade(SQLiteDatabase sqLiteDatabase,inti,inti1) {

}

//插入單條資料

publicvoidinsert(String title, String body) {

ContentValues values =newContentValues;

values.put(“title”, title);

values.put(“body”, body);

db.insert(“fts_test”,null, values);

}

//批量插入資料

publicvoidbulkInsert(String titleArray, String bodyArray) {

if(titleArray ==null|| bodyArray ==null|| titleArray.length ==0|| titleArray.length != bodyArray.length) {

return;

}

db.beginTransaction;

for(inti =0; i < titleArray.length; i++) {

ContentValues values =newContentValues;

values.put(“title”, titleArray[i]);

values.put(“body”, bodyArray[i]);

db.insert(“fts_test”,null, values);

}

db.setTransactionSuccessful;

db.endTransaction;

}

//查詢title欄位包含text內容的資料

publicList queryTitle(String text) {

List resultList =null;

Cursor cursor = db.rawQuery(“SELECT * FROM fts_test WHERE title MATCH ‘”+ text +”*’;”,null);

System.out.println(“wenjun cursor title = “+ (cursor ==null?null: cursor.getCount));

if(cursor !=null&& cursor.getCount >0) {

resultList =newArrayList<>;

while(cursor.moveToNext) {

resultList.add(cursor.getString(0));

}

returnresultList;

}

//查詢body欄位包含text內容的資料

publicList queryBody(String text) {

List resultList =null;

Cursor cursor = db.rawQuery(“SELECT * FROM fts_test WHERE body MATCH ‘”+ text +”*’;”,null);

System.out.println(“wenjun cursor body = “+ (cursor ==null?null: cursor.getCount));

if(cursor !=null&& cursor.getCount >0) {

resultList =newArrayList<>;

while(cursor.moveToNext) {

resultList.add(cursor.getString(0));

}

returnresultList;

}

//查詢全文包含text內容的資料

publicList queryAll(String text) {

List resultList =null;

Cursor cursor = db.rawQuery(“SELECT docid, * FROM fts_test WHERE fts_test MATCH ‘”+ text +”*’;”,null);

if(cursor !=null&& cursor.getCount >0) {

resultList =newArrayList<>;

while(cursor.moveToNext) {

resultList.add(String.valueOf(cursor.getString(0)) +” | “+ cursor.getString(1) +” | “+ cursor.getString(2));

}

returnresultList;

}

//獲取包含text內容的記錄數

publiclonggetCount(String text) {

longresult =0;

String match =”;”;

if(!TextUtils.isEmpty(text)) {

match =” WHERE fts_test MATCH ‘”+ text +”*’;”;

}

Cursor cursor = db.rawQuery(“SELECT count(*) FROM fts_test”+ match,null);

if(cursor !=null&& cursor.getCount >0) {

cursor.moveToFirst;

result = cursor.getLong(0);

}

returnresult;

}

結語

全文檢索技術的核心是分詞演算法以及儲存的數據結構，目前Sqlite3 FTS主要使用的是B-樹的儲存方式，其最低搜尋效能O[log2N]

在Android客戶端中可根據實際的業務場景從分詞演算法方面來優化。

參考文獻：

https://www.sqlite.org/fileformat.html#varint_format

http://www.droidsec.cn/特性還是漏洞？濫用-sqlite-分詞器/

[ShareSDK] 輕鬆實現社會化功能強大的社交分享

[SMSSDK] 快速整合簡訊驗證聯結通訊錄社交圈

[MobLink] 打破App孤島實現Web與App無縫連結

[MobPush] 快速整合推送服務應對多樣化推送場景

[AnalySDK] 精準化行為分析 + 多維資料模型 + 匹配全網標籤 + 垂直行業分析顧問

截止2018 年4 月，Mob 開發者服務平臺全球裝置覆蓋超過84 億，SDK下載量超過3,300,000+次，服務超過380,000+款移動應用。

相關推薦