关于搜索出来的内容根据权重进行排序

怎么对搜索结果按照最相似的权重排序

Imagem de capa

这是整个功能的流程。

对于这需求要做到百度搜索我呸,谷歌搜索的权重排序,我接到这个需求是拒绝的。后来经过和小伙伴的研究,觉得这个按照权重排序是可以实现的。

下面说一下具体思路。

@[@"abcd",@"1abcd",@"abcd1",@"ab1cd",@"1ab2cd",@"abdc"]

上面是一个数组的字符串,就当是我们查找出来的字符串数组,但是我们要按照我们搜索出来的关键词的相似度进行排序。

假设我们需要搜索的字符串是abcd,对于人眼来说直接包含abcd的是排在最前面的。

但是包含abcd的有abcd,1abcd,abcd1。很明显这三个顺序abcd,abcd1,1abcd.

我们肉眼是可以看出来的但是程序不知道,这就涉及到权重的问题了。

我们按照字母所在的位置进行权重的计算,权重越低的排在最前面。

abcd权重是0+1+2+3 = 6

abcd1权重是0+1+2+3 = 6

1abcd的权重是1+2+3+4 = 10

现在出现了两个权重为6的,但是abcd这个完全和我们输入的一样。abcd1多了一个1,我们按照同样的权重,字符串长度越短越排在前面。

那么这三个字符串排序变成了abcd abcd1 1abcd

剩下的字符串ab1cd 1ab2cd abdc了。

我们进行模糊搜索,但是怎么进行模糊搜索呢?小伙伴说进行输入的文字一个一个的进行查找,找到就超找剩下的。

我们按照这个方法查找ab1cd 1ab2cd两个。

但是这两个怎么排序呢 还是进行权重排序。

ab1cd的权重 0+1+3+4 = 8

1ab2cd的权重是 1+2+4+5 = 12

那么这两个进行权重排序是ab1cd 1ab2cd

剩下的不满足精确搜索和模糊搜索,应该直接过滤掉的但是考虑到可能这个算法有问题就暂时按照字符串的长度进行排序 全部放在最后。

下面是实现的代码。

GBSortSearchCountryManger

对搜索出来的结果进行排序的管理类。

/**
 需要进行排序的数组字符串
 */
@property (nonatomic, strong) NSArray<NSString *> *searchResult;

进行过滤的数据源

/**
 对数据源进行按照权重排序之后的数组

 @param searchText 搜索的字符串
 @return 按照权重排序数组
 */
- (NSArray<NSString *> *)sortSearchResultWithSearchText:(NSString *)searchText;

进行过滤的方法

- (NSArray<NSString *> *)sortSearchResultWithSearchText:(NSString *)searchText {
    _currentSortLevelType = SSCSortLevelTypeExactMatch; // 开始设置精确的搜索
    _currentSearchText = searchText;
    NSMutableArray<GBSortSearchCountryItem *> *sortItems = [NSMutableArray array];
    NSMutableArray<NSString *> *sortTempList = [NSMutableArray array];
    [self.searchResult enumerateObjectsUsingBlock:^(NSString * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        // 组装数据源
        GBSortSearchCountryItem *item = [[GBSortSearchCountryItem alloc] init];
        item.text = obj;
        [sortItems addObject:item];
    }];
    while (_currentSortLevelType <= SSCSortLevelTypeOther) {
        // 当查询的状态大于其他查询就退出
        NSArray *sortItemList = [self sortItemWithLevelType:_currentSortLevelType sortResultItems:sortItems];
        [sortItemList enumerateObjectsUsingBlock:^(GBSortSearchCountryItem *  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
            [sortTempList addObject:obj.text];
        }];
        [sortItems removeObjectsInArray:sortItemList];
        _currentSortLevelType ++;
    }
    return sortTempList;
}

实现方法

/**
 查询当前查询的数据

 @param levelType 查询的类型
 @param items 剩余的数据源
 @return 返回查询出来的对象
 */
- (NSArray<GBSortSearchCountryItem *> *)sortItemWithLevelType:(SSCSortLevelType)levelType
                                              sortResultItems:(NSArray<GBSortSearchCountryItem *> *)items {
    NSMutableArray<GBSortSearchCountryItem *> *sortItems = [NSMutableArray array]; // 保存查询出来的数据源
    switch (levelType) {
        case SSCSortLevelTypeExactMatch: {
            // 精确搜索
            [items enumerateObjectsUsingBlock:^(GBSortSearchCountryItem * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
                NSRange range = [obj.text rangeOfString:_currentSearchText]; // 查询查询的字符串是否在查找的字符串存在
                if (range.location != NSNotFound) {
                    // 如果存在就符合精确查找的结果
                    obj.levelTag = [self exactMatchCountWithRange:range]; // 查找权重
                    [sortItems addObject:obj];
                }
            }];
            sortItems = [NSMutableArray arrayWithArray:[self sortWithList:sortItems]]; // 根据权重进行排序
        }
            break;
        case SSCSortLevelTypeFuzzySearch: {
            // 按照顺序模糊搜索
            [items enumerateObjectsUsingBlock:^(GBSortSearchCountryItem * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
                NSInteger count = [self fuzzySearchLevelTagWithItem:obj]; // 查询模糊搜索的权重 如果是0代表没找到
                if (count != NSNotFound) {
                    obj.levelTag = count;
                    [sortItems addObject:obj];
                }
            }];
            sortItems = [NSMutableArray arrayWithArray:[self sortWithList:sortItems]];
        }
            break;
        case SSCSortLevelTypeOther: {
            [items sortedArrayUsingComparator:^NSComparisonResult(GBSortSearchCountryItem *  _Nonnull obj1, GBSortSearchCountryItem *  _Nonnull obj2) {
                if (obj1.text.length > obj2.text.length) {
                    return NSOrderedDescending;
                }else if(obj1.text.length < obj2.text.length) {
                    return NSOrderedAscending;
                }else {
                    return NSOrderedSame;
                }
            }];
            // 剩余的结果 防止算法有问题 造成数据帅选的bug
            [sortItems  addObjectsFromArray:items];
        }
            break;
        default:
            break;
    }
    return sortItems;
}

根据需要过滤的类型进行过滤

/**
 计算精确搜索出来的权重

 @param range 搜索字符串的位置
 @return 权重
 */
- (NSUInteger)exactMatchCountWithRange:(NSRange)range {
    NSUInteger currentIndex = range.location;
    NSUInteger count = 0;
    while (currentIndex < range.location + range.length) {
        count += currentIndex;
        currentIndex ++;
    }
    return count;
}

计算精确搜索的权重

/**
 查询模糊搜索的权重

 @param item 模糊搜索的字符串
 @return 权重
 */
- (NSUInteger)fuzzySearchLevelTagWithItem:(GBSortSearchCountryItem *)item {
    NSUInteger count = 0; // 权重
    NSUInteger quertCharactersLocation = 0; // 查询字符串所在的位置
    NSString *itemText = item.text; // 需要查找的字符串
    while (quertCharactersLocation < item.text.length) {
        // 当字符串查找完毕跳出循环
        NSString *character = [item.text substringWithRange:NSMakeRange(quertCharactersLocation, 1)]; // 截取查找的字符
        NSRange range = [itemText rangeOfString:character]; // 查找字符所在字符串的位置
        if (range.location == NSNotFound) {
            // 如果没有找到跳出方法
            return NSNotFound;
        }
        count += range.location; // 计算权重
        quertCharactersLocation ++; // 进行下一个字符查找
        itemText = [itemText substringFromIndex:quertCharactersLocation]; // 过滤剩下的字符串 可以根据输入顺序查找
    }
    return count;
}

模糊搜索的权重

/**
 对搜索出来的结果进行排序

 @param list 列表
 @return 根据权重排序之后的列表
 */
- (NSArray<GBSortSearchCountryItem *> *)sortWithList:(NSArray<GBSortSearchCountryItem *> *)list {
    NSMutableArray *sortList = [NSMutableArray arrayWithArray:list];
    [sortList sortUsingComparator:^NSComparisonResult(GBSortSearchCountryItem *  _Nonnull obj1, GBSortSearchCountryItem * _Nonnull obj2) {
        if (obj1.levelTag > obj2.levelTag) {
            // 如果权重高就排在最后
            return NSOrderedDescending;
        }else if (obj1.levelTag < obj2.levelTag) {
            // 权重低就排在最前面
            return NSOrderedAscending;
        }else {
            // 权重一样
            if (obj1.text.length > obj2.text.length) {
                // 字符串长的排在后面
                return NSOrderedDescending;
            }else if (obj1.text.length < obj2.text.length) {
                // 字符串短的排在前面
                return NSOrderedAscending;
            }else {
                // 一样就相等
                return NSOrderedSame;
            }
        }
    }];
    return sortList;
}

根据权重进行排序

我们进行测试。

    NSArray *array = @[@"abcd",@"1abcd",@"abcd1",@"ab1cd",@"1ab2cd",@"abdc"];
    GBSortSearchCountryManger *manger = [[GBSortSearchCountryManger alloc] init];
    manger.searchResult = array;
    NSArray *sortList =  [manger sortSearchResultWithSearchText:@"abcd"];
    [sortList enumerateObjectsUsingBlock:^(NSString * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
        NSLog(@"->>>%@",obj);
    }];
2016-12-19 13:44:11.578 GearBest[5812:189459] ->>>abcd
2016-12-19 13:44:11.579 GearBest[5812:189459] ->>>abcd1
2016-12-19 13:44:11.579 GearBest[5812:189459] ->>>1abcd
2016-12-19 13:44:11.579 GearBest[5812:189459] ->>>ab1cd
2016-12-19 13:44:11.580 GearBest[5812:189459] ->>>1ab2cd
2016-12-19 13:44:11.580 GearBest[5812:189459] ->>>abdc

上面就是权重排序算法的实现。这个算法有点笨拙,如果搜索范围大一定卡的要命,但是对于我们需求只有两百个国家还可以。