限 时 特 惠： 本站每日持续稳定更新内部创业教程，一年会员只需98元，全站资源免费下载 点击查看详情
站 长 微 信： muyang-0410
文本比对以及基于文本的高频短语、概念以及字符序列挖掘是自然语言处理中的典型场景，例如在热点挖掘、文本聚类场景中，我们可以事先将相同意思的文本标题聚在一起，得到聚类文本的统一表述，这也是情报分析中的常用技术手段。
本文围绕情报分析中的事件名称生成主题，从情报分析中的事件名称生成代表工作、最长公共子串( )、最长公共子序列( )的实现思路、代码实现进行实践，并进行最长子串和子序列在文本标题抽取的应用实验，供大家参考。
一、情报分析中的事件名称生成代表工作
事件聚类以及事件名称生成是个情报分析中的一个重要部分，如何得到一个好的流利、自然的情报标题，决定了情报的分发与传播。
1、具体场景
百度热搜通常是热门情报的入口，例如，左侧是不同媒体发布出来的报道，右侧是具体的百度热搜事件“普京称实现要求才可能停止军事行动“。
而通过这些标红的字体，我们可以很自然的想到，可以使用字符串的操作算法来逼近这个结果。
我们常常可以通过计算两个字符串之间的公共部分作为意义片段来呈现，例如下图展示了百度热搜中的一个典型例子。又如，在有query-title共点击的业务数据中，可以通过计算两者之间的公共部分来来挖掘用户的搜索意图。
2、代表工作
王伟玉等发表在ccir的文章《一种事件粒度的抽取式话题简短表示生成方法》就是巧妙使用最长公共子串进行事件话题表示生成的工作，很有意思，在这里做下介绍。
利用事件报道描述内容高度相似的特点，提出一种抽取式话题简短表示生成方法，把事件文档集中的标题作为处理对象，从不同的标题中抽取出保留原有语序的共性信息，并迚一步融合这些共性信息，生成事件粒度的话题简短表示。
具体的，在难点分析上，该工作认为：同一事件下的多篇文档是相关的，都在报道同一件事，但由于用语习惯、表 达方式等丌同，有不同的描述；如何从文档集丌同的描述中获得该事件的主要内容，并保证生成的话题简短 表示可读性好。
而在通过对同一事件的文档集研究发现，文档的标题具有很强的指向性：
标题概括了文档主要内容。事件的文档集主要内容一致，同一事件文档集的标题内容往往高度相似；在文档集的标题中重复出现的信息通常是该事件主要内容的反映；标题本身有好的可读性，其原有语序表达流畅。将标题中的部分信息按原序结合组织，会继承一定程度上好的可读性；
因此，该文章采用最长公共子序列的方法提取事件文档标题集的共性信息，这些共性信息能保留原有语序，满足关键信息的显著性和语言表达的流畅性。
在算法架构上，利用事件内容相似、重复度高的特征，基于抽取出的事件文档标题集中保留原有语序的共性信息生成事件的话题简短表示。
例如，上图中展示的算法主要包含3部分，数据的拆分、提取、融合，在第2步提取出的信息还存在噪音等问题，需要在融合阶段迚行筛选甚至压缩等处理。例如：
Step 1:对获得的该事件标题集的最长公共子序列集合进行空值过滤；
Step 2:统计该集合中各个非空最长公共子序列的出现次数，将它们按出现次数降序排列(若出现次数相等则比较这些最长公共子序列的长度，按长度降序排列)，选出排列在前 k 个的高频最长公共子序列；
Step 3:从前 k 个高频最长公共子序列中筛选出满足长度、出现次数、集合内剩余最长公共子序列是其 子序列个数条件要求的或经过上述筛选再经过删除停用词等无用信息压缩处理的最佳高频最长公共子序列作为该事件的话题简短表示；
最后，该工作在模型评估上，利用百度搜索引擎的热搜最长公共子串，人为筛选出事件粒度的话题热搜词，爬取这些事件热搜词及搜索引擎，得到该事件文档集中各个文档的标题，构造测试集，并用ROUGE值进行评估。
对于更详尽的信息，可以查看参考文献3。
二、最长公共子串方案求解
最长公共子串( )，即给定两个字符串，求出它们之间最长的相同子字符串，并且要求该字符串必须连续。
1、问题定义
给定两个字符串：str=、str2=，求出str和str2的最长公共子串为bcbce，公共子串长度为5。
2、代码实现
最直接的解法自然是找出两个字符串的所有子字符串进行比较看他们是否相同，然后取得相同最长的那个。对于一个长度为n的字符串，它有n(n+1)/2 个非空子串。所以假如两个字符串的长度同为n，通过比较各个子串其算法复杂度大致为O(n4)。这还没有考虑字符串比较所需的时间。
因此，为了加快速度，我们可以使用动态规划的方式，用一个矩阵来记录两个字符串中全部位置的两个字符之间的匹配状况，如果匹配则为1，不然为0。而后求出对角线最长的1的序列，其对应的位置就是最长匹配子串的位置。如下所示：
class Solution:
def LongestCommonSubstring(self,s1,s2):
record = [0 for i in range(len(s2)+1)]
res,index = 0,0
for i in range(len(s1)):
for j in range(len(s2)-1,0,-1):
if s1[i]==s2[j]:
record[j] = record[j-1]+1
else:
record[j] = 0
if res<record[j]:
res=record[j]
index=j
return s2[index-res+1:index+1]
if __name__ =="__main__":
s = Solution()
s1,s2 = "acaccbabb","acbac"
print(s.LongestCommonSubstring(s1,s2))
>> cba
3、应用场景
实际上，在搜索场景中，该方案也有应用场景，例如，某个用户在网站搜索框中输入一个字符串hish，但其实用户想输入的是fish，介绍这个网站的可选字典里面只有 fish 和 vista 这两个相似单词。算法需要猜测用户到底想要搜索的是什么字符串？
因此，在实现上就可以采用动态规划的方法进行处理，目标是要将某个指标最大化，在这个例子中，要找出两个单词的公共子串，更大的那个即为结果。
三、最长公共子序列方案求解
最长公共子序列，即 ，是子序列问题中的重要一类，区别于最长公共子串，最长公共字串要求连续，而最长公共子序列不要求连续。
例如，对于、两个字符串，最长公共子序列为blog（,），最长公共子串为lo（, ）。
1、问题定义：
在定义上，一个序列S任意删除若干个字符得到新序列T，则T叫做S的子序列；
在给定两个序列X和Y的公共子序列中，长度最长的那个，定义为X和Y的最长公共子序列。
例如：
字符串13455与的最长公共子序列为455；
字符串acdfg与adfc的最长公共子序列为adf；
2、代码实现：
针对这类问题，最直接的做法就是用动态回归的思想，一个矩阵记录两个字符串中匹配状况，如果匹配则为左上方的值加1最长公共子串，不然为左方和上方的最大值。一个矩阵记录转移方向，而后根据转移方向，回溯找到最长子序列。
具体实现如下：
class Solution:
def LongestCommonSubSequence(self,text,query):
# 生成字符串长度加1的0矩阵，m用来保存对应位置匹配的结果
m = [ [ 0 for x in range(len(s2)+1) ] for y in range(len(s1)+1) ]
# d用来记录转移方向
d = [ [ None for x in range(len(s2)+1) ] for y in range(len(s1)+1) ]
for p1 in range(len(s1)):
for p2 in range(len(s2)):
if s1[p1] == s2[p2]: #字符匹配成功，则该位置的值为左上方的值加1
m[p1+1][p2+1] = m[p1][p2]+1
d[p1+1][p2+1] = 'ok'
elif m[p1+1][p2] > m[p1][p2+1]: #左值大于上值，则该位置的值为左值，并标记回溯时的方向
m[p1+1][p2+1] = m[p1+1][p2]
d[p1+1][p2+1] = 'left'
else: #上值大于左值，则该位置的值为上值，并标记方向up
m[p1+1][p2+1] = m[p1][p2+1]
d[p1+1][p2+1] = 'up'
(p1, p2) = (len(s1), len(s2))
s = []
while m[p1][p2]: #不为None时
c = d[p1][p2]
if c == 'ok': #匹配成功，插入该字符，并向左上角找下一个
s.append(s1[p1-1])
p1-=1
p2-=1
if c =='left': #根据标记，向左找下一个
p2 -= 1
if c == 'up': #根据标记，向上找下一个
p1 -= 1
s.reverse()
return ''.join(s)
if __name__ =="__main__":
s = Solution()
s1,s2 = "acaccbabb","acbac"
print(s.LongestCommonSubSequence(s1,s2))
>> acbac
3、应用场景
在具体应用上，可用于模糊搜索、字符串相似度计算等诸多场景。例如：
在图形相似处理、媒体流的相似比较、计算生物学方面，生物学家常常利用该算法进行基因序列比对，由此推测序列的结构、功能和演化过程。
在自然语言处理领域，最长公共子序列可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。另一方面，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。
四、最长子串和子序列在文本标题抽取的应用实验
在文章一开始，我们就说到，在文本聚类场景中，我们可以事先将相同意思的文本标题聚在一起，为了得到聚类文本的统一表述，我们常常可以通过计算两个字符串之间的公共部分作为意义片段来呈现。
为了尽可能复现出右侧的标题结果，我们采用上述两套方案来实验。
1、编码实验
为了得到尽可能可用的事件标题，我们从搜索网页结果中转写了5条标题，并形成集合，分别两两字符串进行比对，计算得到最大公共子串和最大公共子序列，并统计频次，按照频次从大到小排列。
ss = [
"...普京:准备通过对话解决冲突,实现俄方要求才可能停止军事行动!",
"俄媒:普京告诉埃尔多安,实现俄方要求才可能停止军事行动",
"普京告诉埃尔多安,实现俄方要求才可能停止军事行动",
"普京:只有乌方满足俄方要求 才可能停止特别军事行动",
"快讯!俄媒:普京告诉埃尔多安,实现俄方要求才可能停止军事行动"
]
print("原标题集合：")
print(ss)
print('*****'*10)
for s1 in ss:
for s2 in ss:
if s1 == s2:
continue
commons.append(s.LongestCommonSubstring(s1,s2))
common_dict = Counter(commons).most_common()
print("最长公共子串集合：", common_dict)
print('#####'*5)
print("最长公共子串：", common_dict[0][0])
print('******'*10)
commons = []
for s1 in ss:
for s2 in ss:
if s1 == s2:
continue
commons.append(s.LongestCommonSubSequence(s1,s2))
common_dict = Counter(commons).most_common()
print("最长公共子序列集合：", common_dict)
print('#####'*5)
print("最长公共子序列：", common_dict[0][0])
2、对比实验效果：
为了对比上述两个方案，我们可以进行对比实验，得到一下结果：
我们可以看到，最长公共子序列的效果要比最长公共子串有更好的效果，与标准标题““普京称实现要求才可能停止军事行动”已十分接近。
当然，效果的好坏取决于文本的质量和数量，质量不一定可控，但这种解决思路是值得大家尝试和探索的。
总结
本文主要介绍了情报分析中最大公共子串的用处，从代表工作，以及两个具体动手实践进行了论述，相信大家已经有些了解，也可以进行进一步尝试。
实际上，在其他场景中，我们也能看到类似的用法：生物学家根据最长公共序列来确定 DNA 链的相似性，进而判断两种动物或疾病有多相似。
最长公共序列还被用来寻找多发性硬化症治疗方案；源代码管理中，git diff指令，可以查找出编辑前后文件的差异；常用的编辑距离，判断字符串的相似程度可以通过这个技术从拼写检查到判断用户上传的资料是否是盗版。
小的技巧，加以合理利用，往往会取得令人耳目一新的效果，大家可以多尝试。最后，感谢本文参考文献3的工作。
参考文献
1、
2、
3、王伟玉, 史存会, 俞晓明,等. 一种事件粒度的抽取式话题简短表示生成方法[J]. 山东大学学报：理学版, 2021, 56(5):11.
进技术交流群请添加AINLP小助手微信（id: ainlp2)
请备注具体方向+所用到的相关技术点 关于AINLP
AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLP小助手微信(id：ainlp2)，备注工作/研究方向+加群目的。
阅读至此了，分享、点赞、在看三选一吧
限 时 特 惠： 本站每日持续稳定更新内部创业教程，一年会员只需98元，全站资源免费下载 点击查看详情
站 长 微 信： muyang-0410声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，请联系我们进行处理。
