高效的联想词系统
起因
最近自己写了一个查单词的App，需要一个联想词系统。为了加快检索速度，需要在内存中映射一个检索系统。
举个例子
传统方法
搜索Test
- 当输入
t-> 用CoreData检索word开头是t的数据 - 当输入
e-> 用CoreData检索word开头是te的数据 - 当输入
s-> 用CoreData检索word开头是tes的数据 - 当输入
t-> 用CoreData检索word开头是test的数据
当然，可以简化一些，在step 2中可以在step 1中得到的值继续检索。
使用联想词系统
只需要在第一次的时候检索即可。
由于都使用数组储存，例如"Task"和"Tap"会占用7个位置，而通过联想词系统，只会占用T->a->s->k->p，即5个位置。
联想词系统通过多个HashTable组成数组。并且由于是异步调用，所以存入大量数据时候不会对其他有影响。
而且，输出数据无需排序，就按照关联比重排列
关联比重：与搜索词长度更接近
实现
思路
- 通过一个HashTable储存数据。
- 深度遍历HashTable
HashTable内包含String或HashTable两种类型。
String即代表这是一个单词。
问题
- 在修改的时候，需要一个值不停的更改其引用，但是Dict不是引用类型。
- 通过String表示单词会占用大量空间。
- 使用Enum处理Swift和Dict复杂，不易实现。
最终方案
使用了自定义的字母表，字母表是一个类，所以是引用类型。字母表内有个HashTable，以单词为key，另外一个HashTable为值。还有一个Word table，是一个数组，内部传入是单词的key。
举个例子
存入单词Test，首先处理一下，变成t->e->s->t(lower case)。
然后变成这样：
["t" : LetterTable] // WA.letterTable.hashTable
["e" : LetterTable] // Line1 -> LetterTable.hashTable
["s" : LetterTable] // Line2 -> LetterTable.hashTable
["t" : LetterTable] // Line3 -> LetterTable.hashTable
["t"] // Line2 -> LetterTable.wordTable
大概就是这样一层一层嵌套。
存入数据
Model建好了，思路也有了，下面就是算法实现了。
首先在函数内设置一个临时的字母表，引用自self.letterTable。
然后遍历传入单词，需要进行类型转换和大小写转换。
然后调用letterTable的add方法，返回下一个字母应该加入的表，如果是最后一个字母，就将这个字母加入对应的wordtable。
读取数据
首先，我们要获取读取单词最后对应的表，即改表前面的字母组成起来是获取单词。然后在此期间，如果发现读取单词是在字母表内，就先把它加入结果数组。
然后要用到深度优先遍历，安装最后一个表中的hashtable一个遍历下去，一直到该分支的hashtable是空的。每一次要为下一次递归传入上次已组好的单词。
速度
在少量数据的情况下，直接遍历数组，用hasprefix更快。但是当数量达到万级时候，使用WA速度可以快300倍左右。因为，WA可以更早的避开无关项。