這是整個(gè)功能的流程。
對(duì)于這需求要做到百度搜索我呸，谷歌搜索的權(quán)重排序，我接到這個(gè)需求是拒絕的。后來經(jīng)過和小伙伴的研究，覺得這個(gè)按照權(quán)重排序是可以實(shí)現(xiàn)的。
下面說一下具體思路。
@[@"abcd",@"1abcd",@"abcd1",@"ab1cd",@"1ab2cd",@"abdc"]
上面是一個(gè)數(shù)組的字符串，就當(dāng)是我們查找出來的字符串?dāng)?shù)組，但是我們要按照我們搜索出來的關(guān)鍵詞的相似度進(jìn)行排序。
假設(shè)我們需要搜索的字符串是abcd，對(duì)于人眼來說直接包含abcd的是排在最前面的。
但是包含abcd的有abcd,1abcd,abcd1。很明顯這三個(gè)順序abcd,abcd1,1abcd.
我們?nèi)庋凼强梢钥闯鰜淼牡浅绦虿恢?，這就涉及到權(quán)重的問題了。
我們按照字母所在的位置進(jìn)行權(quán)重的計(jì)算，權(quán)重越低的排在最前面。
abcd權(quán)重是0+1+2+3 = 6
abcd1權(quán)重是0+1+2+3 = 6
1abcd的權(quán)重是1+2+3+4 = 10
現(xiàn)在出現(xiàn)了兩個(gè)權(quán)重為6的，但是abcd這個(gè)完全和我們輸入的一樣。abcd1多了一個(gè)1,我們按照同樣的權(quán)重，字符串長(zhǎng)度越短越排在前面。
那么這三個(gè)字符串排序變成了abcd abcd1 1abcd
剩下的字符串ab1cd 1ab2cd abdc了。
我們進(jìn)行模糊搜索，但是怎么進(jìn)行模糊搜索呢?小伙伴說進(jìn)行輸入的文字一個(gè)一個(gè)的進(jìn)行查找，找到就超找剩下的。
我們按照這個(gè)方法查找ab1cd 1ab2cd兩個(gè)。
但是這兩個(gè)怎么排序呢 還是進(jìn)行權(quán)重排序。
ab1cd的權(quán)重 0+1+3+4 = 8
1ab2cd的權(quán)重是 1+2+4+5 = 12
那么這兩個(gè)進(jìn)行權(quán)重排序是ab1cd 1ab2cd
剩下的不滿足精確搜索和模糊搜索，應(yīng)該直接過濾掉的但是考慮到可能這個(gè)算法有問題就暫時(shí)按照字符串的長(zhǎng)度進(jìn)行排序 全部放在最后。
下面是實(shí)現(xiàn)的代碼。
GBSortSearchCountryManger
對(duì)搜索出來的結(jié)果進(jìn)行排序的管理類。
/**
需要進(jìn)行排序的數(shù)組字符串
*/
@property (nonatomic, strong) NSArray<NSString *> *searchResult;
進(jìn)行過濾的數(shù)據(jù)源
/**
對(duì)數(shù)據(jù)源進(jìn)行按照權(quán)重排序之后的數(shù)組
@param searchText 搜索的字符串
@return 按照權(quán)重排序數(shù)組
*/
- (NSArray<NSString *> *)sortSearchResultWithSearchText:(NSString *)searchText;
進(jìn)行過濾的方法
- (NSArray<NSString *> *)sortSearchResultWithSearchText:(NSString *)searchText {
_currentSortLevelType = SSCSortLevelTypeExactMatch; // 開始設(shè)置精確的搜索
_currentSearchText = searchText;
NSMutableArray<GBSortSearchCountryItem *> *sortItems = [NSMutableArray array];
NSMutableArray<NSString *> *sortTempList = [NSMutableArray array];
[self.searchResult enumerateObjectsUsingBlock:^(NSString * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
// 組裝數(shù)據(jù)源
GBSortSearchCountryItem *item = [[GBSortSearchCountryItem alloc] init];
item.text = obj;
[sortItems addObject:item];
}];
while (_currentSortLevelType <= SSCSortLevelTypeOther) {
// 當(dāng)查詢的狀態(tài)大于其他查詢就退出
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;
}
實(shí)現(xiàn)方法
/**
查詢當(dāng)前查詢的數(shù)據(jù)
@param levelType 查詢的類型
@param items 剩余的數(shù)據(jù)源
@return 返回查詢出來的對(duì)象
*/
- (NSArray<GBSortSearchCountryItem *> *)sortItemWithLevelType:(SSCSortLevelType)levelType
sortResultItems:(NSArray<GBSortSearchCountryItem *> *)items {
NSMutableArray<GBSortSearchCountryItem *> *sortItems = [NSMutableArray array]; // 保存查詢出來的數(shù)據(jù)源
switch (levelType) {
case SSCSortLevelTypeExactMatch: {
// 精確搜索
[items enumerateObjectsUsingBlock:^(GBSortSearchCountryItem * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
NSRange range = [obj.text rangeOfString:_currentSearchText]; // 查詢查詢的字符串是否在查找的字符串存在
if (range.location != NSNotFound) {
// 如果存在就符合精確查找的結(jié)果
obj.levelTag = [self exactMatchCountWithRange:range]; // 查找權(quán)重
[sortItems addObject:obj];
}
}];
sortItems = [NSMutableArray arrayWithArray:[self sortWithList:sortItems]]; // 根據(jù)權(quán)重進(jìn)行排序
}
break;
case SSCSortLevelTypeFuzzySearch: {
// 按照順序模糊搜索
[items enumerateObjectsUsingBlock:^(GBSortSearchCountryItem * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
NSInteger count = [self fuzzySearchLevelTagWithItem:obj]; // 查詢模糊搜索的權(quán)重 如果是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;
}
}];
// 剩余的結(jié)果 防止算法有問題 造成數(shù)據(jù)帥選的bug
[sortItems addObjectsFromArray:items];
}
break;
default:
break;
}
return sortItems;
}
根據(jù)需要過濾的類型進(jìn)行過濾
/**
計(jì)算精確搜索出來的權(quán)重
@param range 搜索字符串的位置
@return 權(quán)重
*/
- (NSUInteger)exactMatchCountWithRange:(NSRange)range {
NSUInteger currentIndex = range.location;
NSUInteger count = 0;
while (currentIndex < range.location + range.length) {
count += currentIndex;
currentIndex ++;
}
return count;
}
計(jì)算精確搜索的權(quán)重
/**
查詢模糊搜索的權(quán)重
@param item 模糊搜索的字符串
@return 權(quán)重
*/
- (NSUInteger)fuzzySearchLevelTagWithItem:(GBSortSearchCountryItem *)item {
NSUInteger count = 0; // 權(quán)重
NSUInteger quertCharactersLocation = 0; // 查詢字符串所在的位置
NSString *itemText = item.text; // 需要查找的字符串
while (quertCharactersLocation < item.text.length) {
// 當(dāng)字符串查找完畢跳出循環(huán)
NSString *character = [item.text substringWithRange:NSMakeRange(quertCharactersLocation, 1)]; // 截取查找的字符
NSRange range = [itemText rangeOfString:character]; // 查找字符所在字符串的位置
if (range.location == NSNotFound) {
// 如果沒有找到跳出方法
return NSNotFound;
}
count += range.location; // 計(jì)算權(quán)重
quertCharactersLocation ++; // 進(jìn)行下一個(gè)字符查找
itemText = [itemText substringFromIndex:quertCharactersLocation]; // 過濾剩下的字符串 可以根據(jù)輸入順序查找
}
return count;
}
模糊搜索的權(quán)重
/**
對(duì)搜索出來的結(jié)果進(jìn)行排序
@param list 列表
@return 根據(jù)權(quán)重排序之后的列表
*/
- (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) {
// 如果權(quán)重高就排在最后
return NSOrderedDescending;
}else if (obj1.levelTag < obj2.levelTag) {
// 權(quán)重低就排在最前面
return NSOrderedAscending;
}else {
// 權(quán)重一樣
if (obj1.text.length > obj2.text.length) {
// 字符串長(zhǎng)的排在后面
return NSOrderedDescending;
}else if (obj1.text.length < obj2.text.length) {
// 字符串短的排在前面
return NSOrderedAscending;
}else {
// 一樣就相等
return NSOrderedSame;
}
}
}];
return sortList;
}
根據(jù)權(quán)重進(jìn)行排序
我們進(jìn)行測(cè)試。
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
上面就是權(quán)重排序算法的實(shí)現(xiàn)。這個(gè)算法有點(diǎn)笨拙，如果搜索范圍大一定卡的要命，但是對(duì)于我們需求只有兩百個(gè)國(guó)家還可以。
