第一次个人编程作业

第一次个人编程作业

1.题目

题目：论文查重

描述如下：

设计一个论文查重算法，给出一个原文文件和一个在这份原文上经过了增删改的抄袭版论文的文件，在答案文件中输出其重复率。

原文示例：今天是星期天，天气晴，今天晚上我要去看电影。
抄袭版示例：今天是周天，天气晴朗，我晚上要去看电影。
要求输入输出采用文件输入输出，规范如下：

从命令行参数给出：论文原文的文件的绝对路径。
从命令行参数给出：抄袭版论文的文件的绝对路径。
从命令行参数给出：输出的答案文件的绝对路径。
我们提供一份样例，使用方法是：orig.txt是原文，其他orig_add.txt等均为抄袭版论文。

注意：答案文件中输出的答案为浮点型，精确到小数点后两位

2.需求分析

检测文件内容的相似度并将结果输出到另一个文件中

1. 读入文件并转换成字符串
2. 利用Levenshtein编辑距离算法计算两字符串的相似度
3. 输出至目标文件

3.各模块设计

• FileToStr：用于读取文件并将文件字符转换为字符串
• Distance：利用Levenshtein算法计算相似度
• StrToFile：将结果输出到目标文件
  

关键算法为Distance类中实现的Levenshtein编辑距离算法，该算法计算出待测字符串至少经过几次变换才转换成原字符串，以此来计算相似度，并且这样定义的相似度更为合理。算法核心思想：假设原字符串为a[1…i],待测字符串为b[1…j],那么要算的是b[1…j]至少经过几次变换转换成a[1…i],我们只需要知道最后一次转换之前，至少需要几次转换，再分析情况就可以得出结果，而最后一次之前有三种情况：
1.b[1…j]经过n次转换为a[1…i-1]
2.b[1…j-1]经过n次转换为a[1…i]
3.b[1…j-1]经过n次转换为a[1…i-1]
在1情况的基础上我们只需再加上一步增加操作就可以转换为目标字符串
在2情况的基础上我们只需再加上一步删除操作就可以转换为目标字符串
在1情况的基础上，当b[j]恰好等于a[i]时，那么只需要n次，若否，则加上一次替换操作

利用递归思想我们可以知道，只要知道空字符串转换为目标字符a[1…i]全部位置的各自需要的次数，和待测字符b[1…j]变成空字符各自需要的次数再依次根据以上三种情况分析就可以得出结果。因此该算法的基本步骤为：

• 创建distanceMatrix[j+1][i+1]的矩阵，用来记录从空到j位b字符串转换成空到i位a字符串
• 初始化矩阵，易知，从空转换为空到i位a字符串，只需要0到a,第一列[j][0]同理

      	   for (int i = 0; i <= a.length(); i++) {
               distanceMatrix[0][i] = i;
           }
           for (int i = 0; i <=b.length(); i++) {
               distanceMatrix[i][0] = i;
           }

• 依次算出distanceMatrix[i][j]的值，因要选择最小值则需进行判断distanceMatr[i-1][j-1]是不是都不比其他两个大，若是，则进行判断a[i]是否等于b[j],等于则distanceMatri[i][j]=distanceMatrix[i-1][j-1]，否则distanceMatrix[i][j]=distanceMatrix[i-1][j-1]+1;如果其他两值存在有比distanceMatrix[i-1][j-1]小的，则

distanceMatrix[y][x]=distanceMatrix[y-1][x]<distanceMatrix[y][x-1]?distanceMatrix[y-1][x]+1:distanceMatrix[y][x-1]+1;

• 最终distanceMatrix[i][j]就是实际要求的值，1-distanceMatrix[i][j]/max(i,j)就是相似度

4.模块性能分析

5.单元测试

1. 测试文件读取

public class Test{
public static void main(String[] args){
        FileInputStream inputStream1 =new FileInputStream(args[0]);
        FileInputStream inputStream2 =new FileInputStream(args[1]);
        byte[] bytes=new byte[inputStream1.available()];
        a =new String(bytes,0, inputStream1.read(bytes));
        bytes=new byte[inputStream2.available()];
        b =new String(bytes,0,inputStream2.read(bytes));
        System.out.println(a);
        System.out.println(b);
}
}

2. 测试算法矩阵以及相似度的计算

    public static void main(String[] args){
        String a="abc";
        String b="abd";
        String str =String.format("%.2f",Levenshtein(a,b));
        System.out.println(str);
    }

3. 测试覆盖率

6. 异常处理

//本次作业没有设计额外异常仅运用io包中的几个异常类
import java.io.FileNotFoundException;
//文件查找异常，当地址错误或其他特殊情况抛出
import java.io.IOException;
//文件读取或写出出现异常或输入输出流关闭异常时抛出

7.PSP

最后

以上就是碧蓝小蝴蝶为你收集整理的第一次个人编程作业的全部内容，希望文章能够帮你解决第一次个人编程作业所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。