在Python中，如果我们要判断一个字符串是否在另一个字符串中，可以使用in关键字，例如：>>>a='YousaidI我应该买苹果电脑还是Windows电脑？'>>>if'apple'ina:...print('Apple这个词在一个字符串中')...如果Apple这个词在一个字符串中，如果有多个句子和关键字，那么就可以使用一个for循环实现：sentences=['你觉得我应该买苹果电脑还是Windows电脑？','人生苦短，我用Python','你成天只会操蛋','不不不，我不是说你，我是说在座的各位都是垃圾。''我cnm你个大sb']keywords=['garbage','cnm','sb','TM']forsentenceinsentences:forkeywordinkeywords:ifkeywordinsentence:print(f'sentence:【{sentence}】包含脏话：【{keyword}]')如下图所示：如果有100,000,000个句子和1,000个关键字，则需要比较1000亿次才能完成所有查询。这个时间成本太高了。如果Python每秒可以运行500万次查询（实际上并没有那么快），那么1000亿次查询将需要20,000秒，接近6小时。而且，由于in关键字的时间复杂度是O(n)，如果有大量的长句，查询时间会更长。比如我们要从下面的句子中找出cnm。sentences=['你觉得我应该买苹果电脑还是Windows电脑？','人生苦短，我用Python','你成天只会操蛋','不不不，我不是说你，我是说在座的各位都是垃圾。','我cnm你个大sb','大家早上好！','网络这个词，它的英文是Network','我不想听到有人说cnm！']如果我们用常规的方法，那么我们的方法就是：cnm你是说我应该买苹果电脑还是Windows电脑？是在吗？不在！生活中的cnm太短，我无法使用Python？不在！…………我的cnm里有cnm吗，你是大sb吗？是的！cnm在，大家早上好！？不在！CMN在network这个词里，英文是Network吗？不在！我不想听到有人在cnm中说cnm！？在！所以我们知道cnm在句子列表下标记为4和7的两个句子中。接下来，我们换一种更笨的方式：找出cnm在哪些句子中，可以改为：找出C、N、M在哪些句子中。然后，同时找出这三个字母的句子：C在4,7句中N在4,6,7句中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次就可以了。现在你分别查询CNM查询24次。修复查询时间过短的bug了吗？在回答这个问题之前，我们先来看另一个问题。在Python中，当我想判断Idon’twanttohearsomeonesaycnm!这句话中是否有字母C时，Python是如何工作的呢？其实它的工作原理可以写成：sentence='Idon'twanttohearsomeonesaycnm!'forcharinsentence:ifchar=='C':print('C在这个字符串中')break如果要判断C、N、M是否都在这个字符串中，我不想听别人这么说在cnm!中，同一个字符字符串会被遍历3次。有没有什么办法可以减少这种看似多余的遍历操作呢？如果我们转换句子Idon'twanttohearsomeonesaycnm怎么办！入字典：sentence='我不想听到有人说cnm！'sentence_dict={char:1forcharinsentence}forletterin'cnm':ifletterinsentence_dict:print(f'letter{letter}在句子中！')这样生成字典时只需要遍历句子一次，减少2冗余遍历。而且判断一个元素是否在字典中，时间复杂度为O(1)，非常快。我不想听到有人说cnm！结果字典是{'I':1,'Not':1,'Want':1,'Listen':1,'To':1,'Have':1,'person':1,'say':1,'C':1,'N':1,'M':1,'!':1}。那么如果要这样处理列表中所有的句子，怎么存储呢？这时候字典的Key就是每一个字符，Value可以是每一个句子在原列表中的索引：sentences=['你说我应该买苹果电脑还是Windows电脑？','人生苦短，我用Python','你成天只会操蛋','不不不，我不是说你，我是说在座的各位都是垃圾。','我cnm你个大sb','大家早上好！','网络这个词，它的英文是Network','我不想听到有人说cnm！']index_dict={}forindex,lineinenumerate(sentences):print(index,line)forcharinline:ifnotchar.strip():continueifcharinindex_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},'one':{2},'not':{3,7},'one':{4,6},'for':{6},'buy':{0},'person':{1,7},'bit':{3,5},'you':{0,2,3,4},'to':{2,7},'single':{6},'only':{2},'each':{3,5},'same':{5},'listen':{7},'what':{0},'in':{3},'garbage':{3},'garbage':{3},'big':{4},'day':{2},'learn':{5},'it':{6},'座':{3},'得':{2},'思':{7},'我':{0,1,3,4,7},'文':{6},'是':{0,3},'late':{2},'yes':{7},'fruit':{0},'se':{2},'birth':{1},'used':{1},'电':{0},'化':{3,6},'知识':{2},'短':{1},'网络':{6},'网':{6},'Brain':{0},'Bitter':{1},'English':{6},'Ping':{0},'Words':{6},'Say':{0,3,7},'also':{0},'this':{6},'Tao':{2},'all':{3},'!':{5,7},',':{0,3,5,6},'?':{0}}生成的字典太长了，看起来很糟糕。不过别慌，毕竟不是你找人肉。对于Python来说，无论字典中有多少个key，它的查询时间都是一样的。现在，我们要找到C、N、M，所以代码可以写成：index_list=[]forletterin'cnm':index_list.append(index_dict.get(letter,{}))common_index=set.intersection(*index_list)#将包含每个字母的索引相交得到同时包含3个字母的句子print(f'这些句子同时包含`C`,`N`,`M`:{common_index}')forindexincommon_index:print(sentences[index])结果如下：所以对于需要查询的一组关键词，也可以这样搜索：keywords=['garbage','cnm','sb','TM']forwordinkeywords:index_list=[]forletterinword:index_list.append(index_dict.get(letter,{}))common_index=set.intersection(*index_list)print(f'>>这些句子还包含：{word}')forindexincommon_index:print(sentences[index])如下图所示：看完本文，你已经学会了倒排索引（Inverted-index）。这是谷歌搜索的核心算法之一。可以看出，对于少量数据的查找，倒排索引与常规方法相比并没有节省多少时间。但是当你有100,000,000个句子和1,000个关键字时，使用倒排索引实现搜索只需要常规方法的1/10甚至更??少的时间。最后回到前面的问题，当一个句子中同时包含字母C、N、M时，即使这三个字母没有组合起来，也会进行查找。这就涉及到搜索引擎的另一项核心技术——分词。对于英语，用空格来分割单词就可以了。但是对于中文来说，不同的汉字组合成的字数是不一样的。甚至有的专有名词可能有七八个字长，但要整体查找。具体分词方法另当别论。本文转载自微信公众号“闻所未闻的密码”，可通过以下二维码关注。转载本文请联系Code公众号。
