之前筆者寫過(guò)一篇文章關(guān)于如何做搜索，但那篇文章的角度是從文本相似度角度寫的。那種方式是目前發(fā)展的趨勢(shì)，但是真正的搜索特別是網(wǎng)頁(yè)搜索不可能在大范圍的文本之間兩兩算相似度的。那樣搜索引擎的效率會(huì)變得特別低下。本文將從字符串模糊匹配的角度介紹一下搜索引擎。

一般的搜索，要分為兩個(gè)步驟：搜索和排序。搜索的方法有很多，為了高效一般進(jìn)行字符串或關(guān)鍵詞匹配，而用戶提供的一些關(guān)鍵詞可能不是數(shù)據(jù)庫(kù)中保存的，例如使用倒排的方法很難找到Head節(jié)點(diǎn)，此處需要使用模糊匹配的方式。這里簡(jiǎn)單列舉一下Learning-to-Rank排序的方法：BM25算法、TF-IDF算相似度、SVD奇異值分解（主題模型）得到向量表示算相似度、再就是之前介紹的文本相似度計(jì)算的方法。如果是網(wǎng)頁(yè)的排序，可能會(huì)涉及到網(wǎng)址質(zhì)量好壞需要使用PageRank排序算法等。

本文主要從模糊匹配的角度，簡(jiǎn)單介紹下搜索。主要解決的問(wèn)題類似，“劉得華演過(guò)的電影”與“劉德華演過(guò)的電影”表示的是同一個(gè)意思。

1. 編輯距離

首先給大家介紹一下編輯距離，編輯距離就是用于衡量?jī)蓚€(gè)字符串之間的差異。具體描述為：string1通過(guò)多少次最少操作（增添字符、刪除字符、替換字符）得到string2，最少操作的次數(shù)就定義為編輯距離。例如句子劉得華演過(guò)的電影”與“劉德華演過(guò)的電影”只需要一次替換“得”為“德”，所以二者之間的距離為1。如果兩個(gè)字符串S1和S2，長(zhǎng)度分別為i,j。那么二者之間的距離D(i,j)可以表示為：

（1）min(i,j)==0，即S1,S2中存在空字符串

D(i,j)=max(i,j)

（2）min(i,j) != 0,

去掉S1或S2的最后一個(gè)字符進(jìn)行比較，分別得到距離

D(i,j-1), D(i-1,j),D(i-1,j-1)

由動(dòng)態(tài)規(guī)劃的思想可以得到：

D(i,j) = min{D(i,j-1), D(i-1,j),D(i-1,j-1)+sigma(i,j)} 其中sigma(i,j)取值為0或 1，1表示S1和S2最后一個(gè)字符不相同，0表示相同。具體實(shí)現(xiàn)如下：

intLevenshteinDistance(constchar*s,intlen_s,constchar*t,intlen_t){intcost;if(len_s==)returnlen_t;if(len_t==)returnlen_s;if(s[len_s-1]==t[len_t-1])cost=;elsecost=1;returnminimum(LevenshteinDistance(s,len_s-1,t,len_t)+1,LevenshteinDistance(s,len_s,t,len_t-1)+1,LevenshteinDistance(s,len_s-1,t,len_t-1)+cost);}

2. fuzzywuzzy

Python提供fuzzywuzzy模塊，不僅可用于計(jì)算兩個(gè)字符串之間的相似度，而且還提供排序接口能從大量候選集中找到最相似的句子。

（1）安裝

需要安裝python-Levenshtein庫(kù)用于計(jì)算上述講解的編輯距離。

pip install python-Levenshtein

pip install fuzzywuzzy

（2）接口說(shuō)明

兩個(gè)模塊：fuzz, process，fuzz主要用于兩字符串之間匹配，process主要用于搜索排序。

fuzz.ratio(s1,s2)直接計(jì)算s2和s2之間的相似度，返回值為0-100，100表示完全相同；

fuzz.partial_ratio(S1,S2)部分匹配，如果S1是S2的子串依然返回100；

fuzz.token_sort_ratio(S1,S2)只比較S1，S2單詞是否相同，不考慮詞語(yǔ)之間的順序；

fuzz.token_set_ratio(S1，S2)相比f(wàn)uzz.token_sort_ratio不考慮詞語(yǔ)出現(xiàn)的次數(shù)；

process.extract(S1, ListS,limit=n)，表示從列表ListS中找出Top n與S1最相似的句子;

process.extractOne(S1,ListS)，返回最相似的一個(gè)

（3）使用

運(yùn)行結(jié)果：

說(shuō)明str1和str2之間相似度是對(duì)稱的。

總結(jié)

以上是生活随笔為你收集整理的python模糊查询_python实现字符串模糊匹配的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。