Android 淘气三千传之——Android搜索中前缀匹配的一点理解

目录

1、前言

2、相关知识点

3、内容

4、问题

5、总结

6、参考文章 & 推荐阅读

1、前言

咳咳，当我们在浏览器、在手机的电话联系人界面等等地方，输入一段字符串之后，就可以匹配出相应前缀的结果出来（如使用 AutoCompleteTextView 输入字段就会有相应的结果匹配），在存储本地数据的时候，由于数据后期可能会变多，所以需要进行缓存或者添加数据库索引，（量级肯定不能和服务端相比），由于是需要通过前缀关键字来搜索得到结果，所以具有一定的特殊性，所以对缓存和索引的知识点简单地梳理了一下。

2、相关知识点

我们的目的都是为了提高数据检索效率，既然是前缀，符合这个特征的，映入脑海的首先是 Trie 了，同时，我们需要考虑的还有空间、时间，涉及到的一共有以下知识点：

• Trie
• Hash Tree
• 索引
• 三叉树 （Ternary Search Trie）
• 番外：fm-index

3、内容

1） Trie （前缀树、字典树）

注：图片来自 http://www.sciencedirect.com/science/article/pii/S1570866703000662

Trie 作为比较常见的数据结构，包含了以下特点：

• 根为空，不包含字符
• 从根到某一个节点连接起来是一个字符串
• 插入时间为 O（n） n 是字符串长度

我们可以尝试写一个简单的Trie，构造的 Trie 如下：

public class TrieNode {public int path; // 多少个字符串有经过这个节点public int end;  // 多少个字符串以这个节点结束public TrieNode[] map;public TrieNode() {path = 0;end = 0;map = new TrieNode[26];}
}

public class Trie {private TrieNode root;private List<String> result;private StringBuilder stringBuilder = new StringBuilder();public Trie() {root = new TrieNode();}public void insert(String word) {if (word == null) {return;}char[] chs = word.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (node.map[index] == null) {node.map[index] = new TrieNode();}node = node.map[index];node.path++;}node.end++;}public List<String> searchStr(String word) {if (word == null) {return null;}char[] chs = word.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';stringBuilder.append(chs[i]);if (node.map[index] == null)return null;node = node.map[index];}if (node.path != 0) {result = new ArrayList<>();if (node.end != 0)result.add(stringBuilder.toString());getStr(node);return result;} else {return null;}}//通过 DFS 对树进行搜索private