什麼是Python中的簡單模糊字符串匹配算法？

我試圖找到一種很好的模糊字符串匹配算法。直接匹配不適用於我 - 這不太好，因爲除非我的字符串100％相似，否則匹配會失敗。對於字符串，Levenshtein方法工作得不好，因爲它在字符級別上工作。我正在尋找符合詞級匹配的東西，例如什麼是Python中的簡單模糊字符串匹配算法？

String A：快速的棕色狐狸。

字符串B：快速的棕色狐狸躍過了懶狗。

這些應該匹配在字符串中的所有單詞都串B.現在

，這是一個過於簡單的例子，但會有人知道一個良好的，模糊的字符串匹配算法，就一個字水平的作品。

來源

2010-05-27 Mridang Agarwalla

所以，你要知道，如果字符串A字符串B的近的子集？如果您交換字符串A和B，它*不匹配嗎？ – Dolph 2010-05-27 17:38:01

我喜歡Drew's answer。

您可以使用difflib找到最長匹配：

>>> a = 'The quick brown fox.' 
>>> b = 'The quick brown fox jumped over the lazy dog.' 
>>> import difflib 
>>> s = difflib.SequenceMatcher(None, a, b) 
>>> s.find_longest_match(0,len(a),0,len(b)) 
Match(a=0, b=0, size=19) # returns NamedTuple (new in v2.6)

或者挑選一些最小匹配閾值。例如：

>>> difflib.SequenceMatcher(None, a, b).ratio() 
0.61538461538461542

來源

2010-05-27 17:50:42 bernie

我認爲difflib更接近OP想要的東西。他說'模糊'，所以我認爲他的例子只是一個特別簡單的例子。 – 2010-05-27 18:01:38

'比例（）'也適用於序列項目（=字符）級別，所以您的答案需要更多的工作。 :) – badp 2010-05-27 18:02:36

@bp：謝謝。我又增加了一個更適合這個問題的例子。 – bernie 2010-05-27 18:03:26

如果你想要做的是測試所有的字符串的話是否一致另一個字符串，這是一個內襯：

if not [word for word in b.split(' ') if word not in a.split(' ')]: 
    print 'Match!'

如果你想得分它們而不是二進制測試，爲什麼不只是這樣做：

（匹配單詞（＃）/（在更大的串詞＃））* （（在較小的串詞）的＃/（在更大的串詞＃））

？

如果你願意，你可以更有愛心，並做每個字符串模糊匹配。

來源

2010-05-27 17:46:15

您可以修改Levenshtein算法來比較單詞而不是字符。這不是一個非常複雜的算法，並且可以在線使用多種語言。

Levenshtein通過比較兩個字符數組來工作。沒有理由相同的邏輯不能應用於兩個字符串數組。

來源

2010-05-27 18:02:39

我之前用C＃做過這個，我以前的問題是here。有興趣的初學者算法，你可以很容易地將其轉換爲Python。

想法，你應該用寫你自己的的算法是這樣的：

與原來的「標題」列表（要匹配文字/句子）。

每個標題項目在單詞/句子上應該具有最小的匹配分數，並忽略標題以及標題。

您還應該擁有全局最小匹配的最終結果百分比。

你應該計算每個單詞Levenshtein距離。

您應該增加總重量匹配的話，如果在同一順序去（敏捷的棕色VS敏捷的棕色，應該有明確更高的權重比棕色快與棕色快。）

來源

2010-05-27 18:07:31

取看看這個python庫，SeatGeek昨天開放源代碼。顯然，這些問題中的大多數都與情境有關，但它可能會對你有所幫助。

from fuzzywuzzy import fuzz 

s1 = "the quick brown fox" 
s2 = "the quick brown fox jumped over the lazy dog" 
s3 = "the fast fox jumped over the hard-working dog" 

fuzz.partial_ratio(s1, s2) 
> 100 

fuzz.token_set_ratio(s2, s3) 
> 73

SeatGeek website

and Github repo

來源

2011-07-09 19:28:58 acslater00

您可以從https://github.com/frazenshtein/fastcd/blob/master/search.py嘗試FuzzySearchEngine。

此模糊搜索僅支持搜索單詞，並且對於單詞有一個固定的允許誤差（只有一個替換或兩個相鄰字符的換位）。

但是，例如你可以嘗試這樣的：

import search 

string = "Chapter I. The quick brown fox jumped over the lazy dog." 
substr = "the qiuck broqn fox." 

def fuzzy_search_for_sentences(substr, string): 
    start = None 
    pos = 0 
    for word in substr.split(" "): 
     if not word: 
      continue 
     match = search.FuzzySearchEngine(word).search(string, pos=pos) 
     if not match: 
      return None 
     if start is None: 
      start = match.start() 
     pos = match.end() 
    return start 

print(fuzzy_search_for_sentences(substr, string))

11將被打印

來源

2015-04-24 11:05:24

什麼是Python中的簡單模糊字符串匹配算法？

回答

相關問題