【算法】编辑距离相似度算法
Levenshtein.java
/**
* 算法原理
* 编辑距离
* Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明，用他的名字命名。不会拼读，可以叫它edit distance（编辑距离）。
* 原理很简单，就是返回将第一个字符串转换(删除、插入、替换)成第二个字符串的编辑次数。次数越少，意味着字符串相似度越高
* Spell checking(拼写检查)
* Speech recognition(语句识别)
* DNA analysis(DNA分析)
* Plagiarism detection(抄袭检测)
* LD用m*n的矩阵存储距离值。算法大概过程：
* @author Administrator
*
*/
public class Levenshtein
{
private int compare(String str, String target)
{
int d[][]; // 矩阵
int n = str.length();
int m = target.length();
int i; // 遍历str的
int j; // 遍历target的
char ch1; // str的
char ch2; // target的
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++)
{ // 遍历str
ch1 = str.charAt(i - 1);
// 去匹配target
for (j = 1; j <= m; j++)
{
ch2 = target.charAt(j - 1);
if (ch1 == ch2 || ch1 == ch2+32 || ch1+32 == ch2)
{
temp = 0;
} else
{
temp = 1;
}
// System.out.println(ch1+" "+ch2+" "+temp);
// 左边+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 int min(int one, int two, int three)
{
return (one = one < two ? one : two) < three ? one : three;
}
/**
* 获取两字符串的相似度
*/
public float getSimilarityRatio(String str, String target)
{
// System.out.println("-------------------------compare------------------------------------");
// System.out.println("str1:"+str);
// System.out.println("str2:"+target);
int len=compare(str, target);
// System.out.println("字符串距离:"+len);
if(Math.max(str.length(), target.length())==0){
return 1;
}
return 1 - (float) len / Math.max(str.length(), target.length());
}
/**
* 获取两字符串的相似度 按最短字符串比较
*/
public float getSimilarityRatioMin(String str, String target)
{
System.out.println(str+" "+target);
if(Math.min(str.length(), target.length())==0){
return 1;
}
int len=compare(str, target);
// System.out.println("字符串距离:"+len);
return 1 - (float) len / Math.min(str.length(), target.length());
}
public static void main(String[] args)
{
Levenshtein lt = new Levenshtein();
String str = "中华人民共和国人民币";
String target = "中华人民共和国";
System.out.println("similarityRatio=" + lt.getSimilarityRatio(str, target));
}
}QuestSimilarityUtil.java
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class QuestSimilarityUtil {
public static String clearHtmlTag(String str,boolean sort) {
if (str != null && str.length() > 0) {
str=clearWiteSpace(str);
if(sort){
str=reSortString(str);
}
return str;
}
return str;
}
public static String clearWiteSpace(String str) {
if (str != null && str.length() > 0) {
str = str.replaceAll("\\s*", "");// 去掉所有空格,包括首尾,中间
str = str.replaceAll("\\u00A0", "");// 中文空格 对应页面中的： ；
str = str.replaceAll("[\\pP\\p{Punct}]", "");// 清除所有符号,只留下字母 数字 汉字 共3类.
return str;
}
return str;
}
/**
* 字符串无需
* @param str
* @return
*/
public static String reSortString(String str) {
if (str == null || str.length() == 0) {
return str;
}
char[] s1 = str.toCharArray();
for (int i = 0; i < s1.length; i++) {
for (int j = 0; j < i; j++) {
if (s1[i] < s1[j]) {
char temp = s1[i];
s1[i] = s1[j];
s1[j] = temp;
}
}
}
// 再次将字符数组转换为字符串，也可以直接利用String.valueOf(s1)转换
String st = new String(s1);
return st;
}
//相似度，字符串进行无序比对
public static float sim(String str1, String str2) {
try{
str1 = clearHtmlTag(str1,true);
str2 = clearHtmlTag(str2,true);
// System.out.println(str1);
// System.out.println(str2);
Levenshtein lt = new Levenshtein();
float sm = lt.getSimilarityRatio(str1, str2);
return sm;
}catch (Exception e){
e.printStackTrace();
}
return 0f;
}
public static float sim3(String str1, String str2) {
try{
str1 = clearHtmlTag(str1,true);
str2 = clearHtmlTag(str2,true);
// System.out.println(str1);
// System.out.println(str2);
Levenshtein lt = new Levenshtein();
float sm = lt.getSimilarityRatioMin(str1, str2);
return sm;
}catch (Exception e){
e.printStackTrace();
}
return 0f;
}
//相似度，字符串进行有序比对
public static float sim2(String str1, String str2) {
try{
str1 = clearHtmlTag(str1,false);
str2 = clearHtmlTag(str2,false);
// System.out.println(str1);
// System.out.println(str2);
Levenshtein lt = new Levenshtein();
float sm = lt.getSimilarityRatio(str1, str2);
return sm;
}catch (Exception e){
e.printStackTrace();
}
return 0f;
}
public static boolean isLaji(String str){
String reg=".*([0-9a-zA-Z\u4e00-\u9fa5]+).*";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(str);
return m.find();
}
public static void main(String[] args) {
// clearWiteSpace("A.蔗糖 B.食盐 C.小苏打 D.食醋 ");
String str1 = "11.【中考·牡丹江】某种商品的进价为每件100元，商 16.【中考·贵阳】某文具店最近有A，B两款毕业纪念 场按进价提高50%后标价，为增加销量，准备打折销 册比较畅销，近两周的销售情况是第一周A款销售 售，但要保证利润率不低于20%，则至多可以打 数量是15本，B款销售数量是10本，销售总价是 _折. 230元：第二周A款销售数量是20本，B款销售数量 12.若关于x的一元一次不等式组 \\left\\{\\begin{array}{l}3-2x>2，\\\\x-a>0\\end{array}\\right. 是10本，销售总价是280元. 有3个整 (1)求A，B两款毕业纪念册的销售单价； 数解，则a的取值范围是. (2)若某班准备用不超过529元购买这两种款式的毕业 13.若x为有理数，则[x]表示不大于x的最大整数，例 纪念册共60本，求最多能够买多少本A款毕业纪 如 [1.6]=1，[π]=3，[-2.82]=-3 等. [x]+1 念册. 是大于x的最小整数，对任意的有理数x都满足不 等式组 [x]≤x<[x]+1. 利用这个不等式组，求出 满足 [x]=2x-1 1的所有解，其所有解为. 三、解答题 14.解下列不等式(组).并把它们的解集在数轴上表示 出来. \\left(1\\right)\\frac{2x-1}{3}\\le\\frac{3x+2}{4}-1； 17.【中考·福建】某工厂为贯彻落实“绿水青山就是 金山银山”的发展理念，投资组建了日废水处理量为 m吨的废水处理车间，对该厂工业废水进行无害化 处理.但随着工厂生产规模的扩大，该车间经常无法 完成当天工业废水的处理任务，需要将超出日废水 (2)【中考·江西】 \\left\\{\\begin{array}{l}2\\left(x+1\\right)>x，\\\\1-2x\\ge\\frac{x+7}{2}.\\end{array}\\right. 处理量的废水交给第三方企业处理.已知该车间处 理废水，每天需固定成本30元，并且每处理一吨废 水还需其他费用8元；将废水交给第三方企业处理， 每吨需支付12元.根据记录，5月21日，该厂产生工 业废水35吨，共花费废水处理费370元. (1)求该车间的日废水处理量 m； 3x<5x+6， (2)为实现可持续发展，走绿色发展之路，工厂合理控制 15.【中考·遂宁】解不等式组 \\left\\{\\begin{array}{l}\\frac{x+1}{6}+1\\le0，\\\\\\frac{x+1}{6}\\ge\\frac{x-1}{2}，\\end{array}\\right. 把它的解 了生产规模，使得每天废水处理的平均费用不超过 10元/吨，试计算该厂一天产生的工业废水量的 集在数轴上表示出来，并写出其整数解. 范围. 期末提分练案 条案/ 111 本页答案及点拨见145页\n";
String str2 = "\n" +
"第5课时一元一次不等式 11.【中考·牡丹江】某种商品的进价 场按进价提高50%后标价，为增加销 一考点梳理! 售，但要保证利润率不低于20% 1.不等式的两边都加上(或都减去) 3-2 同一个教或同一个整式，不等号好 12.若关于x的一元一次不等式组 x 不等式 方向不变 不等式 不等式的解 2.不等式的两边都乘从(或都除从) 数解，则的取值范围是. 的性质 不等式的解集 同一个正数，不等号的方向不变 概念 13.若x为有理数，则[ [x] ]表示不大于x的 一元一次不等式 3.不等式的两边都乘以(或都除以 同一个数，不等号的方向改变 如[ [1.6]=1，[π]=3，[-2.82]=-3 一元-次不等式组 一元一次不等式姐的解集 元一次 去分母 是大于x的最小整数，对任意的有理数 等式组[ x]≤x<[x]+1. .利用这个不等 每个不等式的解集，监 不等式 解一元一 去括号 D利用教轴找出解集的 次不等式 移项 满足 [x]=2x-1 的所有解，其所有解为 公共部分 合并同类项 解一元一次 三、解答题 不等式组 系数化为! 同大取大，同小取小 14.解下列不等式(组).并把它们的解集在券 大小小大中间找，大大 一 小小找不列 用 )一元一次不等式 出来. 解决实际间题 \\left(1\\right)\\frac{2x-1}{3}\\le\\frac{3x+2}{4}-1； 达标训练 一、选择题 1.已知四个有理数a，b，c，d，若 a>b，c>d， 省30元，直到她至少存有1080元，设x个月后小丽 A.a+c>b+d B.a-c>b-d 有1080元，则可列计算月数的不等式为 为() A.30x+750>1080 C.ac>bd D.\\frac{a}{c}>\\frac{b}{d} C.30x-750≤1080 B.30x~750≥1080 D.30x+750≥1080 2.【中考·襄阳】不等式组 且 2x<x+4， 7.【中考·德州】不等式组 5x+33(x-1)， 5x+3>3(x-1)， (2)【中考·江 {3+x≥3x+9\\right. 的解集在数轴 x-1\\le7-\\frac{3}{2}x 的所有 则\\left\\{\\begin{array}{l}2\\left(x+1\\right)>x，\\\\1-2x\\ge\\frac{x+7}{2}.\\end{array}\\right. 上用阴影表示正确的是 () 非负整数解的和是 B. A.10 30 C.6 D.0 D. \\overrightarrow{0} \\frac{1}{-30} 8.【中考·呼和浩特】若不等t-1≤2~x的解集 \\frac{2x+5}{3}-1\\le2-x 3.【中考·南充】关于x的不等式 2x+a≤1 只有2个 中x的每一个值，都能使关于的不等式3(x-1)+ 5>5x+2(m+x) 3(x-1)+ 成立，则m的取值范围是 () 3x<5x+6， 正整数解，则α的取值范围为 15.【中考·遂宁】解不等式组 且 \\left\\{\\begin{array}{l}3x<5x+6，\\\\\\frac{x+1}{6}\\ge\\frac{x-1}{2}，\\end{array}\\right. 1把它 A.-5<a<-3 B.-5≤a<-3 A.m>-\\frac{3}{5} B.m<-\\frac{1}{5} C.-5<a≤-3 D.-5≤a≤-3 集在数轴上表示 写出其整数解. 4.【中考·株洲】下列不等式中与不等式 5x>8+2x 组 C.m<-\\frac{3}{5} D.m>-\\frac{1}{5} 成的不等式组的解集为 \\frac{8}{3}<x<5 的是 () 二、填空题 A.x+5<0 B.2x>10 9.【中考·达州】如图所示，点Ｃ位于点A.B之间(不 1-2x， C.3x-15<0 D.-x-5>0 与A.B重合)，点Ｃ表示1-2x，则x的取值范围 ^{∘}， x 是 5.若代数式 \\frac{1}{4}a 的值不大于 \\frac{1}{2}a+1 的值，则。应满足 () (第9题) A.a≥-4 B.a≤-4 C.a>4 4 D.4 4 >3， 6.小丽同学准备用自己节省的零花钱购买一台学生平 10.【中考·温州】不等式组 \\frac{x-2}{2}\\le4 4的解集为 板电脑，她已存有750元，并计划从本月起每个月节 七年级数学·下(HS版) 110 本页答及点拔T45页\n";
System.out.println("sim=" + sim(str1, str2));
System.out.println(isLaji("-"));
}
}