python字典实现关键字检索_如何实现搜索框的关键词提示功能
我們都使用過主流的搜索引擎，谷歌、 bing，當然還有搜狗、百度之類。當你搜索某一關鍵詞時，它會貼心在下拉框補全一些熱門關鍵詞，像下圖這樣：
搜索關鍵詞提示
你點擊某一關鍵詞，頁面就直接跳轉到結果頁面，這種顯示搜索關鍵詞提示功能，一定程度上節省用戶的搜索時間。
能節省時間的東西就有價值，值得我們學習和使用。
但是，在公司內部的很多系統中，搜索框中都沒有這個功能。如果你能實現這個功能，那么你的用戶在使用時肯定會眼前一亮，頓生好感，領導看到后也會給你點贊。
這個功能實現非常簡單，前端每輸入一個字符，都去后端查詢前輟相同的關鍵詞返回到下拉列表中即可。前端的實現網上一搜一大堆，比如搜索關鍵字「搜索框自動補全」就有很多結果，這里就不說了。這里主要說下后端如何實現。
如果關鍵詞數量并不大，我們可以使用最簡單的字符串匹配算法，如 BF 算法，就是遍歷所有關鍵詞，找出前輟和輸入的字符串匹配的并返回給前端即可，Python 語言還提供了字符串的 startswith 這種方法，實現起來就更簡單了，簡單就意味著不容易出錯，沒有 bug，在關鍵詞少的情況下，可以優先選擇這種方法。
如果關鍵詞量較大，就需要考慮性能問題了，前輟樹( Trie 樹)就是高效解決這種問題的數據結構。先看一下前輟樹的圖：
trie樹
這棵前輟樹根節點不存放數據，其他節點保存了 hello,her,hi,how,see,so 等關鍵詞信息，如果查 he 前輟的單詞可以很快返回 hello,her。
這種樹的子節點數據并不固定，一般的算法教程在實現時都通過固定每個節點的指針數量來降低實現難度，比如使用一個下標與字符一一映射的數組灰存儲子節點的指針，如下圖所示：
一種實現方式
這種結構效率非常高，但是比較浪費空間，如果關鍵詞有中文或者標點，更是無法復用。
好在 Python 語言有字典這種高效的數據結構，實現起來易如反掌：鍵可以作為父節點，值作為子節點，值又是一個字典，包含所有的子節點信息，這種字典里又有字典這種嵌套的方式實現的前輟樹也叫字典樹。先直觀的感受下：
{'中': {-1: True, '國': {-1: True, '人': {-1: True}}, '華': {'人': {'民': {'共': {'和': {'國': {-1: True}}}}}}}}
這里 -1 是 True 表示到這里已經是一個完整的候選詞了，上述字典樹代表以下關鍵詞：
中
中國
中國人
中華人民共和國
Trie 樹的 Python 實現：
前輟樹(Trie 樹)主要有三個操作，第一個是就是一個將關鍵詞插入到 Trie 樹，第二個是在 Trie 樹中查詢一個關鍵詞，第三個是返回 Trie 樹中給定前輟的所有關鍵詞。實現起來并不難，下面是我的一種實現方法：
# encoding = utf-8
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
self.end = -1
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
curNode = self.root
for c in word:
if not c in curNode:
curNode[c] = {}
curNode = curNode[c]
curNode[self.end] = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
curNode = self.root
for c in word:
if not c in curNode:
return False
curNode = curNode[c]
# Doesn't end here
if not self.end in curNode:
return False
return True
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
curNode = self.root
for c in prefix:
if not c in curNode:
return False
curNode = curNode[c]
return True
def get_start(self,prefix):
'''
給出一個前輟，打印出所有匹配的字符串
:param prefix:
:return:
'''
def get_key(pre,pre_node):
result = []
if pre_node.get(self.end):
result.append(pre)
for key in pre_node.keys():
if key != self.end:
result.extend(get_key(pre+key,pre_node.get(key)))
return result
if not self.startsWith(prefix):
return []
else:
node = self.root
for p in prefix:
node = node.get(p)
else:
return get_key(prefix,node)
if __name__ == "__main__":
trie = Trie()
trie.insert("Python")
trie.insert("Python 算法")
trie.insert("Python web")
trie.insert("Python web 開發")
trie.insert("Python web 開發 視頻教程")
trie.insert("Python 算法 源碼")
trie.insert("Perl 算法 源碼")
print(trie.search("Perl"))
print(trie.search("Perl 算法 源碼"))
print((trie.get_start('P')))
print((trie.get_start('Python web')))
print((trie.get_start('Python 算')))
print((trie.get_start('P')))
print((trie.get_start('Python web')))
print((trie.get_start('Python 算')))
代碼運行結果如下：
False
True
['Python', 'Python 算法', 'Python 算法 源碼', 'Python web', 'Python web 開發', 'Python web 開發 視頻教程', 'Perl 算法 源碼']
['Python web', 'Python web 開發', 'Python web 開發 視頻教程']
['Python 算法', 'Python 算法 源碼']
Trie 的時間復雜度
如果要在一組關鍵詞中，頻繁地查詢某些關鍵詞，用 Trie 樹會非常高效。構建 Trie 樹的過程，需要掃描所有的關鍵詞，時間復雜度是 O(n)(n 表示所有關鍵詞的長度和)。但是一旦構建成功之后，后續的查詢操作會非常高效。
每次查詢時，如果要查詢的關鍵詞長度是 k，那我們只需要最多比對 k 個節點，就能完成查詢操作。跟原本那組關鍵詞的長度和個數沒有任何關系。所以說，構建好 Trie 樹后，在其中查找關鍵詞的時間復雜度是 O(k)，k 表示要查找的關鍵詞的長度。
不想造輪子，學習下 marisa-trie
自己造輪子還要思考，編碼，驗證，但這是學習提升的最佳方式。如果急于應用沒有時間造輪子，至少要學會如何使用輪子，下面的前輟樹的輪子是一個日本人寫的，大家可以學習應用下。
寫在最后
上述只實現了搜索框智能提示的一小步，實際使用中，你可能還會遇到以下問題：
1、如果候選詞過多，應該如何選擇性的顯示哪些關鍵詞呢？
2、如果用戶輸入錯誤，如何仍按正確的拼寫來顯示候選關鍵詞呢？
第一個問題比如好解決，我們可以按搜索的頻度或關鍵詞的搜索結果數來為每個關鍵詞自動生成一個權重數，按權重從大到小選擇性的顯示前 n 條即可。
第二個問題涉及動態規劃，大家可以先思考，如果有時間，會再寫一篇文章。
其實 Trie 樹在自動補全的需求上都可以大顯身手，如輸入法自動補全功能、IDE 代碼編輯器自動補全功能、瀏覽器網址輸入的自動補全功能等。
(完)
歡迎訂閱微信公眾號 somenzz，和你一起學習 Python。
總結
以上是生活随笔為你收集整理的python字典实现关键字检索_如何实现搜索框的关键词提示功能的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 12306订票候补是个坑_加30元就能抢
- 下一篇： 拼接图像亮度均匀调整_液晶拼接屏如何才能