使用倒排索引极速提高字符串搜索效率
在Python中,如果要判断一个字符串是否在另一个字符串里面,我们可以使用in
关键字,例如:
1 | >>> a = '你说我是买苹果电脑,还是买windows电脑呢?' |
如果有多个句子和多个关键字,那么可以使用for
循环来实现:
1 | sentences = ['你说我是买苹果电脑,还是买windows电脑呢?', |
运行效果如下图所示:
现在如果有100000000个句子,有1000个关键字,那么你需要对比1000亿次才能全部查询完成。这个时间代价太大了,如果Python一秒钟能运行500万次查询(实际上没有这么快),那么1000亿次查询需要20000秒,接近6小时。而且,由于in
关键字的时间复杂度为O(n)
,如果有大量长句子,查询时间会更长。