解决的问题
很多有关于通讯录的功能都会有用户搜索数据库，从数据库中模糊查询出用户所需要的信息这样的需求。当需求为可以通过名称、首字母、全拼进行查询时，设计的数据库如下：
| 姓名 | 首字母 | 全拼 |
|---|---|---|
| 天真无邪 | tzwx | tianzhenwuxie |
查询的流程图
但是用着用着就发现了一些查询结果不准确的情况
比如：
用户输入：nc
实际想搜索：内存、农村...
数据库保存的汉字对应的拼音：biancheng
搜索结果：除了本来想通过首字母查询出来的正确匹配项以外，额外会搜索出来“编程”这个匹配项。
以及
用户输入：henqiang
实际想搜索：很强
数据库保存的汉字对应拼音：chenqiang
搜索结果：除了本来想通过首字母查询出来的正确匹配项以外，额外会搜索出来“陈强”这个匹配项。
解决方案
在数据库存储的全拼中插入空格，如：
| 姓名 | 首字母 | 全拼 |
|---|---|---|
| 天真无邪 | tzwx | (字符串头部也要有空格)tian zhen wu xie |
且为用户输入的字符串同样的加上空格，这样处理之后就可以避免了上面可能出现的问题。
但是在为用户输入字符串中加入空格的时候，也同样的遇到了问题，比如：
用户输入：xian
用户可能会有4种想要搜索的内容
| 姓名 | 全拼 |
|---|---|
| 闲 | xian |
| 西安 | xi an |
| 侠女 | xia nv |
| 希阿娜 | xi a na |
为了解决上述的问题，可以写一个字典树，去获取用户输入的所有的查询可能性。
字典树
网络上已经有很多字典树实现的原理了，那么这边就直接上代码
节点
@interface RCYTrieTreeNode : NSObject
//是否可以成为结束的节点
@property (nonatomic, assign) BOOL canBeEnd;
//子节点
@property (nonatomic, strong) NSMutableDictionary *children;
@end
树
插入方法
- (void)insertNodeWithWord:(NSString *)word {
NSMutableArray *words = [[NSMutableArray alloc] init];
for (int i = 0; i < word.length; i++) {
[words addObject:[word substringWithRange:NSMakeRange(i, 1)]];
}
__block RCYTrieTreeNode *node = self.rootNode;
[words enumerateObjectsUsingBlock:^(NSString *ch, NSUInteger idx, BOOL * _Nonnull stop) {
if (!node.children) {
node.children = [[NSMutableDictionary alloc] init];
}
if ([node.children.allKeys containsObject:ch]) { //key中是否有该字符
if (idx == words.count - 1) { //如果是最后一个
RCYTrieTreeNode *endNode = [node.children valueForKey:ch];
endNode.canBeEnd = YES;
}
}
else {
RCYTrieTreeNode *newNode = [[RCYTrieTreeNode alloc] init];
if (idx == words.count - 1) {
newNode.canBeEnd = YES;
}
[node.children setValue:newNode forKey:ch];
}
node = [node.children valueForKey:ch];
}];
}
查找方法
- (RCYTrieTreeNode *)searchTreeWithWord:(NSString *)word {
NSMutableArray *words = [[NSMutableArray alloc] init];
for (int i = 0; i < word.length; i++) {
[words addObject:[word substringWithRange:NSMakeRange(i, 1)]];
}
__block RCYTrieTreeNode *node = self.rootNode;
[words enumerateObjectsUsingBlock:^(NSString *ch, NSUInteger idx, BOOL * _Nonnull stop) {
if ([node.children.allKeys containsObject:ch]) {
node = [node.children valueForKey:ch];
}
else {
node = nil;
*stop = YES;
return;
}
}];
return node;
}
通过字典树获得划分好的数组
切分拼音
+ (void)splitPinYinWithString:(NSString *)string successBlock:(void (^)(NSArray *))successBlock {
RCYTrieTree *tree = [[RCYTrieTree alloc] init];
NSMutableArray *resultArray = [[NSMutableArray alloc] init];
[self PinYinAddSpaceWithTree:tree string:string index:0 resultArray:resultArray];
if (resultArray && successBlock) {
successBlock(resultArray);
}
}
//例如:xianguo -> xian guo, xian gu o, xi an guo, xi an gu o
+ (void)PinYinAddSpaceWithTree:(RCYTrieTree *)tree string:(NSString *)string index:(NSInteger)index resultArray:(NSMutableArray *)resultArray {
NSInteger currentLength = 1;
BOOL isFind = YES;
NSMutableString *resultString = [NSMutableString stringWithString:string];
while (currentLength + index <= string.length) {
NSString *subString = [string substringWithRange:NSMakeRange(index, currentLength)];
RCYTrieTreeNode *node = [tree searchTreeWithWord:subString];
if (!node) {
isFind = NO;
break;
}
if (node.canBeEnd) {
//递归
//一旦找到后分为两个方法，一个为加入空格继续查找，一个为不加空格继续查找 如:字符串xian 查到xi 的时候 一个方法的字符串为 xi an 另一个为 xian
if (index + currentLength != resultString.length) {
NSMutableString *mutableString = [NSMutableString stringWithString:string];
[mutableString insertString:@" " atIndex:currentLength + index];
[self PinYinAddSpaceWithTree:tree string:mutableString index:currentLength + index + 1 resultArray:resultArray];
}
}
currentLength++;
}
if (isFind) {
[resultArray addObject:resultString];
}
}
输入xian
输出结果为：
RCYTrieTree[51502:1416638] (
"xi a n",
"xi an",
"xia n",
xian
)
最后用获取到的数组去数据库里面like查询就好啦。
代码地址：RCYTrieTree
网友评论