怎么使用倒排索引極速提高字符串搜索效率

這篇文章主要講解了“怎么使用倒排索引極速提高字符串搜索效率”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“怎么使用倒排索引極速提高字符串搜索效率”吧！

在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！'             ]

如果使用常規方法，那么我們的做法是：

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. cnm在你說我是買蘋果電腦，還是買windows電腦呢?中嗎?不在!

3. cnm在人生苦短我用Python嗎?不在!

4. ……

5. ……

6. cnm在我cnm你個大sb嗎?在!

7. cnm在各位同學，Good Morning!嗎?不在!

8. CMN在網絡這個單詞，它的英文為Network嗎?不在!

9. cnm在我不想聽到有人說cnm!嗎?在!

于是就知道了，cnm在sentences列表下標為4和7的這兩個句子中。

下面，我們換一個看起來更笨的辦法：

要找到cnm在哪幾句里面，可以變成：尋找C、N、M這三個字母在哪幾句里面。然后，再找到同時有這三個字母的句子:

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. C在4, 7句

3. N在4，6，7句

4. 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])

運行效果如下圖所示：

感謝各位的閱讀，以上就是“怎么使用倒排索引極速提高字符串搜索效率”的內容了，經過本文的學習后，相信大家對怎么使用倒排索引極速提高字符串搜索效率這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！