Python中的序列數據類型包括字符串、列表、元組等,這些類型在處理數據時經常使用。其中,恰好也有一種序列數據類型--序列寒暑表(SequenceMatcher)。
序列寒暑表是Python中用于字符串匹配和比較的一種算法,可用于比較兩個字符串的相似度,比如代碼版本管理系統(tǒng)中代碼版本對比、網頁爬蟲中的網頁相似度研究等等。
序列寒暑表算法本質上是通過動態(tài)規(guī)劃的方式得出兩個字符串的相似度,采用最長公共子序列的思路來解決問題。
from difflib import SequenceMatcher s1 = 'python programming' s2 = 'programming python' matcher = SequenceMatcher(None, s1, s2) match = matcher.find_longest_match(0, len(s1), 0, len(s2)) print('兩個字符串的相似度為:', match.size / max(len(s1), len(s2)))
使用Python內置的difflib庫我們可以很簡單地使用SequenceMatcher算法。上述代碼展示了如何計算s1和s2的相似度。運行結果為:
兩個字符串的相似度為: 0.8181818181818182
序列寒暑表算法不僅可以計算相似度,還可以得到兩個字符串之間的差異。例如:
from difflib import Differ s1 = 'a beautiful girl' s2 = 'a pretty girl' differ = Differ() diff = differ.compare(s1.split(), s2.split()) print('\n'.join(diff))
代碼輸出結果為:
a - beautiful + pretty girl
通過上述輸出結果,即可輕松地知道s1和s2兩個字符串之間最大、最小的不同點是什么。