【专家坐堂】Android FTS 实现方案（下篇）

本文来自网易云社区

作者：苏甦

查询结果高亮处理

可以使用SQLite提供的Snippet功能，但很难控制ellipses的位置，在结果显示时，由于文本控件的大小位置在不同机型上的不确定性，ellipses还是由UI层去处理比较合适。

还可以使用matchinfo，但最大的问题是JAVA层使用的是UNICODE，而SQLite的matchinfo的位置信息是基于UTF-8编码，做反向转换比较繁琐。

如果查询结果中包含了比较多的数据记录，而界面不可能同时展示这么多的数据记录，可以在界面绘制时，动态的计算高亮的位置并缓存下来。

高亮处理，就是计算查询串在内容串中的命中的区域集合，比如命中区域集合是[0,3),[5,6),[10,14)。区域按从小到大排序，区域之间不交叠，如果交叠了，可以被合并成更大的区域。

在前边的"查询文本处理"章节里介绍了用户输入的查询串的处理流程。而命中区域集合的确定也是类似的。

• 同处理用户输入的查询串，把用户输入的查询串切分为一个词组的列表，对每个词组进行分词，产生一个token的列表，也就是一个token的二维数组，允许词组中的最后一个token进行前缀匹配。
• 检索到的内容串，通过分词器进行分词，产生一个token列表。
• 针对每一个词组的token列表，与内容token列表进行匹配，逻辑类似于String.indexOf，区别在于对于词组中的最后一个token，允许前缀匹配。
• 把每个查询词组匹配到的击中区域进行合并。最后得到一个区域的集合。

public final class FTSQuery {
    public static final String[][] queryToken(String str) {
        String[] querys = breakQuery(str);
        if (querys == null || querys.length == 0) {
            return null;
        }

        List<String[]> tokens = new ArrayList<String[]>(10);

        for (String query : querys) {
            if (!TextUtils.isEmpty(query)) {
                String[] toks = tokenize(query);

                if (toks != null && toks.length > 0) {
                    tokens.add(toks);
                }                
            }
        }

        String[][] aToken = new String[tokens.size()][];
        tokens.toArray(aToken);

        return aToken;
    }

    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;
    }

    private static final String[] tokenize(String str) {
        List<String> tokens = new ArrayList<String>(str.length());

        int[] tok = new int[2];
        int start = 0;
        int end = str.length();
        while ((start = Tokenizer.tokenize(str, start, end, tok)) != -1) {
            tokens.add(str.substring(tok[0], tok[1]));
        }

        String[] aTokens = new String[tokens.size()];
        tokens.toArray(aTokens);

        return aTokens;
    }
}

public final class FTSQuery {
    public static final int[] hitRanges(String str, String[][] tokens) {
        List<Integer> ranges = new ArrayList<Integer>(10);

        int[] range = new int[2];
        for (String[] toks : tokens) {
            if (hitRange(str, toks, range)) {
                RangeMerge.merge(range, ranges);
            }
        }

        int[] aRanges = new int[ranges.size()];
        for (int i = 0; i < ranges.size(); i++) {
            aRanges[i] = ranges.get(i);
        }

        return aRanges;
    }

    private static final boolean hitRange(String str, String[] tokens, int[] range) {
        int end = str.length(); // avoid call
        int[] tok = new int[2]; // shared
        range[0] = -1; // mark
        int sourceIndexAnchor = -1; // source index when match first token

        int tokenIndex = 0; // token index
        int sourceIndex = 0; // source token index
        while (tokenIndex < tokens.length && sourceIndex != -1) { // both in range
            // extract token
            sourceIndex = Tokenizer.tokenize(str, sourceIndex, end, tok);
            if (sourceIndex == -1) { // no more token
                break;
            }

            // match token
            boolean match = matchToken(str, tok, tokens[tokenIndex], tokenIndex == tokens.length - 1);
            if (match) {
                if (tokenIndex == 0) { // first
                    // save
                    sourceIndexAnchor = sourceIndex;

                    // range as first
                    range[0] = tok[0];
                    range[1] = tok[1];
                } else {
                    if (range[1] != tok[0]) { // violate 'source adjacent' rule
                        match = false;
                    } else {                        
                        // extend end
                        range[1] = tok[1];
                    }
                }
            }            

            if (match) {
                // next token
                tokenIndex++;               
            } else {
                // can't match more
                if (tokenIndex != 0) {
                    tokenIndex = 0;

                    // to source index when match first token
                    sourceIndex = sourceIndexAnchor;
                }
            }
        }

        return tokenIndex >= tokens.length;
    }

    private static final boolean matchToken(String str, int[] tok, String token, boolean prefix) {
        int diff = tok[1] - tok[0] - token.length();
        if (diff < 0 || diff > 0 && !prefix) {
            return false;
        }

        // todo avoid sub string
        if (token.compareToIgnoreCase(str.substring(tok[0], tok[0] + token.length())) != 0) {
            return false;
        }

        tok[1] -= diff;

        return true;
    }
}

/*package*/ final class RangeMerge {
    public static final void merge(int[] range, List<Integer> ranges) {
        // empty
        if (ranges.isEmpty()) {
            ranges.add(range[0]);
            ranges.add(range[1]);

            return;
        }

        //
        // for start and end of new range, locate start and end range in ranges
        // 'start' & 'end' is the index of range list, if the index is even, it's 'in' range, if the index is odd, it's 'after' range
        //

        int start = 0;
        for (; start < ranges.size() && range[0] >= ranges.get(start); start++) {}
        start--;

        int end = start + 1; // no need from begin, cause end > start
        for (; end < ranges.size() && range[1] >= ranges.get(end); end++) {}
        end--;

        boolean startAfter = (start & 1) != 0;
        boolean endAfter = (end & 1) != 0;

        // start & end after the same range
        if (startAfter && start == end) {
            // extend range
            if (start != -1 && ranges.get(start) == range[0]) {
                ranges.set(start, range[1]);
            } else { // insert range
                ranges.add(start + 1, range[0]);
                ranges.add(start + 2, range[1]);
            }
        } else {
            // end after a range, extend range with new end
            if (endAfter) {
                ranges.set(end, range[1]);
            }

            // start before all ranges or after a range and unable to merge
            // extend start of next range and move to next range (end range must exists)
            // if need to merge, don't move to next range, and no need to extend start of next range
            if (startAfter && (start == -1 || ranges.get(start) != range[0])) {
                ranges.set(start + 1, range[0]);
                start += 2;
            }

            // merge ranges
            // i.ex. S1 E1 S2 E2 -> S1 E2
            // start index must be end of range, that's index is odd
            int index = start + (startAfter ? 0 : 1);
            // count to remove
            int count = end - start + (startAfter ? (endAfter ? 0 : 1) : (endAfter ? -1 : 0));
            while (count-- > 0) {
                ranges.remove(index);
            }
        }
    }
}

索引数据统计

这部分是辅助调试的逻辑。SQLite提供了另一个功能fts4aux，可以帮助查询token的数据。

CREATE VIRTUAL TABLE IF NOT EXISTS FtsIndex_token USING fts4aux(FtsIndex)

可以查询token的数量

SELECT count(*) FROM FtsIndex_token where col='*'

网易云免费体验馆，0成本体验20+款云产品！

更多网易研发、产品、运营经验分享请访问网易云社区。