怎么使用倒排索引极速提高字符串搜索效率

grandyang 阅读:107 2022-12-27 15:29:36 评论:0

在Python中,如果要判断一个字符串是否在另一个字符串里面,我们可以使用in关键字,例如:

>>> a = '你说我是买苹果电脑,还是买windows电脑呢?' >>> if '苹果' in a: ...  print('苹果这个词在a字符串里面') ... 苹果这个词在a字符串里面

如果有多个句子和多个关键字,那么可以使用for循环来实现:

sentences = ['你说我是买苹果电脑,还是买windows电脑呢?',               '人生苦短我用Python',               '你TM一天到晚只知道得瑟',              '不不不,我不是说你,我是说在座的各位都是垃圾。'              '我cnm你个大sb'             ] keywords = ['垃圾', 'cnm', 'sb', 'TM'] for sentence in sentences:     for keyword in keywords:         if keyword in sentence:             print(f'句子: 【{sentence}】包含脏话:【{keyword}】')

运行效果如下图所示:

怎么使用倒排索引极速提高字符串搜索效率

现在如果有100000000个句子,有1000个关键字,那么你需要对比1000亿次才能全部查询完成。这个时间代价太大了,如果Python一秒钟能运行500万次查询(实际上没有这么快),那么1000亿次查询需要20000秒,接近6小时。而且,由于in关键字的时间复杂度为O(n),如果有大量长句子,查询时间会更长。

例如,我们要从下面的句子里面寻找cnm。

sentences = ['你说我是买苹果电脑,还是买windows电脑呢?',               '人生苦短我用Python',               '你TM一天到晚只知道得瑟',              '不不不,我不是说你,我是说在座的各位都是垃圾。',              '我cnm你个大sb',              '各位同学,Good Morning!',              '网络这个单词,它的英文为Network',              '我不想听到有人说cnm!'             ]

如果使用常规方法,那么我们的做法是:

  1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

  2. cnm在你说我是买苹果电脑,还是买windows电脑呢?中吗?不在!

  3. cnm在人生苦短我用Python吗?不在!

  4. ……

  5. ……

  6. cnm在我cnm你个大sb吗?在!

  7. cnm在各位同学,Good Morning!吗?不在!

  8. CMN在网络这个单词,它的英文为Network吗?不在!

  9. cnm在我不想听到有人说cnm!吗?在!

于是就知道了,cnm在sentences列表下标为4和7的这两个句子中。

下面,我们换一个看起来更笨的办法:

要找到cnm在哪几句里面,可以变成:寻找C、N、M这三个字母在哪几句里面。然后,再找到同时有这三个字母的句子:

  1. 鸿蒙官方战略合作共建——HarmonyOS技术社区

  2. C在4, 7句

  3. N在4,6,7句

  4. M在2, 4,5,7句

所以,{4, 7} 与 {4, 6, 7} 与 {4, 5, 7}做交集,得到{4, 7}说明cnm这个词很有可能是在第4句和第7句。

为什么说很可能呢?因为假如再添加一句话:今天我们学习三个单词:Cat, Network,  Morning。这一句也会被认为包含cnm这个词,但实际上它只是同时包含了C、N、M三个字母而已。

接下来,有人会问了:原来直接查询cnm的时候,只需要查询8次就可以了。现在你分别查询C N M要查询24次。你是修复了查询时间太短的bug吗?

回答这个问题之前,我们再来看另一个问题。

Python里面,当我要判断字母C是不是在句子我不想听到有人说cnm!里面时,Python是如何工作的?

实际上,它的工作原理可以写成:

sentence = '我不想听到有人说cnm!' for char in sentence:     if char == 'C':         print('C在这个字符串中')         break

如果要判断C、N、M是不是都在这个字符串我不想听到有人说cnm!中,同一个字符串会被遍历3次。有没有办法减少这种看起来多余的遍历操作呢?

如果我们把我不想听到有人说cnm!这个句子转成字典会怎么样:

sentence = '我不想听到有人说cnm!' sentence_dict = {char: 1 for char in sentence} for letter in 'cnm':     if letter in sentence_dict:         print(f'字母{letter}在句子中!')

这样一来,只需要在生成字典的时候遍历句子一次,减少了2次冗余遍历。并且,判断一个元素是否在字典里面,时间复杂度为O(1),速度非常快。

我不想听到有人说cnm!生成的字典为{'我': 1, '不': 1, '想': 1, '听': 1, '到': 1, '有': 1, '人': 1,  '说': 1, 'C': 1, 'N': 1, 'M': 1, '!':  1}。那么如果要把列表里面的所有句子都这样处理,又怎么存放呢?此时,字典的Key就是每一个字符,而Value可以是每一句话在原来列表中的索引:

sentences = ['你说我是买苹果电脑,还是买windows电脑呢?',               '人生苦短我用Python',               '你TM一天到晚只知道得瑟',              '不不不,我不是说你,我是说在座的各位都是垃圾。',              '我cnm你个大sb',              '各位同学,Good Morning!',              '网络这个单词,它的英文为Network',              '我不想听到有人说cnm!'] index_dict = {} for index, line in enumerate(sentences):     print(index, line)     for char in line:         if not char.strip():             continue         if char in index_dict:             index_dict[char].add(index)         else:             index_dict[char] = {index}

生成的字典为:

{'B': {4},  'C': {4, 7},  'G': {5},  'M': {2, 4, 5, 7},  'N': {4, 6, 7},  'P': {1},  'S': {4},  'T': {2},  'd': {0, 5},  'e': {6},  'g': {5},  'h': {1},  'i': {0, 5},  'k': {6},  'n': {0, 1, 5},  'o': {0, 1, 5, 6},  'r': {5, 6},  's': {0},  't': {1, 6},  'w': {0, 6},  'y': {1},  '。': {3},  '一': {2},  '不': {3, 7},  '个': {4, 6},  '为': {6},  '买': {0},  '人': {1, 7},  '位': {3, 5},  '你': {0, 2, 3, 4},  '到': {2, 7},  '单': {6},  '只': {2},  '各': {3, 5},  '同': {5},  '听': {7},  '呢': {0},  '在': {3},  '圾': {3},  '垃': {3},  '大': {4},  '天': {2},  '学': {5},  '它': {6},  '座': {3},  '得': {2},  '想': {7},  '我': {0, 1, 3, 4, 7},  '文': {6},  '是': {0, 3},  '晚': {2},  '有': {7},  '果': {0},  '瑟': {2},  '生': {1},  '用': {1},  '电': {0},  '的': {3, 6},  '知': {2},  '短': {1},  '络': {6},  '网': {6},  '脑': {0},  '苦': {1},  '英': {6},  '苹': {0},  '词': {6},  '说': {0, 3, 7},  '还': {0},  '这': {6},  '道': {2},  '都': {3},  '!': {5, 7},  ',': {0, 3, 5, 6},  '?': {0}}

生成的字典这么长,看起来非常可怕。但是别慌,毕竟不是你人肉寻找。对Python来说,字典里面无论有多少个Key,它的查询时间都是一样的。

现在,我们要寻找C、N、M,于是代码可以写为:

index_list = [] for letter in 'cnm':     index_list.append(index_dict.get(letter, {}))  common_index = set.intersection(*index_list)  # 对包含各个字母的索引做交集,得到同时包含3个字母的句子 print(f'这几个句子里面同时含有`C`、`N`、`M`:{common_index}') for index in common_index:     print(sentences[index])

运行结果如下:

怎么使用倒排索引极速提高字符串搜索效率

所以,对于一组需要被查询的关键字,也可以这样搜索:

keywords = ['垃圾', 'cnm', 'sb', 'TM'] for word in keywords:     index_list = []     for letter in word:         index_list.append(index_dict.get(letter, {}))      common_index = set.intersection(*index_list)     print(f'>>这几个句子里面同时含有:{word}')     for index in common_index:         print(sentences[index])

运行效果如下图所示:

怎么使用倒排索引极速提高字符串搜索效率


本文参考链接:https://www.yisu.com/zixun/459548.html
标签:java
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

关注我们

一个IT知识分享的公众号