My technology blog

起因

最近自己写了一个查单词的App,需要一个联想词系统。为了加快检索速度,需要在内存中映射一个检索系统。

举个例子

传统方法

搜索Test

  1. 当输入t -> 用CoreData检索word开头是t的数据
  2. 当输入e -> 用CoreData检索word开头是te的数据
  3. 当输入s -> 用CoreData检索word开头是tes的数据
  4. 当输入t -> 用CoreData检索word开头是test的数据

当然,可以简化一些,在step 2中可以在step 1中得到的值继续检索。

使用联想词系统

只需要在第一次的时候检索即可

由于都使用数组储存,例如"Task""Tap"会占用7个位置,而通过联想词系统,只会占用T->a->s->k->p,即5个位置。

联想词系统通过多个HashTable组成数组。并且由于是异步调用,所以存入大量数据时候不会对其他有影响。

而且,输出数据无需排序,就按照关联比重排列

关联比重:与搜索词长度更接近

实现

思路

  1. 通过一个HashTable储存数据。
  2. 深度遍历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可以更早的避开无关项

You’ve successfully subscribed to UTS Blog
Welcome back! You’ve successfully signed in.
Great! You’ve successfully signed up.
Your link has expired
Success! Check your email for magic link to sign-in.