最新博客
最新资源下载
【专家坐堂】Android FTS 实现方案（上篇）
叁叁肆2018-09-19 14:26本文来自网易云社区
作者：苏甦
在Android开发中，遇到搜索的需求，可以考虑FTS的方案。
名词解释
- FTS Full-Text Search 全文检索
- tokenizer 分词器
- token 被检索内容输入分词器后产生的分词
- FTS3/FTS4 SQLite中支持FTS的虚拟表
SQLite FTS 支持
SQLite是支持FTS的，具体的文档在 https://www.sqlite.org/fts3.html 上可以找到，这里简要的总结下。
- SQLite支持FTS3(3.5.0)和FTS4(3.7.4)
- FTS3和FTS4是virtual table modules，创建的表是虚拟表，同时SQLite会创建几个隐藏的表。
- FTS表创建语句中的主键，索引都会被丢弃。
- FTS查询时使用match关键字。
- 可以指定表使用的分词器。
- 可以注入自定义分词器。
Android SQLite FTS 支持
参考这个变动 https://android.googlesource.com/platform/external/sqlite/+/c82acac4e67711e8d9289b572d334298aeb5d806，绝大多数Android版本支持到FTS4。
参考这个变动 https://android.googlesource.com/platform/external/sqlite/+/a586535b4c1fa23e280ff9a188671113f900b48b%5E%21/#F0，绝大多数Android版本不支持自定义分词器的注入。
结论就是，如果不需要自定义分词器，那么Android的FTS支持完全够用，如果需要自定义分词器，那就得找其他的办法了。
实现方案-不需要自定义分词
如果不需要自定义分词，那么可以使用SQLite自带的内建分词器。
- simple/porter 具体查询SQLite文档。
- icu 使用ICU break rules分词。参考这个变动 https://android.googlesource.com/platform/external/sqlite/+/399dce677c821a43476eac5e07da340669d82321%5E%21/#F0 Android开始支持ICU分词器
- unicode61 SQLite在3.7.13之后才支持，Android的支持，可以查阅相关文档。
实现方案-需要自定义分词
讨论一种可行性
需要自定义分词，但同时又使用Android SQLite，有没有一种方案可以满足呢？我们先使用外部分词器产生token，再把token重新拼装，而同时使用SQLite的内建simple分词器，那么问题在于simple分词器如何处理我们拼装过的内容。simple的算法，简单说，就是在ASCII范围内设定哪些字符是分隔符，然后找到连续的非分隔符做为一个token，跳过所有的分隔符和非ASCII。这样导致一个问题，所有非ASCII的字符全部被丢弃掉。假设我们分词后产生中文的token，那么再次拼装后，中文会被丢弃。这样，如果需要自定义分词的话，使用Android SQLite是做不到的。
编译SQLite
自行编译Android SQLite，详细的编译过程不描述，这里注意在源码基础上，加上-DSQLITE_ENABLE_FTS3_TOKENIZER这个宏定义。
封装SQLite
可以选择移植Android SQLite的封装代码来封装新编译的的SQLite库。也可以选择直接调用SQLite的C API来实现业务逻辑。具体看模块的定位，如果是出于扩展Android SQLite的目的，那采用移植比较好，这样在使用上，就如同采用SQLCipher一样，只需要更换掉导入的包名就可以。如果只是实现单一的搜索的功能，那只就直接使用SQLite的C API就可以。具体的在JNI封装章节会提到。
注入分词器
这里先假定实现了一个SQLite的分词器，也就是实现了sqlite3_tokenizer_module，具体内容在后续的实现分词器章节讲述。编译Android SQLite中，打开了SQLITE_ENABLE_FTS3_TOKENIZER这个开关，目的就是启用SQLite的fts3_tokenizer函数。具体参考SQLite文档。
SELECT fts3_tokenizer("my_tokenizer", "my_sqlite3_tokenizer_module_address")。
调用是针对某个SQLite连接的，也就是sqlite3*。每次打开一个连接，需要做分词器的注入。
数据库表设计
存在数据库的数据，并不是所有的数据都需要做索引的，也包含其他的数据。有如下的考虑点
- FTS3创建的表，所有列都必须进行索引，也就是所有的列都必须进入分词器进行分词，这样，会增加数据插入时分词器的调用次数，增加索引表的数据大小。而FTS4创建的表，是支持哪些列不索引的，可以使用notindexed选项。
- FTS3/4创建的表，所有主键和索引会被丢弃。如果查询业务不仅仅是搜索，还需要按照某个列查询的话，只建立FTS索引表是不够的。
- 可以采用建立FTS表和其他信息表的方式。
public final class IndexRecord {
public String content;
public String sid;
public int iid;
}
创建表和索引
// 创建索引表，使用自定义分词器，仅包含有一个content列，content进入索引，同时表还包含一个隐藏列docid
CREATE VIRTUAL TABLE IF NOT EXISTS FtsIndex USING fts4(content, tokenize=my_tokenizer);
// 创建数据表，使用docid做为主键，docid与索引表中的docid对应，包含status列，用来标记状态，包含另外两个数据列
CREATE TABLE IF NOT EXISTS FtsMeta(docid INTEGER PRIMARY KEY, status INT DEFAULT 0, sid TEXT, iid INT);
// sid列索引
CREATE INDEX IF NOT EXISTS FtsMeta_sid ON FtsMeta(sid);
// iid列索引
CREATE INDEX IF NOT EXISTS FtsMeta_iid ON FtsMeta(iid);数据更新
插入
先插入FtsIndex表，得到插入行的docid，再插入FtsMeta表。// 插入索引内容
INSERT INTO FtsIndex(content) values(?)
// 数据库变动
changes()
// FtsIndex docid
last_insert_rowid()
// 插入数据表
INSERT INTO FtsMeta(docid, sid, iid) values(?, ?, ?)
删除
删除单条记录，先删除FtsIndex表，再删除FtsMeta表。// 根据iid删除
DELETE FROM FtsIndex WHERE docid in (SELECT docid FROM FtsMeta WHERE iid=?)
// 根据iid删除
DELETE FROM FtsMeta WHERE iid=?删除一批记录，标记FtsMeta表status列。
// 根据sid标记删除
UPDATE FtsMeta SET status=1 WHERE sid=?
由于SQLite中int的存储方式使用varint，负数占用最大长度，所以以0做为正常状态，以1做为删除状态。
索引数据的删除的代价很大，所以在批量删除时，选择标记删除的方式。
数据查询
查询语句
查询符合查询关键字的所有有效记录SELECT sid,iid,content FROM FtsMeta LEFT OUTER JOIN FtsIndex USING(docid) WHERE docid IN (SELECT docid FROM FtsIndex WHERE content MATCH ?) AND status=0查询文本处理
用户端输入的任意查询字符串需要经过处理。在一次FTS查询中，输入给MATCH的参数会通过分词器进行分词。这里需要提到几个查询方式，做简要介绍，详细的参考SQLite文档。
- prefix query 前缀查询，查询的token可以做为索引token的前缀子串，需要在查询token后面追加*
- phrase query 词组查询，词组是由一串token组成的，一个查询词组和索引匹配，需要词组中的token按照同样的顺序出现在索引中。需要用""包含。
- set operations 集合操作，多个查询字符串的集合操作，比如AND。
查询字符串处理流程
- 由于*是做为前缀查询关键字，替换所有*为空白符。
- 按照不可见字符做为分隔符拆分。
- 针对拆分出来的字符串，按照词组查询，并允许最后一个token前缀查询。
- 针对拆分出来的每个词组查询，做AND操作，AND是隐式操作，直接按照空格衔接。
public final class FTSQuery {
public static final String queryString(String str) {
String[] querys = breakQuery(str);
if (querys == null || querys.length == 0) {
return "";
}
StringBuilder sb = new StringBuilder(32);
for (String query : querys) {
if (!TextUtils.isEmpty(query)) {
sb.append('"');
sb.append(query);
sb.append("*\" ");
}
}
return sb.toString();
}
private static final Pattern QUERY_PATTERN = Pattern.compile("\\s+");
private static final String[] breakQuery(String query) {
if (query != null) {
query = query.trim();
}
return !TextUtils.isEmpty(query) ? QUERY_PATTERN.split(query.replace('*', ' ')) : null;
}
}实现分词器
可以找到很多分词器的方案，但都需要词库的支持。字母和数字比较好处理，针对中文，可以采用单字切的方式。也就是一个中文字符做为一个token，这样就不需要词库的支持了，优点是怎么样都能匹配到，缺点是SQLite中的记录一个token命中的document数量很多，但是token总数是有限的。这里不讨论了，具体可以SQLite中FTS相关文档中的B-TREE节点部分。
SQLite的字符数据通常采用UTF-8编码。针对中文，或者说非ASCII字符，都使用单字符分词切分，探测也很简单，直接扫描第一个字节有多少个1的位。而针对ASCII字符，我们可以分为三类，一类是分隔符，直接丢弃，比如0x20，一类是单字符token，既做为分隔符，又做为token，比如#，最后一类是连续token字符，通常就是字母和数字，'0'-'9'，'a-z'，'A-Z'。
C版本实现
tokenizer_cursor *cursor = (tokenizer_cursor *) pCursor;
tokenizer *tokenizer = (tokenizer *) pCursor->pTokenizer;
unsigned char *input = (unsigned char *) cursor->pInput;
int iStartOffset = -1;
while (cursor->iOffset < cursor->nBytes) {
unsigned char c = input[cursor->iOffset];
if (c < 0x80) {
int config = tokenizer->configs[c];
if (config == 0) { // continuous token
// begin
if (iStartOffset == -1) {
iStartOffset = cursor->iOffset;
}
// next
cursor->iOffset++;
} else if (config > 0) { // single token
// catch it
if (iStartOffset == -1) {
iStartOffset = cursor->iOffset++;
}
// if break continuous token, catch it in next turn
break;
} else { // space
if (iStartOffset != -1) {
// break continuous token, skip it in next turn
break;
} else {
// skip
cursor->iOffset++;
}
}
} else {
if (iStartOffset == -1) {
iStartOffset = cursor->iOffset;
int length = 0;
for (; c & 0x80; c <<= 1, length++) {}
int remain = cursor->nBytes - cursor->iOffset;
cursor->iOffset += length > remain ? remain : length;
}
break;
}
}
JAVA版本实现（在查询结果高亮处理章节会用到）
/*package*/ final class Tokenizer {
public static final int tokenize(String str, int start, int end, int[] token) {
int tok = -1;
while (start < end) {
char c = str.charAt(start);
if (c < 0x80) {
int config = configs[c];
if (config == 0) { // continuous token
// begin
if (tok == -1) {
tok = start;
}
// next
start++;
} else if (config > 0) { // single token
// catch it
if (tok == -1) {
tok = start++;
}
// if break continuous token, catch it in next turn
break;
} else { // space
if (tok != -1) {
// break continuous token, skip it in next turn
break;
} else {
// skip
start++;
}
}
} else {
if (tok == -1) {
tok = start++; // todo what about UCS4 ?
}
break;
}
}
if (tok != -1) {
token[0] = tok;
token[1] = start;
return start;
}
return -1;
}
}JNI封装
封装部分有如下
- Android上，配置SQLite在多线程方式运行。类似的，配置SQLite在多线程方式下运行。
- Android上，使用SQLiteConnectionPool管理数据库连接，保证一个SQLiteConnection同时只能被一个线程使用。类似的，如果只有一个连接，需要保证连接的使用在多线程下的问题。
- 由于查询结果数据需要填充到JAVA层，比如文章中的IndexRecord类，这里可以缓存掉jfieldID，这样不需要每次都通过JNIEnv查找。当然这里注意，不要缓存掉jclassID，而jfiedldID在class unload时也会失效，但在Android中，如果class是存放在主DEX中，那么基本可以忽略这个问题，这里更加详细的问题，可以查阅JNI规范相关文档。
- SQLite错误码通过JNI层抛出异常给JAVA层，比如SQLITE_BUSY是一定需要处理的。这里提下，Android封装SQLite时，把busy的超时设置在了2500ms。有兴趣可以查阅源码。
网易云免费体验馆，0成本体验20+款云产品！
更多网易研发、产品、运营经验分享请访问网易云社区。
