`
ghost_face
  • 浏览: 54295 次
社区版块
存档分类
最新评论

计算字符串相似度【转载】

阅读更多

---------以下部分转载自博客http://www.cnblogs.com/grenet/archive/2010/06/04/1751147.html---------------- 

在“文本比较算法Ⅰ——LD算法”中,介绍了编辑距离的计算。

  在“文本比较算法Ⅱ——Needleman/Wunsch算法”中,介绍了最长公共子串的计算。

  在给定的字符串A和字符串B,LD(A,B)表示编辑距离,LCS(A,B)表示最长公共子串的长度。

  如何来度量它们之间的相似度呢?

  不妨设S(A,B)来表示字符串A和字符串B的相似度。那么,比较合理的相似度应该满足下列性质。

  性质一:0≤S(A,B)≤100%,0表示完全不相似,100%表示完全相等

  性质二:S(A,B)=S(B,A)

  目前,网上介绍的各种相似度的计算,都有各自的不尽合理的地方。

  计算公式一:S(A,B)=1/(LD(A,B)+1)

    能完美的满足性质二。

    当LD(A,B)=0时,S(A,B)=100%,不过无论LD(A,B)取任何值,S(A,B)>0,不能满足性质一。

 

  计算公式二:S(A,B)=1-LD(A,B)/Len(A)

    当Len(B)>Len(A)时,S(A,B)<0。不满足性质一。

    有人会说,当S(A,B)<0时,强制指定S(A,B)=0就解决问题了。

    问题是,S(A,B)=1-LD(A,B)/Len(A),而S(B,A)=1-LD(B,A)/Len(B)。当Len(A)≠Len(B)时,S(A,B)≠S(B,A)。不满足性质二

    还有一个例子可以说明问题

    A="BC",B="CD",C="EF"

    S(A,B)=1-LD(A,B)/Len(A)=1-2/2=0

    S(A,C)=1-LD(A,C)/Len(A)=1-2/2=0

    A和B的相似度与A和C的相似度是一样的。不过很明显的是B比C更接近A

 

  计算公式三:S(A,B)=LCS(A,B)/Len(A)

    这个公式能完美的满足的性质一

    不过当Len(A)≠Len(B)时,S(A,B)≠S(B,A)。不满足性质二

    用一个例子说明问题

    A="BC",B="BCD",C="BCEF"

    S(A,B)=LCS(A,B)/Len(A)=2/2=100%

    S(A,C)=LCS(A,C)/Len(A)=2/2=100%

    A和B的相似度与A和C的相似度是一样的。不过很明显的是B比C更接近A

 

  上面是网上能找到的三个计算公式,从上面的分析来看都有各自的局限性。

 

  我们看一个例子:

  A=GGATCGA,B=GAATTCAGTTA,LD(A,B)=5,LCS(A,B)=6

  他们的匹配为:

    A:GGA_TC_G__A

    B:GAATTCAGTTA

  可以看出上面蓝色的部分表示的是LCS部分,黑色表示的是LD部分。

  因此,给出一个新的公式

  S(A,B)=LCS(A,B)/(LD(A,B)+LCS(A,B))

  这个公式能解决上述三个公式的种种不足。

  而LD(A,B)+LCS(A,B)表示两个字符串A、B的最佳匹配字串的长度。这个是唯一的。

  还有注意的是LD(A,B)+LCS(A,B)和Max(Len(A),Len(B))这两个并不完全相等。

---------以上部分转载自博客http://www.cnblogs.com/grenet/archive/2010/06/04/1751147.html----------------

实现代码如下:

package algorithm;

import java.io.IOException;

/**
 * Levenshtein Distance 算法实现
 * 可以使用的地方:DNA分析   拼字检查   语音辨识   抄袭侦测
 * 相似度公式:S(A,B)=LCS(A,B)/(LD(A,B)+LCS(A,B))
 * LCS为最长公共子串长度,LD是编辑距离
 */
public class Levenshtein {

    public static void main(String[] args) throws IOException {
        //要比较的两个字符串
        String str1 = "【性教育】当孩子能听懂言语时,家长应把性教育贯穿在日常生活中,如在洗澡、着装、修整发型及玩具选择等方面要有明确的性别区分。还可通过书报、画册、影视、讲故事等进行引导,使孩子对性别产生一种自然的认识,从而使他们接受、认识生命本质,使性自认得以完成。";
        String str2 = "【对孩子进行适当的性教育】当孩子能听懂言语时,家长应把性教育贯穿在日常生活中,如在洗澡、着装、修整发型及玩具选择等方面要有明确的性别区分。还可通过书报、画册、影视、讲故事等进行引导,使孩子对性别产生一种自然的认识,从而使他们接受、认识生命本质,使性自认得以完成。";
        System.out.println(levenshtein(str1, str2));
    }

    /**
     *   DNA分析   拼字检查   语音辨识   抄袭侦测
     * <p/>
     * 加入了LCS
     */
    public static float levenshtein(String str1, String str2) {
        //计算两个字符串的长度。
        int len1 = str1.length();
        int len2 = str2.length();
        //建立上面说的数组,比字符长度大一个空间
        /**
         * 若ai=bj,则LD(i,j)=LD(i-1,j-1)
         * 若ai≠bj,则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1
         */
        int[][] dif = new int[len1 + 1][len2 + 1];
        /**
         *   若ai=bj,则LCS(i,j)=LCS(i-1,j-1)+1
         * 若ai≠bj,则LCS(i,j)=Max(LCS(i-1,j-1),LCS(i-1,j),LCS(i,j-1))
         */
        int[][] lcs = new int[len1 + 1][len2 + 1];
        //赋初值,步骤B。
        for (int a = 0; a <= len1; a++) {
            dif[a][0] = a;
            lcs[a][0] = 0;
        }
        for (int a = 0; a <= len2; a++) {
            dif[0][a] = a;
            lcs[0][a] = 0;
        }
        //计算两个字符是否一样,计算左上的值
        int temp;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    temp = 0;
                } else {
                    temp = 1;
                }
                //取三个值中最小的
                dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,
                        dif[i - 1][j] + 1);
                if (temp == 0)
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                else
                    lcs[i][j] = max(lcs[i - 1][j - 1], lcs[i][j - 1], lcs[i - 1][j]);
            }
        }
        //取数组右下角的值,同样不同位置代表不同字符串的比较
//        System.out.println("差异步骤:" + dif[len1][len2]);
        //计算相似度
        /**
         *   这个计算公式有弊端,假设A="BC",B="CD",C="EF"
         S(A,B)=1-LD(A,B)/Max(Len(A),Len(B))=1-2/2=0
         S(A,C)=1-LD(A,C)/Max(Len(A),Len(C))=1-2/2=0
         A和B的相似度与A和C的相似度是一样的。不过很明显的是B比C更接近A
         */
//        float similarity = 1 - (float) dif[len1][len2] / Math.max(str1.length(), str2.length());
        float similarity = (float) lcs[len1][len2] / (dif[len1][len2] + lcs[len1][len2]);

        return similarity;
    }

    //得到最小值
    private static int min(int... is) {
        int min = Integer.MAX_VALUE;
        for (int i : is) {
            if (min > i) {
                min = i;
            }
        }
        return min;
    }

    //得到最大值
    private static int max(int... is) {
        int max = Integer.MIN_VALUE;
        for (int i : is) {
            if (max < i) {
                max = i;
            }
        }
        return max;
    }

}

 

0
0
分享到:
评论

相关推荐

    字符串相似度算法 字符串相似度算法 字符串相似度算法

    字符串相似度算法 字符串相似度算法是一种衡量两个字符串之间相似度的方法,广泛应用于自然语言处理、数据挖掘、机器学习等领域。在本文中,我们将讨论一种常用的字符串相似度算法:Levenshtein Distance。 什么是...

    mysql 计算字符串相似度

    ### MySQL 计算字符串相似度 #### 背景与需求 在许多应用场景中,我们需要对两个字符串进行相似度比较,比如搜索引擎中的关键词匹配、文本分析中的近义词识别等。MySQL 提供了多种方法来实现字符串相似度的计算,...

    java 计算字符串相似度

    java 计算字符串相似度

    Delphi计算字符串的相似度

    在编程领域,字符串的相似度计算是一个常见的任务,特别是在文本处理、信息检索和自然语言处理中。本篇文章将深入探讨如何在Delphi环境下计算字符串的相似度,以及相关的技术细节。 Delphi是一种基于Object Pascal...

    字符串相似度比较算法

    在计算机科学领域,字符串相似度比较算法是一种用于评估两个字符串之间相似程度的技术。这些算法广泛应用于文本处理、信息检索、生物信息学等多个领域。当我们要判断两个字符串是否含有相同或相近的信息时,这类算法...

    LD的两字符串相似度计算.zip

    在IT领域,字符串相似度计算是一项基础且重要的任务,它广泛应用于信息检索、文本匹配、数据清洗等多个场景。Levenshtein Distance(简称LD),又称编辑距离,是衡量两个字符串相似度的一种方法。这个概念由俄国科学...

    delphi计算两个字符串相似度源码 Levenshtein算法版

    《使用Delphi实现Levenshtein算法:计算字符串相似度》 在信息技术领域,字符串处理是常见的任务之一,其中计算两个字符串的相似度是尤为重要的一个环节。Levenshtein算法,也称为编辑距离算法,就是用于衡量两个...

    DELPHI Levenshtein算法 字符串相似度计算(附源码)

    开发者可以通过查看源代码学习如何在DELPHI中实现这个算法,也可以直接使用提供的可执行文件进行快速的字符串相似度计算。在实际应用中,这样的工具对于文本分析、搜索引擎优化、拼写检查等领域都具有很高的价值。

    字符串相似度算法

    这个小例子旨在介绍如何通过计算字符串间的相似度来进行模糊匹配。我们将探讨几种常见的字符串相似度算法,理解它们的原理,并讨论它们在实际问题中的应用。 1. **Levenshtein距离**:由俄国科学家Levenshtein提出...

    strutil:Golang度量标准,用于计算字符串相似度和其他字符串实用程序功能

    Strutil strutil提供了用于计算字符串相似度的字符串度量标准以及其他字符串实用程序功能。 完整文档可在以下找到: : 。安装 go get github.com/adrg/strutil字符串指标杰罗·温克勒史密斯·沃特曼·高图索伦森-...

    DELPHI 计算两个字符串相似度 LCS算法(附源代码)

    在IT行业中,字符串的相似度计算是一个常见的任务,特别是在文本处理、信息检索和自然语言处理等领域。本篇文章将深入探讨如何使用DELPHI编程语言实现LCS(最长公共子序列)算法来衡量两个字符串的相似度。LCS算法是...

    字符串相似度比对JAVA

    就是一个简单的字符串相似度比较的方法,暂时还不知道有没有更好的方法,大家先看看,有更好的希望分享一下

    字符串相似度比较

    3. **余弦相似度**:通过计算两个字符串的向量表示之间的夹角余弦值来评估相似性,适用于较长文本的比较。 4. **Jaro-Winkler距离**:特别适合名字和地址等短字符串的比较,考虑了字符的顺序和位置。 5. **Hamming...

    字符串相似度检测程序

    关于字符串相似度检测的一个很好用的C代码

    两个字符串相似度匹配

    1. **Levenshtein距离**:这是一种编辑距离算法,通过计算将一个字符串转换为另一个字符串所需的最少单字符编辑(插入、删除或替换)次数来衡量相似度。 2. **Jaccard相似系数**:该方法是基于集合的交集和并集来...

    字符串相似度比较T-2021-7-1.rar

    字符串相似度比较的目标是量化两个字符串之间的相似性,这通常通过计算它们的差异程度来实现。常见的方法有以下几种: 1. **编辑距离(Levenshtein Distance)**:编辑距离是指将一个字符串转换成另一个字符串所需...

    一个使用 Python 实现不同字符串相似度和距离度量的库_python_代码_下载

    一个实现不同字符串相似度和距离度量的库。目前实现了十几种算法(包括 Levenshtein 编辑距离和兄弟、Jaro-Winkler、最长公共子序列、余弦相似度等)。查看下面的汇总表以获取完整列表... python字符串相似度 下载 ...

    比较两个字符串之间相似度

    用途:可用于论文抄袭检测、DNA等。...算法实现思路:通过对一个字符串插入、删除、替换转变成另一个字符串所需要的步骤称为距离,计算两个字符串之间的距离,从而可以得到两个字符串之间的相似度。

    计算字符串相似度(支持中英文,编辑距离算法,余弦,繁体转简体)

    在IT领域,字符串相似度计算是一项重要的技术,广泛应用于文本分析、信息检索、自然语言处理等多个方面。本项目提供了一个简单易用的demo,支持中英文字符串的相似度比较,采用了编辑距离算法和余弦相似度这两种经典...

    C#中文文本匹配,字符串匹配,中文词语匹配,计算2个句子相似度

    C#中文文本匹配,字符串匹配,中文词语匹配,计算2个句子相似度 中文匹配C#中文文本匹配,字符串匹配,中文词语匹配,计算2个句子相似度 C#中文文本匹配,字符串匹配,中文词语匹配,计算多个句子相似度 C#中文文本...

Global site tag (gtag.js) - Google Analytics