专业分销网站建设,wordpress添加登录注册按钮,网站建设四步骤,网页设计与网站建设课程设计报告2019年认证杯SPSSPRO杯数学建模
基于统计和迭代匹配的未知语言文本片段提取模型
B题 外星语词典
原题再现#xff1a; 我们发现了一种未知的语言#xff0c;现只知道其文字是以 20 个字母构成的。我们已经获取了许多段由该语言写成的文本#xff0c;但每段文本只是由字母…2019年认证杯SPSSPRO杯数学建模
基于统计和迭代匹配的未知语言文本片段提取模型
B题 外星语词典
原题再现 我们发现了一种未知的语言现只知道其文字是以 20 个字母构成的。我们已经获取了许多段由该语言写成的文本但每段文本只是由字母组成的序列没有标点符号和空格无法理解其规律及含义。我们希望对这种语言开展研究有一种思路是设法在不同段文本中搜索共同出现的字母序列的片段。语言学家猜测如果有的序列片段在每段文本中都会出现这些片段就很可能具备某种固定的含义 (类似词汇或词根)可以以此入手进行进一步的研究。在文本的获取过程中由于我们记录技术的限制可能有一些位置出现了记录错误。可能的错误分为如下三种 1. 删失错误丢失了某个字母 2. 插入错误新增了原本不存在的字母 3. 替换错误某个字母被篡改成了其他的字母。 第二阶段问题 现假设我们已经获取了 30 段文本每段文本的长度都在5000–8000 个字母之间。我们希望找到的片段的长度为 15 个字母。由于技术的限制当我们在记录每个字母时都可能有五分之一的概率发生错误。错误类型可能为删失错误、插入错误或替换错误每个错误只涉及一个字母且每个错误的发生是独立的。请你设计合理的数学模型快速而尽可能多地找到符合要求的片段并自行编撰算例来验证算法的效果。如果我们事先不知道所寻找的片段的长度算法又应当进行什么改进呢
整体求解过程概述(摘要) 任何自然语言系统都可看作是表达意义的符号系统本文提出的模型的目标是如何有效且快速地从完全未知的语言文本中提取出可能具有某个固定含义的片段并考虑了在记录文本过程中由于技术限制出现的错误能够最大限度提取出可能由于记录错误导致出错的片段并分析错误的类型替换错误、删失错误、插入错误。 针对问题一本文假设希望获取到的片段长度固定的为 15 个字母从时间上和空间上都简化了复杂度。首先我们按照要求模拟了 30 段长度在 5000~8000 个字母之间且含有错误的外星文本。具体做法是先构造一个每个字母呈 Gauss 分布的片段库每个片段长度固定为 15个字母再根据片段库里的片段构造出 30 段正确的文本每个片段在文中也是呈 Gauss分布接着又根据正确的文本构造出 30 段错误的文本其特点是每个字母有 1/5 的出错概率并且每个错误类型出现的概率皆为 1/3。然后本文对外星文本进行大量统计和分析寻找到截取出的每个片段的三个属性特征由此建立三维坐标系。具体做法是首先以窗体形式截取出所有片段固定窗体宽度为 15然后基于马尔可夫Markov模型获取片段的概率紧接着回到外星文本统计出每个字母的频率观察其分布最后统计出每个片段中不同符号字母的个数作为片段的第三个特征量经过这些工作就可以建立三维坐标系。接着对于上一步所得到的片段三维特征量进行减法聚类subtrative clustering methodSCM便得出中心点的三维坐标根据中心点的坐标确定出中心片段即我们的目标片段。最后将取得的目标片段与片段库 1 作比对正确率为 73.3%。最后还对模型一做了扩展在模型一的基础上结合汉明距离(Hamming Distance)分析出错误片段的错误类型。分析结果表明错误片段的错误类型基本可以确定。 针对问题二本文通过改进模型一建立了模型二改进内容最主要有以下四个方面第一方面将模型一的片段库里的定长片段改为长度在 15~21 字母之间的不定长片段其中 15~21 这一片段长度是根据第一阶段的问题而假定的在模型二中只是用来说明模型长度的范围可以灵活改变。第二方面是建模的难点不定长的片段应如何截取才能得到我们所需要的片段我们丢弃了传统的方法传统方法是将每个长度的片段都截取一遍而本文通过对片段进行仔细研究找到这样一个特点从文本的同一位置出发非最短长度这里指长度为16、17、18、19、20、21 的片段必定已经包含最短长度的片段这里指长度为 15 的片段即最短长度的片段一定是非最短长度的片段的子串此处忽略非最短片段间的相互包含关系如长度为 19 的片段是长度为 21 片段的子片段。根据这一特点本文只选取最短片段长度作为窗体大小截取子串再根据后面的算法找出子串的“后半段”来确定目标片段。第三方面是建模的重点前面只截取了片段的子串那么如何找出连接在子串后的后半段是该步骤要解决的问题。解决方法是迭代匹配搜索算法把中心子串带回外星文本按一定的概率标准和长度限制进行“首字母位置不变尾字母右移 1 位”匹配搜索直至确定出目标片段。最后将取得的目标片段与片段库 1 作比对正确率为 83.3%。第四个方面分析错误类型时长短不一的两个片段先使用“-”进行补位后再进行汉明距离的计算。另外本文运用 Java、Matlab 语言用 Excel 工具做辅助对模型和问题进行了仿真实验验证了模型的可行性。 最后本文还对模型进行了量化评价总体来说通过对问题一的分析基本建立起了整体模型通过问题二对模型一进行了改进模型二的可靠性较强有效性适中但模型的使用灵活性大范围广还可用于自然语言处理Natural Language ProcessingNLP、机器学习(Machine Learning)等方面是一个应用性能比较强的模型。
问题分析 解读未知文本的过程第一步是寻找很可能具备某种固定的含义(类似词汇或词根)的片段。这些希望被找到的片段出现频率不一从经验的角度出发文本的基元出现频率一般服从 Gauss 分布为此我们假设各片段、各字母在文本中出现的频率大致服从Gauss 分布。 针对问题一 问题一的要求是有 30 段长度为 5000~8000 的外星文本片段长度固定为 15每个字母有 20%的概率发生错误考虑有三种错误删失错误、插入错误、替换错误每个错误只涉及一个字母且错误是独立发生的。要求快而尽可能多地找到符合要求的片段。正对该问题本文的基本思路是首先构造外星文本对文本截取片段、做一些基础统计由此建立三维坐标系然后通过减法聚类找到目标片段到此我们还要根据聚类中心点以及汉明距离分析出有可能出现错误的片段和错误类型。 针对问题二 问题二的要求是在问题一的基础上假设事先不知道所寻找的片段的长度要如何改进模型一。本文假设片段的长度在 15–21 个字母之间参考第一阶段的问题要求设想在截取片段的过程中在同一个位置往后截取长度为 15 的片段S1和截取长度为18可以为 16、17、18、19、20、21的片段S2那么S2必定包含S1换句话说S1是S2的子串。在模型一的基础上我们改进的部分是 1 建立长度不固定的片段库 2 先只截取最小字串长度15的所有片段 3 减法聚类的结果其实就是我们要找的目标片段的子串把子串带入外星文本搜索以这个子串为字串的更长片段根据频率确定出本来该有的片段长度。
模型假设 在求解过程中假设 (1) 文本中一共由 20 个不同的符号构成符号的形状并不是主要研究对象这里假设是英文字母表的前 20 个字母a~t (2) 文本没有空格没有标点符号 (3) 未知片段出现的频率服从 Gauss 分布 (4) 由于人类技术限制替换和插入的字母是随机的并且每个错误只涉及一个字母错误是独立发生的 (5) 每个字母发生错误的概率是 1/5 (6) 每种错误删失错误、插入错误、替换错误发生的概率都是 1/3 (7) 对于问题一片段长度为 15对于问题二希望找到的片段的长度在 15–21 个字母之间参考第一阶段的问题要求。
论文缩略图 全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可
部分程序代码(代码和文档not free)
import java.io.*;
import java.util.*;
public class dictionary {
public static void getStringRandom(String s,int leng) {
File filenew File(s);
String linenull;
String chars abcdefghijklmnopqrst;
Double[] p
{0.3,0.6,0.6,0.7,0.75,0.8,0.85,0.9,0.9,0.95,0.95,0.95,0.9,0.85,0.8,0.75,0.7,0.6,0.4,0.3};
String val ;//片段字符串
char c\0;
ListString pd new ArrayListString();//片段
ListDouble pr new ArrayListDouble();//概率
try{
BufferedReader buf new BufferedReader(new FileReader(file));
while((line buf.readLine())!null){
for(int i 0; i leng; i) {
int m (int)(Math.random() * 20);
if (mingZhong(p[m])) {
cchars.charAt(m);
}
val c;
}
pd.add(val);//片段
pr.add(Double.parseDouble(line)); //概率
val;
if(pd.size()50){
break;
}
if(pd.size()50){
break;
}
}
buf.close();
for (int m0;mpr.size() ;m ) {
System.out.println(pd.get(m):pr.get(m));
}
StringBuilder sb new StringBuilder();
File file_result new File(AlienLang.txt);
PrintWriter output new PrintWriter(file_result);//创建写对象
Random rand new Random();
for (int k0;k30 ;k ) {
int zishu rand.nextInt(3001)5000;//生成 50008000 之间的随
机数包括 8000
while (true) {
int ra (int)(Math.random()*50);
if (mingZhong(pr.get(ra))) {
sb.append(pd.get(ra));
}
if (sb.length()(zishu-15) sb.length()(zishu15)) {
output.println(sb.toString());
sb.delete( 0, sb.length() );
break;
}
}
}
output.close();System.out.println(结束);
}catch(Exception e){
e.printStackTrace();
}
}
public static boolean mingZhong(double hr) {
Random r new Random();
int a r.nextInt(100);//随机产生[0,100)的整数每个数字出现的概率为
1%
if(a(int) (hr*100)){ //前 hr*100 个数字的区间代表的几率
return true;
}else{
return false;
}
}
public static void main(String[] args) {
getStringRandom(pro.txt,15);
}
}import java.io.*;
import java.util.*;
class ErrorText{
public static void main(String[] args) throws Exception{
File file_source new File(AlienLang.txt);
File file_result new File(AlienLang_err.txt);
InputStreamReader is new InputStreamReader(new
FileInputStream(file_source));//将输入的字节流转换成字符流
BufferedReader brnew BufferedReader(is);//将字符流添加到缓冲流PrintWriter output new PrintWriter(file_result);//创建写对象
String strnull;
String chars abcdefghijklmnopqrst;
try{
while ((str br.readLine()) ! null){
StringBuilder sb new StringBuilder(str);
for (int i0;isb.length() ;i ) {
if (mingZhong(0.2)) {
if (err_type()1) {//插入
int ra2 (int)(Math.random()*20);
String chString.valueOf(chars.charAt(ra2));
sb.replace(i,i1,String.valueOf(str.charAt(i))ch);//sb.append(str.charAt(i)ch);
i;//下一个字母
}else if (err_type()2) {//替换
String chnull;
while (true) {//不能替换成同一个字母。例如 b 不能
替换成 b
int ra2 (int)(Math.random()*20);
chString.valueOf(chars.charAt(ra2));
if (!ch.equals(String.valueOf(str.charAt(i)))) {
break;
}
}
sb.replace(i,i1,ch);//sb.append(ch);
}else {//缺失
sb.delete(i,i1);//不包含 i1
i--;
}
}
}
output.println(sb.toString());
}
}catch(FileNotFoundException e){
e.printStackTrace();
}br.close();
output.close();System.out.println(结束);
}
public static boolean mingZhong(double hr) {
Random r new Random();
int a r.nextInt(100);//随机产生[0,100)的整数每个数字出现的概率为
1%
if(a(int) (hr*100)){ //前 hr*100 个数字的区间代表的几率
return true;
}else{
return false;
}
}
public static int err_type() {
Random r new Random();
int flag;
int a r.nextInt(100);//随机产生[0,100)的整数每个数字出现的概率为
1%
if(a33){
flag 1;
}else if(a66){
flag 2;
}else {
flag 3;
}
return flag;
}
}全部论文及程序请见下方“ 只会建模 QQ名片” 点击QQ名片即可
