任务一

步骤一

对于任意两个中文字符串,使用Levenshtein Distance算法比较两个字符串的相似度

解决方法:

这里的Levenshtein Distance指的是编辑距离,也就是指两个字符串之间,由一个转换成另一个所需要的最少编辑操作次数。

每处的计算规则:

这处上边的值加1,左边的值加1,如果这两个字符相同,则在左上角的值的基础上加0,不同则加1。然后取这三个数中最小的值。

例如abcabe

abcabc
abd0123
a1012
b2101
d3211

经过有限次的重复后,获得右下角的操作数。

相似度的计算即为

$$ 相似度=1-\frac{(右下角的操作数)}{字符串的最大长度}\times100\% $$

代码实现

package dachuang;

import java.util.*;

public class compare {
    public static void main(String[] args) {
        compare lt = new compare();
        Scanner scanner = new Scanner(System.in); 
        System.out.print("Input your string1: "); 
        String str1 = scanner.nextLine(); 
        System.out.print("Input your string2: "); 
        String str2 = scanner.nextLine(); 
        System.out.println("similarityRatio=" + lt.getSimilarityRatio(str1, str2, true)*100+"%");
    }
    
    private static int compare(String str1, String str2, boolean isIgnore) {
        int d[][]; // 矩阵
        int n = str1.length();
        int m = str2.length();
        int i; // 遍历str1的
        int j; // 遍历str2的
        char ch1; // str1的
        char ch2; // str2的
        int temp; // 记录相同字符,在某个矩阵位置值的增量,不是0就是1
        if (n == 0) {
            return m;
        }
        if (m == 0) {
            return n;
        }
        d = new int[n + 1][m + 1];
        for (i = 0; i <= n; i++) { // 初始化第一列
            d[i][0] = i;
        }

        for (j = 0; j <= m; j++) { // 初始化第一行
            d[0][j] = j;
        }

        for (i = 1; i <= n; i++) { // 遍历str1
            ch1 = str1.charAt(i - 1);
            // 去匹配str2
            for (j = 1; j <= m; j++) {
                ch2 = str2.charAt(j - 1);
                if (isIgnore) {
                    if (ch1 == ch2 || ch1 == ch2 + 32 || ch1 + 32 == ch2) {
                        temp = 0;
                    } else {
                        temp = 1;
                    }
                } else {
                    if (ch1 == ch2) {
                        temp = 0;
                    } else {
                        temp = 1;
                    }
                }

                // 左边+1,上边+1, 左上角+temp取最小
                d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + temp);
            }
        }
        return d[n][m];
    }

    private static int min(int one, int two, int three) {
        return (one = one < two ? one : two) < three ? one : three;
    }

    public static float getSimilarityRatio(String str1, String str2, boolean isIgnore) {
        float ret = 0;
        if (Math.max(str1.length(), str2.length()) == 0) {
            ret = 1;
        } else {
            ret = 1 - (float) compare(str1, str2, isIgnore) / Math.max(str1.length(), str2.length());
        }
        return ret;
    }

}

目前存在的问题(后继优化):

依赖一定的顺序,比如输入你好我好的时候,相似度为50%

但是如果输入斗罗大陆封号斗罗的时候,本来相似度应该为50%,但计算结果却为0

步骤二

对于任意两段文字,要求能去除文字中的 “的”“得”“地”等无意义词汇,保留文字中的名词。

对于这里的两个想法:

  • 如果只是在一段文字中删去 的得地 等有限个无意义词语,那么只需要进行有限次的重复比较,如果含有已经枚举出的词语,那么就在字符串中删去这个词语。
  • 如果给出的是一段文字,我们还可以根据TextRank算法根据词频提取出关键词,因为一般词频比较高的就是知识点名词,而提取出的名词大部分都不含无意义词语,这里其实和钟宜芮的部分比较像。说白了就是在已经提取出的教学知识点大纲再进行一次提取,目前这里的想法是调用API。

若为第一种情况,那就利用replace函数进行替换,从而达到去除文字中无意义词汇的目的。

缺点:虽然实现了基本的功能,可以满足绝大多数的需求,但仍然可能存在小概率出现的词汇,因为没有想到所以未能删去。

实现代码:

package dachuang;

import java.util.*;

public class delete {
    public static void main(String[] args) {
        delete lt = new delete();
        Scanner scanner = new Scanner(System.in); 
        System.out.print("Input your string1: "); 
        String str1 = scanner.nextLine(); 
        str1=str1.replace("的","");
        str1=str1.replace("得","");
        str1=str1.replace("地","");
        str1=str1.replace("吧","");
        str1=str1.replace("和"," ");
        str1=str1.replace("与"," ");
        System.out.print("Input your string2: "); 
        String str2 = scanner.nextLine(); 
        str2=str2.replace("的","");
        str2=str2.replace("得","");
        str2=str2.replace("地","");
        str2=str2.replace("吧","");
        str2=str2.replace("和"," ");
        str2=str2.replace("与"," ");
        System.out.println(str1);
        System.out.println(str2);
    }
}

若为第二种情况,就需要调用API了。。。

HanLP或者百度的API

如何在一个字符串去掉指定字符串

1.借助 jdk java.lang.String.replace(CharSequence, CharSequence) 方法,实例:

 public static void main(String[] args){
        //从 feitianbenyue 中移除 tian
        String str = "feitianbenyue";
        String removeStr = "tian";
        System.out.println(str.replace(removeStr, ""));
    }

输出:

feibenyue

2.使用commons-lang3 jar

org.apache.commons.lang3.StringUtils.remove(String, String),实例:

public static void main(String[] args){
      //从 feitianbenyue 中移除 tian
      String str = "feitianbenyue";
      String removeStr = "tian";
      //System.out.println(str.replace(removeStr, ""));
      System.out.println(StringUtils.remove(str, removeStr));
  }    //输入同上

以下实例中我们通过字符串函数 substring() 函数来删除字符串中的一个字符,我们将功能封装在 removeCharAt 函数中。

实例代码如下:

public class Main {
   public static void main(String args[]) {
      String str = "this is Java";
      System.out.println(removeCharAt(str, 3));
   }
   public static String removeCharAt(String s, int pos) {
      return s.substring(0, pos) + s.substring(pos + 1);
   }
}

输出:

thi is Java

步骤三

对于两段格式化的教学大纲,比较两端教学大纲知识点的相似度与重复度。

目前的想法:

在提取出的教学知识点大纲上进行比较,因为我尝试教务系统中的数据结构和离散数学的教学大纲进行相似度计算,结果高达了92%。。。这里也是调用hanlp中的API来进行实现的。。。

现在的情况总结来说为以下几点:

  • 实现了比较两个中文字符串的相似度,但是还存在顺序的问题,这是之后要优化的内容。
  • 对于去除无意义词汇,我这里采用枚举,虽然很白痴,但是效果好像还行?如果之后要进行大量的其他词语的删除,可能需要寻找类似的算法或者调用API。
  • 比较两段格式化的教学大纲目前采用的是调用hanlp的文本相似度分析API,还在寻找其他算法进行优化。
  • 如果咱们最终不调用API,那么我目前需要调用API的功能就要在第一个功能的代码上进行改进实现了。

任务二

需要优化算法的部分已经在上文列出,目前就是这样,反正bug是de不完的hhh。

最后修改:2021 年 07 月 29 日 07 : 51 PM
如果觉得我的文章对你有用,请随意赞赏