背景
前段时间产品锦鲤说APP内要做搜索关键字提示功能，后台由于能(人)力有限，所以这功能由前台来做。
Google搜索
Google、百度这类的搜索引擎，有一堆大佬对它进行优化，它的关键词提示会非常全面和精准，不过原理都差不多，就是利用了trie树。
Trie树
Trie树又称字典树，利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。
假设现在有四个字符串，分别为aa、abc、abcd、ac，我们要在这里面查找某个字符串是否存在，就需要依次遍历这四个字符串。即使像查找“cc”这样和所有的字符串的首字符都不同的字符串也要一个个的比较，那么查询效率就比较低了。
Trie树
图中每一条路径代表一个字符串，每个节点对应字符串中的字符。不过看起来似乎只有三个字符串，很难看出还有abc字符串，所以需要在c节点加一个标志位，表示有一个单词到这里结束了。如果要查询“ab”字符串，当匹配到“b”时，标志位没有表明到这里结束，所以没有“ab”字符串，它是其他字符串的前缀。
节点头文件如下
@interface Node : NSObject
@property (nonatomic, copy) NSString *string;
@property (nonatomic, copy) NSString *character;
@property (nonatomic, assign) BOOL isFinish;
@property (nonatomic, strong, nullable) NSMutableDictionary *children;
- (void)add:(NSString *)str;
@end
character：当前节点的字符
string：这条路径上到当前字符前的所有字符
isFinish：字符串是否结束
children：存放了后续所有路径的首字符
@implementation Node
+ (Node *)initWithValue:(NSString *)str parent:(Node *)node
{
Node *n = [[Node alloc] init];
n.character = str;
n.string = [NSString stringWithFormat:@"%@%@", node.string, node.character];
return n;
}
- (instancetype)init
{
if (self = [super init]) {
self.children = [NSMutableDictionary dictionary];
self.character = @"";
self.string = @"";
}
return self;
}
- (void)add:(NSString *)str
{
if (!self.children[str]) {
self.children[str] = [Node initWithValue:str parent:self];
}
}
@end
image.png
trie树只有两个功能，一个是添加字符串生成trie树，另一个就是在trie树种匹配字符串。创建一个管理类来处理trie树，并提供这两个方法。
@interface searchManager : NSObject
- (void)insert:(NSString *)word;
- (NSArray *)find:(NSString *)word;
@end
管理类的实现。
- (instancetype)init
{
if (self = [super init]) {
self.root = [[Node alloc] init];
}
return self;
}
这个root节点就是根节点，它不包含任何字符，所有的字符路径都从root根节点开始。
- (void)insert:(NSString *)word
{
if (word.length == 0) {
return;
}
word = [word lowercaseString];
Node *node = self.root;
int index = 0;
NSString *str = @"";
while (index < word.length) {
str = [word substringWithRange:NSMakeRange(index, 1)];
if (!node.children[str]) {
[node add:str];
}
node = node.children[str];
index++;
}
node.isFinish = YES;
}
- (NSArray *)find:(NSString *)word
{
if (word.length == 0) {
return @[];
}
word = [word lowercaseString];
Node *node = self.root;
int index = 0;
NSString *str = @"";
while (index < word.length) {
str = [word substringWithRange:NSMakeRange(index, 1)];
if (node.children[str]) {
node = node.children[str];
index++;
} else {
break;
}
}
if (index == word.length) {
NSMutableArray *arr = [NSMutableArray array];
[self addAllData:node arr:arr];
return arr;
}
return @[];
}
- (void)addAllData:(Node *)node arr:(NSMutableArray *)arr
{
if (node.isFinish) {
[arr addObject:[NSString stringWithFormat:@"%@%@", node.string, node.character]];
}
NSArray *arrKey = node.children.allKeys;
for (int i = 0; i < arrKey.count; i++) {
Node *n = node.children[arrKey[i]];
if (n.children.count > 0) {
[self addAllData:n arr:arr];
} else {
[arr addObject:[NSString stringWithFormat:@"%@%@", n.string, n.character]];
}
}
}
image.png
到这里，trie树的基本功能都已完成，接下来就验证一下trie树的正确性和效率。
和系统方法做对比
我从某学习网站获取了1327条课程名称，先用系统方法遍历一下看看效率如何
- (void)systemFind:(NSArray *)array
{
NSMutableArray *arr = [NSMutableArray array];
NSString *str = @"";
NSLog(@"开始....");
for (int i = 0; i < array.count; i++) {
str = array[i];
if ([str hasPrefix:@"java"] || [str hasPrefix:@"JAVA"] || [str hasPrefix:@"Java"]) {
[arr addObject:str];
}
}
NSLog(@"结束....");
self.result1 = arr;
}
2019-05-19 13:40:33.064389+0800 trie树[9817:359745] 开始....
2019-05-19 13:40:33.064886+0800 trie树[9817:359745] 结束....
1327条里匹配了19条数据，耗时0.000497s。
- (void)trieFind:(NSArray *)array
{
NSLog(@"开始4----------");
searchManager *model = [[searchManager alloc] init];
for (int i = 0; i < array.count; i++) {
[model insert:array[i]];
}
NSMutableArray *arr = [NSMutableArray array];
NSLog(@"开始3----------");
[arr addObjectsFromArray:[model find:@"java"]];
NSLog(@"结束3----------");
self.result2 = arr;
}
2019-05-19 20:55:57.287762+0800 trie树[10390:399224] 开始3----------
2019-05-19 20:55:57.288423+0800 trie树[10390:399224] 结束3----------
trie树搜索，耗时0.000661s，数据太少，体现不出优势，将核心查询方法循环10w次，再比较两者的消耗时间。
// 系统方法：16.148049s
// 2019-05-19 21:04:46.893443+0800 trie树[10522:406446] 开始....
// 2019-05-19 21:05:03.041492+0800 trie树[10522:406446] 结束....
// trie树：41.086426s
// 2019-05-19 21:05:03.084477+0800 trie树[10522:406446] 开始3----------
// 2019-05-19 21:05:44.170903+0800 trie树[10522:406446] 结束3----------
trie树优化
这样就可以有效的降低查询的递归深度。
- (void)optimization
{
Node *node = self.root;
NSArray *arrKey = node.children.allKeys;
for (int i = 0; i < arrKey.count; i++) {
[self optimization:node.children[arrKey[i]]];
}
}
- (BOOL)optimization:(Node *)node
{
NSArray *arrKey = node.children.allKeys;
if (arrKey.count == 0) {
return YES;
}
for (int i = 0; i < arrKey.count; i++) {
Node *n = node.children[arrKey[i]];
if ([self optimization:n]) {
if (n.children.count == 0 && arrKey.count == 1 && !node.isFinish) {
Node *n2 = [node.children.allValues lastObject];
node.character = [NSString stringWithFormat:@"%@%@", node.character, n2.character];
node.children = nil;
return YES;
}
}
}
return NO;
}
在最终生成的trie树之后调用该方法进行缩点优化，再来看看10w次查询耗时
// 3.814531s
// 2019-05-19 21:08:43.831729+0800 trie树[10582:409365] 开始3----------
// 2019-05-19 21:08:47.646260+0800 trie树[10582:409365] 结束3----------
不到4秒就可以循环10w次查询1327条数据了，1秒大约可以查询3300w条。具体的查询效率需要根据实际的数据来看，极端情况下如果3300w条数据的首字符都不相同，那就需要依次对比每个字符串。
代码
网友评论