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

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

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

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

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

运行效果如下图所示：

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

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

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

如果使用常规方法，那么我们的做法是：

  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. 
  
  
  
  
  2. for char in sentence:
    3. 
  
  
  
  
  3.     if char == 'C':
    4. 
  
  
  
  
  4.         print('C在这个字符串中')
    5. 
  
  
  
  
  5.         break
    6.

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

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

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

这样一来，只需要在生成字典的时候遍历句子一次，减少了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. 
  
  
  
  
  2.              '人生苦短我用Python', 
    3. 
  
  
  
  
  3.              '你TM一天到晚只知道得瑟',
    4. 
  
  
  
  
  4.              '不不不，我不是说你，我是说在座的各位都是垃圾。',
    5. 
  
  
  
  
  5.              '我cnm你个大sb',
    6. 
  
  
  
  
  6.              '各位同学，Good Morning！',
    7. 
  
  
  
  
  7.              '网络这个单词，它的英文为Network',
    8. 
  
  
  
  
  8.              '我不想听到有人说cnm！']
    9. 
  
  
  
  
  9. index_dict = {}
    10. 
  
  
  
  
  10. for index, line in enumerate(sentences):
    11. 
  
  
  
  
  11.     print(index, line)
    12. 
  
  
  
  
  12.     for char in line:
    13. 
  
  
  
  
  13.         if not char.strip():
    14. 
  
  
  
  
  14.             continue
    15. 
  
  
  
  
  15.         if char in index_dict:
    16. 
  
  
  
  
  16.             index_dict[char].add(index)
    17. 
  
  
  
  
  17.         else:
    18. 
  
  
  
  
  18.             index_dict[char] = {index}
    19.

生成的字典为：

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

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

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

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

运行结果如下：

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

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

运行效果如下图所示：

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

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

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

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

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

当前题目：使用倒排索引极速提高字符串搜索效率
本文URL：http://www.csdahua.cn/qtweb/news16/311766.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

ChatGPT知识

各行业网站

重庆移动机房托管　　 　移动机房服务器托管　　 　雅安主机托管　　 　艾名斯智能　　 　高端网站定制　　 　成都网站安全运维　　 　app开发　　 　网站制作　　 　成都申请ssl证书　　 　app制作　　 　成都展柜定制　　 　雪茄烟品牌　　 　成都网站设计　　 　成都钢筋机械设备　　 　微信网站开发　　 　橡塑保温材料　　 　传美奇电气　　 　成都网站制作公司　　 　工程造价　　 　绵阳电信机房