高效的联想词系统
起因
最近自己写了一个查单词的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可以更早的避开无关项。