使用倒排索引極速提高字符串搜索效率
在Python中，如果要判斷一個(gè)字符串是否在另一個(gè)字符串里面，我們可以使用in關(guān)鍵字，例如：
- >>> a = '你說(shuō)我是買蘋(píng)果電腦，還是買windows電腦呢？'
- >>> if '蘋(píng)果' in a:
- ... print('蘋(píng)果這個(gè)詞在a字符串里面')
- ...
- 蘋(píng)果這個(gè)詞在a字符串里面
如果有多個(gè)句子和多個(gè)關(guān)鍵字，那么可以使用for循環(huán)來(lái)實(shí)現(xiàn)：
- sentences = ['你說(shuō)我是買蘋(píng)果電腦，還是買windows電腦呢？',
- '人生苦短我用Python',
- '你TM一天到晚只知道得瑟',
- '不不不，我不是說(shuō)你，我是說(shuō)在座的各位都是垃圾。'
- '我cnm你個(gè)大sb'
- ]
- keywords = ['垃圾', 'cnm', 'sb', 'TM']
- for sentence in sentences:
- for keyword in keywords:
- if keyword in sentence:
- print(f'句子: 【{sentence}】包含臟話：【{keyword}】')
運(yùn)行效果如下圖所示：
現(xiàn)在如果有100000000個(gè)句子，有1000個(gè)關(guān)鍵字，那么你需要對(duì)比1000億次才能全部查詢完成。這個(gè)時(shí)間代價(jià)太大了，如果Python一秒鐘能運(yùn)行500萬(wàn)次查詢(實(shí)際上沒(méi)有這么快)，那么1000億次查詢需要20000秒，接近6小時(shí)。而且，由于in關(guān)鍵字的時(shí)間復(fù)雜度為O(n)，如果有大量長(zhǎng)句子，查詢時(shí)間會(huì)更長(zhǎng)。
例如，我們要從下面的句子里面尋找cnm。
- sentences = ['你說(shuō)我是買蘋(píng)果電腦，還是買windows電腦呢？',
- '人生苦短我用Python',
- '你TM一天到晚只知道得瑟',
- '不不不，我不是說(shuō)你，我是說(shuō)在座的各位都是垃圾。',
- '我cnm你個(gè)大sb',
- '各位同學(xué)，Good Morning！',
- '網(wǎng)絡(luò)這個(gè)單詞，它的英文為Network',
- '我不想聽(tīng)到有人說(shuō)cnm！'
- ]
如果使用常規(guī)方法，那么我們的做法是：
- cnm在你說(shuō)我是買蘋(píng)果電腦，還是買windows電腦呢?中嗎?不在!
- cnm在人生苦短我用Python嗎?不在!
- ……
- ……
- cnm在我cnm你個(gè)大sb嗎?在!
- cnm在各位同學(xué)，Good Morning!嗎?不在!
- CMN在網(wǎng)絡(luò)這個(gè)單詞，它的英文為Network嗎?不在!
- cnm在我不想聽(tīng)到有人說(shuō)cnm!嗎?在!
于是就知道了，cnm在sentences列表下標(biāo)為4和7的這兩個(gè)句子中。
下面，我們換一個(gè)看起來(lái)更笨的辦法：
要找到cnm在哪幾句里面，可以變成：尋找C、N、M這三個(gè)字母在哪幾句里面。然后，再找到同時(shí)有這三個(gè)字母的句子:
- C在4, 7句
- N在4，6，7句
- M在2, 4，5，7句
所以，{4, 7} 與 {4, 6, 7} 與 {4, 5, 7}做交集，得到{4, 7}說(shuō)明cnm這個(gè)詞很有可能是在第4句和第7句。
為什么說(shuō)很可能呢?因?yàn)榧偃缭偬砑右痪湓挘航裉煳覀儗W(xué)習(xí)三個(gè)單詞：Cat, Network, Morning。這一句也會(huì)被認(rèn)為包含cnm這個(gè)詞，但實(shí)際上它只是同時(shí)包含了C、N、M三個(gè)字母而已。
接下來(lái)，有人會(huì)問(wèn)了：原來(lái)直接查詢cnm的時(shí)候，只需要查詢8次就可以了?，F(xiàn)在你分別查詢C N M要查詢24次。你是修復(fù)了查詢時(shí)間太短的bug嗎?
回答這個(gè)問(wèn)題之前，我們?cè)賮?lái)看另一個(gè)問(wèn)題。
Python里面，當(dāng)我要判斷字母C是不是在句子我不想聽(tīng)到有人說(shuō)cnm!里面時(shí)，Python是如何工作的?
實(shí)際上，它的工作原理可以寫(xiě)成：
- sentence = '我不想聽(tīng)到有人說(shuō)cnm！'
- for char in sentence:
- if char == 'C':
- print('C在這個(gè)字符串中')
- break
如果要判斷C、N、M是不是都在這個(gè)字符串我不想聽(tīng)到有人說(shuō)cnm!中，同一個(gè)字符串會(huì)被遍歷3次。有沒(méi)有辦法減少這種看起來(lái)多余的遍歷操作呢?
如果我們把我不想聽(tīng)到有人說(shuō)cnm!這個(gè)句子轉(zhuǎn)成字典會(huì)怎么樣：
- sentence = '我不想聽(tīng)到有人說(shuō)cnm！'
- sentence_dict = {char: 1 for char in sentence}
- for letter in 'cnm':
- if letter in sentence_dict:
- print(f'字母{letter}在句子中！')
這樣一來(lái)，只需要在生成字典的時(shí)候遍歷句子一次，減少了2次冗余遍歷。并且，判斷一個(gè)元素是否在字典里面，時(shí)間復(fù)雜度為O(1)，速度非?？臁?/p>
我不想聽(tīng)到有人說(shuō)cnm!生成的字典為{'我': 1, '不': 1, '想': 1, '聽(tīng)': 1, '到': 1, '有': 1, '人': 1, '說(shuō)': 1, 'C': 1, 'N': 1, 'M': 1, '!': 1}。那么如果要把列表里面的所有句子都這樣處理，又怎么存放呢?此時(shí)，字典的Key就是每一個(gè)字符，而Value可以是每一句話在原來(lái)列表中的索引：
- sentences = ['你說(shuō)我是買蘋(píng)果電腦，還是買windows電腦呢？',
- '人生苦短我用Python',
- '你TM一天到晚只知道得瑟',
- '不不不，我不是說(shuō)你，我是說(shuō)在座的各位都是垃圾。',
- '我cnm你個(gè)大sb',
- '各位同學(xué)，Good Morning！',
- '網(wǎng)絡(luò)這個(gè)單詞，它的英文為Network',
- '我不想聽(tīng)到有人說(shuō)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},
- '個(gè)': {4, 6},
- '為': {6},
- '買': {0},
- '人': {1, 7},
- '位': {3, 5},
- '你': {0, 2, 3, 4},
- '到': {2, 7},
- '單': {6},
- '只': {2},
- '各': {3, 5},
- '同': {5},
- '聽(tīng)': {7},
- '呢': {0},
- '在': {3},
- '圾': {3},
- '垃': {3},
- '大': {4},
- '天': {2},
- '學(xué)': {5},
- '它': {6},
- '座': {3},
- '得': {2},
- '想': {7},
- '我': {0, 1, 3, 4, 7},
- '文': {6},
- '是': {0, 3},
- '晚': {2},
- '有': {7},
- '果': {0},
- '瑟': {2},
- '生': {1},
- '用': {1},
- '電': {0},
- '的': {3, 6},
- '知': {2},
- '短': {1},
- '絡(luò)': {6},
- '網(wǎng)': {6},
- '腦': {0},
- '苦': {1},
- '英': {6},
- '蘋(píng)': {0},
- '詞': {6},
- '說(shuō)': {0, 3, 7},
- '還': {0},
- '這': {6},
- '道': {2},
- '都': {3},
- '！': {5, 7},
- '，': {0, 3, 5, 6},
- '？': {0}}
生成的字典這么長(zhǎng)，看起來(lái)非?？膳?。但是別慌，畢竟不是你人肉尋找。對(duì)Python來(lái)說(shuō)，字典里面無(wú)論有多少個(gè)Key，它的查詢時(shí)間都是一樣的。
現(xiàn)在，我們要尋找C、N、M，于是代碼可以寫(xiě)為：
- index_list = []
- for letter in 'cnm':
- index_list.append(index_dict.get(letter, {}))
- common_index = set.intersection(*index_list) # 對(duì)包含各個(gè)字母的索引做交集，得到同時(shí)包含3個(gè)字母的句子
- print(f'這幾個(gè)句子里面同時(shí)含有`C`、`N`、`M`：{common_index}')
- for index in common_index:
- print(sentences[index])
運(yùn)行結(jié)果如下：
所以，對(duì)于一組需要被查詢的關(guān)鍵字，也可以這樣搜索：
- 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'>>這幾個(gè)句子里面同時(shí)含有：{word}')
- for index in common_index:
- print(sentences[index])
運(yùn)行效果如下圖所示：
看完這篇文章以后，你已經(jīng)學(xué)會(huì)了倒排索引(Inverted-index)。這是Google搜索的核心算法之一。
可以看出，對(duì)于少量數(shù)據(jù)的搜索，倒排索引并不會(huì)比常規(guī)方法節(jié)約多少時(shí)間。但是當(dāng)你有100000000條句子，1000個(gè)關(guān)鍵詞的時(shí)候，用倒排索引實(shí)現(xiàn)搜索，所需要的時(shí)間只有常規(guī)方法的1/10甚至更少。
最后回到前面遇到的一個(gè)問(wèn)題，當(dāng)句子里面同時(shí)含有字母C、N、M，雖然這三個(gè)字母并不是組合在一起的，也會(huì)被搜索出來(lái)。這就涉及到搜索引擎的另一個(gè)核心技術(shù)——分詞了。對(duì)于英文而言，使用空格來(lái)切分單詞就好了。但是對(duì)于中文來(lái)說(shuō)，不同的漢字組合在一起構(gòu)成的詞語(yǔ)，字?jǐn)?shù)是不一樣的。甚至有些專有名詞，可能七八個(gè)字，但是也要作為整體來(lái)搜索。
分詞的具體做法，又是另外一個(gè)故事了。
本文轉(zhuǎn)載自微信公眾號(hào)「未聞Code」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系未聞Code公眾號(hào)。
