没有合适的资源?快使用搜索试试~ 我知道了~
4466队B题1
需积分: 0 0 下载量 36 浏览量
2022-08-03
16:03:11
上传
评论
收藏 1.32MB PDF 举报
温馨提示
试读
25页
英文摘要This article main discussion is the string matching problem, we use an exact
资源详情
资源评论
资源推荐
参赛队号#4466
第十二届“认证杯”数学中国
数学建模网络挑战赛
承 诺 书
我们仔细阅读了第十二届“认证杯”数学中国数学建模网络挑战赛的竞赛规则。
我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网
上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。
我们知道,抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的
资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参
考文献中明确列出。
我们郑重承诺,严格遵守竞赛规则,以保证竞赛的公正、公平性。如有违反竞赛规
则的行为,我们接受相应处理结果。
我们允许数学中国网站(www.madio.net)公布论文,以供网友之间学习交流,数学中
国网站以非商业目的的论文交流不需要提前取得我们的同意。
我们的参赛队号为:4466
参赛队员 (签名) :
队员 1:何东清
队员 2:马壮壮
队员 3:杨壮
参赛队教练员 (签名): 指导教师组
参赛队伍组别(例如本科组):本科组
参赛队号#4466
第十二届“认证杯”数学中国
数学建模网络挑战赛
编 号 专 用 页
参赛队伍的参赛队号:(请各个参赛队提前填写好):
#4466
竞赛统一编号(由竞赛组委会送至评委团前编号):
竞赛评阅编号(由竞赛评委团评阅前进行编号):
参赛队号#4466
2019 年第十二届“认证杯”数学中国
数学建模网络挑战赛第一阶段论文
题 目 基于精准匹配和模糊匹配的外星语字典解析模型
关 键 词 精准匹配 近似匹配 BM 算法 Levenshtein Distance 算
法 gram 索引
摘 要
本文主要讨论的是字符串的匹配问题,我们利用精确匹配算法和近似匹配算法,分
别建立了字符串精确匹配模型和字符串近似匹配模型,通过使用两种匹配算法,可以对
文本中的字符串匹配得更加准确可靠,克服了 BM 及其改进算法等精确匹配算法遇到字
符的替换,删失和插入给匹配带来的大量缺失的问题,确定出了令人满意的字符串匹配
数目。
模型 1:假设无替换错误,文本运用 BM 算法对其进行精确匹配,BM 算法主要采用
字符串从右向左匹配的方式,它首先将字母序列和目标文本对其,然后从字母序列的最
后一个字母开始与其对应的在目标文本中的字母进行匹配,如果匹配成功,则进行倒数
第二位进行匹配,直到完全匹配,从而查询出字母序列的个数,如果在匹配过程中有字
母匹配不成功,则根据 BM 算法,字母序列整体向后移动,从而和下一位目标对应字母
片段匹配,直到匹配成功,同时,我们在 BM 算法的基础上对其进行了改进,采用 BMH
算法算法再次进行字符串的精确匹配。并将匹配到的字符串输出,对于没有匹配到的字
符串归为复杂文本,需要进一步分析。
模型 2:假设有替换错误,则对文本字符串运用 Levenshtein Distance 算法和 gram
索引等算法进行字符串的近似匹配。Levenshtein Distance 算法是指两个字符串之间,
由一个转成另一个所需的最少编辑操作次数。在本文中,由于题目中说明可能出现的替
换错误最多不超过 4 个,所以,我们利用 Levenshtein Distance 算法对目标文本和字母
序列进行相似段计算,这里我们选择字母序列长度为 20 个字母,当计算出来的相似度
如果大于等于 80%,则将此目标序列认为我们所需要的字母序列,同时,对于没能匹
配的字符串再进行 gram 索引算法的近似匹配,gram 索引的局部最优化近似子串查询算
法(GASQ)。我们尽可能得防止字符串匹配的遗漏,同样,对于没有匹配到的字符串归为
复杂文本,需要进一步分析。
关键词:字符串 精确匹配 近似匹配 BM 算法 Levenshtein Distance 算法 gram 索
引。
参赛队号: #4466
所选题目: B 题
参赛密码
(由组委会填写)
参赛队号#4466
英文摘要
This article main discussion is the string matching problem, we use an exact
match algorithm and approximate matching algorithm, respectively established
string matching model precise and approximate string matching model, by using
two kinds of matching algorithm, can be in the text string matching more accurate
and reliable, improved algorithm overcomes the BM and its exact match algorithm
with characters such as replacement, delete and insert to match a lot of the
problem of the missing, identify a satisfactory number of string matching.
Model 1: Assuming no substitution errors, text using BM algorithm carries
on the exact match, BM algorithm is mainly with the method of matching a string
from right to left, it will first letter sequence and the target text, to its
and then from the last letter of alphabet sequence start the corresponding
letters in the target text matching, if the match is successful, in the
penultimate match, until the match completely, thus the query sequence number
of the letters, if you have any letters in the matching process matching is not
successful, depending on the BM algorithm, letters backward sequence as a whole,
and thereby the next target fragments matching corresponding letters, until the
match is successful, at the same time, On the basis of BM algorithm, we improved
it, and used BMH algorithm to precisely match the strings again. The matched
strings are outputted, and the unmatched strings are classified as complex text,
which requires further analysis.
Model 2: if replacement error is assumed, Levenshtein Distance algorithm
and gram index algorithm are used to approximate match the text string. The
Levenshtein Distance algorithm is the minimum number of edits required to go
from one string to the other between two strings. In this article, because that
may appear in the title of the replacement error is no more than four, so, we
use the Levenshtein algorithm of short of target text and letter sequence
similarity computation, here we select alphabetical sequence length of 20, if
when calculating the similarity is greater than or equal to 80%, will the target
sequence, think of what we need letters at the same time, for the failed to match
the string "gramm indexing algorithm approximate matching again," gramm index
of local approximate substring query optimization algorithm (GASQ). We do our
best to prevent the omission of string matches, as well as to classify unmatched
strings as complex text, which requires further analysis.
Key words: string exact match approximate match BM algorithm Levenshtein
Distance algorithm gram index.
参赛队号#4466
1
一、问题重述
1.1 背景:
本题属于模式匹配类建模,字符串匹配是模式匹配中最简单的一个问题,在实际应
用中,字符串匹配技术在计算机科学,语义学以及分子生物学等领域也具有相当重要的
地位,在以模式匹配为主的网络安全应用方面中也发挥着举足轻重的作用。
1.2 需要解决的问题:
一种未知的语言,现只知道其文字是以 20 个字母构成的。已经获取了许多段由该
语言写成的文本,但每段文本只是由字母组成的列,没有标点符号和空格,无法理解其
规律及含义。我们希望对这种语言开展研究,有一种思路是设法在不同段文本中搜索共
同出现的字母序列的片段。语言学家猜测:如果有的序列片段在每段文本中都会出现,
这些片段就很可能具备某种固定的含义(类似词汇或词根),可以以此入手进行进一步的
研究。在文本的获取过程中,由于我们记录技术的限制,可能有一些位置出现了记录错
误。可能的错误分为如下三种:
1. 删失错误:丢失了某个字母;
2. 插入错误:新增了原本不存在的字母;
3. 替换错误:某个字母被篡改成了其他的字母。
第一阶段问题: 假设我们已经获取了 30 段文本,每段文本的长度都在 5000–
8000 个字母之间。我们希望找到的片段的长度在 15–21 个字母之间。 为简单起见,
我们假设文本中出现的错误只有替换错误,而且对我们要找的 片段而言,在文本中每
次出现时,最多只会出现 4 个字母的替换错误。请设计有效的数学模型,快速而尽可
能多地找到符合要求的字母片段,并自行编撰算例来验证算法的效果。
二、问题分析
由于替换,删除和插入错误会对就精准匹配算法 BM 算法产生一定的影响。所以我
们把第一阶段分为问题一和问题二。
问题一:假设无替换,删除和插入错误,则对文本运用 BM 算法及其改进算法进行
字符串的精准匹配。
问题二:假设有替换,删除和插入错误,则对文本运用 Levenshtein Distance 算法
和 gram 索引的模糊匹配算法进行字符串的模糊匹配。
通过将阶段一的问题进一步划分为问题一和问题二,可以对文本中的字符串匹配得
更加快速,准确,可靠,同时克服了 BM 及其改进算法等精确匹配算法遇到字符的替换,
删失和插入给匹配带来的大量缺失的问题。
剩余24页未读,继续阅读
禁忌的爱
- 粉丝: 20
- 资源: 334
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0