文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-12-03 12:52

关注

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

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

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

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

运行效果如下图所示:

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

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

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

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

  1. cnm在你说我是买苹果电脑,还是买windows电脑呢?中吗?不在!
  2. cnm在人生苦短我用Python吗?不在!
  3. ……
  4. ……
  5. cnm在我cnm你个大sb吗?在!
  6. cnm在各位同学,Good Morning!吗?不在!
  7. CMN在网络这个单词,它的英文为Network吗?不在!
  8. cnm在我不想听到有人说cnm!吗?在!

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

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

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

  1. C在4, 7句
  2. N在4,6,7句
  3. 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是如何工作的?

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

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

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

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

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

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

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

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

生成的字典为:

  1. {'B': {4}, 
  2.  'C': {4, 7}, 
  3.  'G': {5}, 
  4.  'M': {2, 4, 5, 7}, 
  5.  'N': {4, 6, 7}, 
  6.  'P': {1}, 
  7.  'S': {4}, 
  8.  'T': {2}, 
  9.  'd': {0, 5}, 
  10.  'e': {6}, 
  11.  'g': {5}, 
  12.  'h': {1}, 
  13.  'i': {0, 5}, 
  14.  'k': {6}, 
  15.  'n': {0, 1, 5}, 
  16.  'o': {0, 1, 5, 6}, 
  17.  'r': {5, 6}, 
  18.  's': {0}, 
  19.  't': {1, 6}, 
  20.  'w': {0, 6}, 
  21.  'y': {1}, 
  22.  '。': {3}, 
  23.  '一': {2}, 
  24.  '不': {3, 7}, 
  25.  '个': {4, 6}, 
  26.  '为': {6}, 
  27.  '买': {0}, 
  28.  '人': {1, 7}, 
  29.  '位': {3, 5}, 
  30.  '你': {0, 2, 3, 4}, 
  31.  '到': {2, 7}, 
  32.  '单': {6}, 
  33.  '只': {2}, 
  34.  '各': {3, 5}, 
  35.  '同': {5}, 
  36.  '听': {7}, 
  37.  '呢': {0}, 
  38.  '在': {3}, 
  39.  '圾': {3}, 
  40.  '垃': {3}, 
  41.  '大': {4}, 
  42.  '天': {2}, 
  43.  '学': {5}, 
  44.  '它': {6}, 
  45.  '座': {3}, 
  46.  '得': {2}, 
  47.  '想': {7}, 
  48.  '我': {0, 1, 3, 4, 7}, 
  49.  '文': {6}, 
  50.  '是': {0, 3}, 
  51.  '晚': {2}, 
  52.  '有': {7}, 
  53.  '果': {0}, 
  54.  '瑟': {2}, 
  55.  '生': {1}, 
  56.  '用': {1}, 
  57.  '电': {0}, 
  58.  '的': {3, 6}, 
  59.  '知': {2}, 
  60.  '短': {1}, 
  61.  '络': {6}, 
  62.  '网': {6}, 
  63.  '脑': {0}, 
  64.  '苦': {1}, 
  65.  '英': {6}, 
  66.  '苹': {0}, 
  67.  '词': {6}, 
  68.  '说': {0, 3, 7}, 
  69.  '还': {0}, 
  70.  '这': {6}, 
  71.  '道': {2}, 
  72.  '都': {3}, 
  73.  '!': {5, 7}, 
  74.  ',': {0, 3, 5, 6}, 
  75.  '?': {0}} 

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

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

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

运行结果如下:

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

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

运行效果如下图所示:

看完这篇文章以后,你已经学会了倒排索引(Inverted-index)。这是Google搜索的核心算法之一。

可以看出,对于少量数据的搜索,倒排索引并不会比常规方法节约多少时间。但是当你有100000000条句子,1000个关键词的时候,用倒排索引实现搜索,所需要的时间只有常规方法的1/10甚至更少。

最后回到前面遇到的一个问题,当句子里面同时含有字母C、N、M,虽然这三个字母并不是组合在一起的,也会被搜索出来。这就涉及到搜索引擎的另一个核心技术——分词了。对于英文而言,使用空格来切分单词就好了。但是对于中文来说,不同的汉字组合在一起构成的词语,字数是不一样的。甚至有些专有名词,可能七八个字,但是也要作为整体来搜索。

分词的具体做法,又是另外一个故事了。

本文转载自微信公众号「未闻Code」,可以通过以下二维码关注。转载本文请联系未闻Code公众号。

 

来源:未闻Code内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯