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