一、最长公共子序列
最长公共子序列（Longest Common Subsequence，LCS）是指两个或多个序列中共同出现的一段连续序列，它在多个序列中都保持相同的顺序和连续性。在计算机科学中，寻找最长公共子序列是一个经典问题，通常通过动态规划算法解决。
动态规划算法解决最长公共子序列问题的步骤如下：
初始化状态数组：创建一个二维数组dp，其大小为(m+1)×(n+1)，其中m和n分别是两个序列的长度。dp[i][j]表示序列1的前i个字符与序列2的前j个字符的最长公共子序列的长度。
填充状态数组：遍历两个序列，对于每一对字符，如果它们相同，则dp[i][j] = dp[i-1][j-1] + 1；如果不同，则dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
找到最长公共子序列：dp数组的最后一个元素dp[m][n]就是两个序列的最长公共子序列的长度。可以通过回溯的方式找到具体的子序列。
python代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
## 最长公共子序列计算最长公共子串-------------------
def LCS(str_a, str_b):
if len(str_a) == 0 or len(str_b) == 0:
return 0
dp = [0 for _ in range(len(str_b) + 1)]
for i in range(1, len(str_a) + 1):
left_up = 0
dp[0] = 0
for j in range(1, len(str_b) + 1):
left = dp[j-1]
up = dp[j]
if str_a[i-1] == str_b[j-1]:
dp[j] = left_up + 1
else:
dp[j] = max([left, up])
left_up = up
return dp[len(str_b)]
#转换最长公共子序列为0-1之间的数值，结果越接近1，相似度越大
def LCS_Score(str_a, str_b):
return np.round(LCS(str_a, str_b)*2/(len(str_a)+len(str_b)),2)
#LCS_Score(str_a, str_b)
## 对dataframe的2列按照最长公共子序列计算相似度
## df: 数据来源变量
## col_name1、col_name2：用于计算相似度的2个列名
## simarity_score_name： 返回的相似度结果的列名
## 返回数据框，则simarity_score_name是用该计算方法对2列文本相似度的计算结果
def df_simarity_lcs(df , col_name1 , col_name2 , simarity_score_name):
df[simarity_score_name] = list(map(lambda str_a, str_b:LCS_Score(str_a, str_b),df[col_name1],df[col_name2]))
return df
|
二、Jaccard相似度（Jaccard Similarity）
基于集合的交集与并集的比值来计算相似度。
适用于短文本或关键词列表的比较。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
## 采用集合的方法计算2个集合的相似度
def similarity(a, b):
try:
return len(a & b) / len(a | b)
except ZeroDivisionError:
return -1e-4
## 采用集合的方法计算一个数据框中2个列的文本相似度
## df: 数据来源变量
## col_name1、col_name2：用于计算相似度的2个列名
## simarity_score_name： 返回的相似度结果的列名
## 返回数据框，则simarity_score_name是用该计算方法对2列文本相似度的计算结果
#对dataframe的2列按照集合的方法计算相似度
def df_simarity_jh(df , col_name1 , col_name2 , simarity_score_name):
df[simarity_score_name] = list(map(lambda str_a, str_b:similarity(set(str_a), set(str_b)),df[col_name1],df[col_name2]))
return df
|
三、余弦相似度（Cosine Similarity）
通过计算两个文本向量在空间中的夹角余弦值来评估它们的相似度。
通常与词袋模型（BOW）或TF-IDF结合使用。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
## vec1, vec2:待计算的向量
## 返回2个向量的相似度
def cosine_simi(vec1, vec2):
from scipy import spatial
return 1 - spatial.distance.cosine(vec1, vec2)
## 对dataframe的2列按照最长公共子序列计算相似度
## df: 数据来源变量
## col_name1、col_name2：用于计算相似度的2个列名
## simarity_score_name： 返回的相似度结果的列名
## 返回数据框，则simarity_score_name是用该计算方法对2列文本相似度的计算结果
def df_simarity_cosine(df , col_name1 , col_name2 , simarity_score_name):
df[simarity_score_name] = list(map(lambda str_a, str_b:cosine_simi(str_a, str_b),df[col_name1],df[col_name2]))
return df
|
四、方法补充
除了上文的方法，小编还为大家整理了一些其他Python文件相似度计算的方法，希望对大家有所帮助
TF-IDF
TF-IDF是一种统计方法，用于评估单词在文档集中的重要性。它可以将文本表示为向量，进而计算余弦相似度。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
from sklearn.feature_extraction.text import TfidfVectorizer
def calculate_tfidf_cosine_similarity(text1, text2):
vectorizer = TfidfVectorizer()
corpus = [text1, text2]
vectors = vectorizer.fit_transform(corpus)
similarity = cosine_similarity(vectors)
return similarity[0][1]
text1 = "I love Python programming"
text2 = "Python programming is great"
tfidf_cosine_similarity = calculate_tfidf_cosine_similarity(text1, text2)
print(tfidf_cosine_similarity)
|
Word2Vec
Word2Vec是一种将单词表示为向量的模型，可以捕捉单词之间的语义关系。使用预训练的词向量模型，可以计算文本之间的相似度。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
import gensim.downloader as api
from gensim import matutils
import numpy as np
def calculate_word2vec_similarity(text1, text2):
model = api.load("word2vec-google-news-300")
tokens1 = text1.split()
tokens2 = text2.split()
vec1 = np.mean([model[token] for token in tokens1 if token in model], axis=0)
vec2 = np.mean([model[token] for token in tokens2 if token in model], axis=0)
return matutils.cosine(vec1, vec2)
text1 = "I love Python programming"
text2 = "Python programming is great"
word2vec_similarity = calculate_word2vec_similarity(text1, text2)
print(word2vec_similarity)
|
Doc2Vec
Doc2Vec是一种将文档表示为向量的模型，可以捕捉文档之间的语义关系。与Word2Vec类似，可以使用预训练的Doc2Vec模型计算文本之间的相似度。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
from gensim.models import Doc2Vec
from gensim.models.doc2vec import TaggedDocument
def calculate_doc2vec_similarity(text1, text2):
corpus = [TaggedDocument(text1.split(), ["text1"]), TaggedDocument(text2.split(), ["text2"])]
model = Doc2Vec(corpus, vector_size=100, window=5, min_count=1, workers=4)
vec1 = model.docvecs["text1"]
vec2 = model.docvecs["text2"]
return matutils.cosine(vec1, vec2)
text1 = "I love Python programming"
text2 = "Python programming is great"
doc2vec_similarity = calculate_doc2vec_similarity(text1, text2)
print(doc2vec_similarity)
|
这些方法可以根据具体需求进行选择和组合，为自然语言处理任务提供强大的文本相似度计算能力。在实际应用中，可能会遇到多种场景，例如推荐系统、自动问答和文本聚类等。在这些场景中，选择合适的文本相似度计算方法至关重要。
BERT
BERT（Bidirectional Encoder Representations from Transformers）是一种基于Transformer的预训练模型，用于捕捉上下文相关的单词表示。可以通过BERT模型将文本表示为向量，然后计算余弦相似度。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
from sentence_transformers import SentenceTransformer
def calculate_bert_similarity(text1, text2):
model = SentenceTransformer("bert-base-nli-mean-tokens")
embeddings = model.encode([text1, text2])
similarity = cosine_similarity(embeddings)
return similarity[0][1]
text1 = "I love Python programming"
text2 = "Python programming is great"
bert_similarity = calculate_bert_similarity(text1, text2)
print(bert_similarity)
|
|
