忘了redis從哪個(gè)版本開啟,能夠根據(jù)輸入的部分命令前綴給出提示,即自動(dòng)補(bǔ)全。接下來(lái)筆者介紹基于redis實(shí)現(xiàn)這個(gè)很酷的功能。
成都創(chuàng)新互聯(lián)公司是一家專業(yè)提供阜康企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站制作、做網(wǎng)站、html5、小程序制作等業(yè)務(wù)。10年已為阜康眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進(jìn)行中。
about sorted set
假設(shè)結(jié)果中有mara,marabel,marcela。現(xiàn)在我們輸入mar,就能得到這三個(gè)名字,并且輸出結(jié)果按照字典排序。在實(shí)現(xiàn)這個(gè)需求之間,我們先簡(jiǎn)單介紹sorted set。
大家都知道sorted set是按照score排序的:
127.0.0.1:6380> zadd test 85 sida 127.0.0.1:6380> zadd test 80 xiaolang 127.0.0.1:6380> zadd test 60 afei 127.0.0.1:6380> zadd test 90 chenssy 127.0.0.1:6380> zadd test 98 yunaiv 127.0.0.1:6380> zrange test 0 -1 1) "afei" 2) "xiaolang" 3) "sida" 4) "chenssy" 5) "yunaiv"
但是如果score都一樣,sorted set是按照什么排序的呢?是按照字典排序的:
127.0.0.1:6380> zadd exam 0 sida 127.0.0.1:6380> zadd exam 0 xiaolang 127.0.0.1:6380> zadd exam 0 chenssy 127.0.0.1:6380> zadd exam 0 yunaiv 127.0.0.1:6380> zadd exam 0 afei 127.0.0.1:6380> zrange exam 0 -1 1) "afei" 2) "chenssy" 3) "sida" 4) "xiaolang" 5) "yunaiv"
這是sorted set一個(gè)非常重要的特性,也是我們自動(dòng)補(bǔ)全需求的一個(gè)要點(diǎn)。但是這還不夠,離我們的最終需求還有一段路要走。幸運(yùn)的是sorted set還有另一個(gè)很酷的命令:ZRANK。這個(gè)命令能知道你要查詢的key在sorted set中的位置:
127.0.0.1:6380> zrank exam sida (integer) 2 127.0.0.1:6380> zrank exam yunaiv (integer) 4 127.0.0.1:6380> zrange exam 2 4 1) "sida" 2) "xiaolang" 3) "yunaiv"
到這里感覺離我們實(shí)現(xiàn)自動(dòng)補(bǔ)全的第一個(gè)版本非常接近了,我們能得到sorted set中按照字典排序后任意一個(gè)member及其后面N個(gè)member。
簡(jiǎn)單實(shí)現(xiàn)
為了實(shí)現(xiàn)最終的自動(dòng)補(bǔ)全,我們需要付出一些代價(jià):空間。
意思是,對(duì)于某個(gè)準(zhǔn)備添加到sorted set中的member,例如afei,我們不僅要把完整的詞(afei)添加到sorted set中,而且還要添加所有可能的前綴(a, af, afe, afei)。這里為了解決某個(gè)詞是真正的member還是某個(gè)member的前綴(例如bar既是一個(gè)完整的詞,也是某個(gè)member例如bark的可能前綴),我們加了一個(gè)小把戲,即在真正member的后面增加一個(gè)特殊字符,例如"$",那么afei這個(gè)member就會(huì)添加下列這些詞:
a, af, afe, afei, afei$
現(xiàn)在假設(shè)我們需要添加三個(gè)詞:foo, bar, foobar 來(lái)進(jìn)行一些測(cè)試, 那么sorted set中就會(huì)有如下這些詞:
127.0.0.1:6380> zrange autoc 0 -1 1) "b" 2) "ba" 3) "bar" 4) "bar$" 5) "f" 6) "fo" 7) "foo" 8) "foo$" 9) "foob" 10) "fooba" 11) "foobar" 12) "foobar$"
離我們最終的目標(biāo)又要近了很多。現(xiàn)在假設(shè)用戶輸入"fo",那么為了實(shí)現(xiàn)自動(dòng)補(bǔ)全,我們需要執(zhí)行如下命令,仔細(xì)查看結(jié)果,foo$和foobar$就是我們需要的結(jié)果,只需要將特殊后綴$去掉即可(其他沒有以$結(jié)尾的詞全部忽略):
127.0.0.1:6380> zrank autoc fo (integer) 5 127.0.0.1:6380> zrange autoc 5 -1 1) "fo" 2) "foo" 3) "foo$" 4) "foob" 5) "fooba" 6) "foobar" 7) "foobar$"
更多詞的測(cè)試
網(wǎng)址http://antirez.com/misc/female-names.txt 提供了近5000個(gè)女性名字。按照前面說(shuō)的規(guī)則,將所有名字的所有可能前綴全部添加到sorted set中。假定用戶輸入member,那么只需要通過(guò)如下兩個(gè)命令,得到字典排序后用戶輸入的member后面的50個(gè)詞,然后只取$結(jié)尾的詞:
127.0.0.1:6380> zrank autoc member (integer) 8 127.0.0.1:6380> zrange autoc 8 50
時(shí)間&空間復(fù)雜度
根據(jù)官方文檔可知,zrank和zrange的事件復(fù)雜度都是O(log(N))。因此,即使數(shù)據(jù)量比較大,這種方案也是可行的。
ZRANK key member
起始版本:2.0.0
時(shí)間復(fù)雜度:O(log(N))ZRANGE key start stop [WITHSCORES]
起始版本:1.2.0
時(shí)間復(fù)雜度:O(log(N)+M) with N being the number of elements in the sorted set and M the number of elements returned.
那么需要多少內(nèi)存呢?
假設(shè)在最糟糕的情況下,一個(gè)長(zhǎng)度為M的詞需要添加M+1個(gè)詞到sorted set中。那么如果有N個(gè)詞,總計(jì)需要添加N*(Ma+1)個(gè)詞到sorted set中,Ma是這N個(gè)詞的平均長(zhǎng)度。
幸運(yùn)的是,實(shí)際情況遠(yuǎn)比這個(gè)要好得多,以近5000個(gè)女性名字為例,只需要添加大約15000個(gè)詞到sorted set中,因?yàn)檫@些名詞存在大量重復(fù)的前綴。以3個(gè)名字為例:marci,marcia,marcile。如果按照最糟糕的情況,需要添加3*(6+1)=21個(gè)詞到sorted set中,然而實(shí)際情況呢,只需要添加11個(gè)詞到sorted set中即可:
m, ma , mar, marc, marci, marci$, marcia, marcia$, marcil, marcile, marcile$。
而且,隨著樣本越來(lái)越大,重復(fù)的前綴會(huì)越大越多。
所以,需要的內(nèi)存也還OK。是不是覺得美滋滋?哈
查詢預(yù)測(cè)
我們這次的自動(dòng)補(bǔ)全是按照字典排序,很多時(shí)候,這是我們需要的。但是也有一些情況,我們希望按照相似度來(lái)排序。例如google搜索那樣,搜索結(jié)果按照頻率和熱度等維度進(jìn)行排序。例如,當(dāng)用戶輸入ne,用戶應(yīng)該希望看到Netflix,news,new york times等這些熱門關(guān)鍵詞。
這樣做起來(lái)就不那么容易了,如果要能達(dá)到根據(jù)頻率排序,我們需要一個(gè)特別的sorted set能以非阻塞的方式實(shí)時(shí)更新每個(gè)前綴的頻率:
當(dāng)用戶輸入一個(gè)例如"foo"這種查詢,由于它的所有前綴為:"f", "fo", "foo"。那么對(duì)每個(gè)前綴都執(zhí)行命令:ZINCRBY <prefix> 1 foo ;如果用戶輸入"foobar",那么對(duì)每個(gè)前綴都執(zhí)行:ZINCRBY <prefix> 1 foobar;
這種方法還有一個(gè)問題,許多自動(dòng)補(bǔ)全系統(tǒng)只需要展示TOP N個(gè)關(guān)鍵詞,假設(shè)N為10。但是我們這種方法,如果要計(jì)算TOP 10,我們需要取得關(guān)鍵詞遠(yuǎn)不止10個(gè),理論上我們要這個(gè)前綴作為key的sorted set中所有member都取出來(lái)。
幸運(yùn)的是,從統(tǒng)計(jì)學(xué)上來(lái)講,每個(gè)對(duì)于sorted set中有300個(gè)member的前綴,就能得到TOP 5關(guān)鍵詞。如果查詢?cè)筋l繁,它的得分越高,它最終被選中的概率也就越高。因此,我們要做的就是對(duì)搜索字符串的每個(gè)前綴:
這個(gè)方法一下子可能理解不過(guò)來(lái),沒關(guān)系,舉個(gè)栗子。假設(shè)現(xiàn)在用戶輸入了next,其前綴n為key的sorted set中已經(jīng)有netflix(100), news(120), new york(80), near(23), nequ(1)。由于這個(gè)前綴對(duì)應(yīng)的sorted set中的member數(shù)量還沒有300,所以,執(zhí)行:zincrby n 1 next。其中n是前綴,next是用戶輸入的關(guān)鍵詞。假設(shè)現(xiàn)在用戶輸入了next,其前綴n為key的sorted set中已經(jīng)有netflix(100), news(120), new york(80), near(23), 省略295個(gè)score大于1的關(guān)鍵詞, nequ(1)。由于這個(gè)前綴對(duì)應(yīng)的sorted set中的member數(shù)量達(dá)到了300,所以,先刪除得分比較低的nequ,再執(zhí)行:zincrby n 1 next。
這個(gè)方法跟用戶輸入關(guān)鍵詞分布有很大的關(guān)聯(lián)性,如果用戶輸入的所有關(guān)鍵詞頻率比較接近,那么這個(gè)方法得到的數(shù)據(jù)并不是很可靠。但是我們知道這不是問題,因?yàn)樗阉骶褪墙^大部分人在搜索那一小部分關(guān)鍵詞集合。
清理階段
由于上面提到的搜索長(zhǎng)尾效應(yīng),我們可以講那些得分為1的member清理掉,因?yàn)橛脩魧?duì)這些關(guān)鍵詞幾乎沒有任何關(guān)注度。清理操作還能夠減少使用內(nèi)存,從而讓redis保存更多更有用的數(shù)據(jù)。
知識(shí)總結(jié)
參考:http://oldblog.antirez.com/post/autocomplete-with-redis.html
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了,希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,謝謝大家對(duì)創(chuàng)新互聯(lián)的支持。
網(wǎng)站名稱:利用Redis如何實(shí)現(xiàn)自動(dòng)補(bǔ)全功能
本文鏈接:http://muchs.cn/article48/jogjep.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供網(wǎng)站收錄、自適應(yīng)網(wǎng)站、企業(yè)網(wǎng)站制作、用戶體驗(yàn)、手機(jī)網(wǎng)站建設(shè)、標(biāo)簽優(yōu)化
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)