65.9K
CodeProject 正在变化。 阅读更多。
Home

改进字符串相似度捕获

Thanh Dao
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.78/5 (77投票s)

2005 年 7 月 29 日

7分钟阅读

viewsIcon

446094

downloadIcon

6279

字符串相似性捕获的改进。该算法是用 C# 开发的。

引言

本文描述了一种捕获两个字符串（或单词）之间相似度的方法。字符串相似度是一个置信度分数，反映了两个字符串含义之间的关系，这两个字符串通常由多个单词或缩写组成。目前，在这个方法中，我更关注衡量两个字符串模式之间的关系，而不是单词的含义。

我在开发一个半自动匹配 XML Schema 的工具时实现了这个算法。

准备基础

在本文中，我实现了两个算法

  • Levenshtein 算法 [1]
  • Kuhn-Munkres 算法（也称为匈牙利方法）[2]

不深入“理论”，如果您想理解这些算法，请阅读算法书籍。其他关于它们的信息可以在

  1. Levenshtein
  2. 最优分配问题

问题

字符串相似性算法的开发是为了满足以下要求

  • 真实地反映词汇相似性 - 差异很小的字符串应被识别为相似。特别是，重要的子字符串重叠应表明字符串之间的高度相似性。
  • 对词序变化的鲁棒性 - 包含相同单词但顺序不同的两个字符串应被识别为相似。另一方面，如果一个字符串只是另一个字符串中字符的随机字母组合，那么它（通常）应该被识别为不相似。
  • 语言独立性 - 该算法不仅适用于英语，也适用于许多不同的语言。

解决方案

相似度计算分为三个步骤

  • 将每个字符串分割成一个令牌列表。
  • 使用字符串编辑距离算法计算令牌之间的相似度（扩展功能：使用 WordNet 库进行语义相似度测量）。
  • 计算两个令牌列表之间的相似度。

分词

字符串是由单词或缩写组成的列表，它可以遵循 Camel 或 Pascal 驼峰式命名法，而不带分隔符。例如：‘fileName’被分词为“file”和“Name”。这项工作由 tokeniser.cs 类完成。

计算两个单词之间的相似度

第一种方法使用编辑距离字符串匹配算法：Levenshtein。字符串编辑距离是将一个字符串转换为另一个字符串的总成本，使用一组具有关联成本的编辑规则。Levenshtein 距离是通过找到将一个字符串转换为另一个字符串的最便宜的方法获得的。转换是（单音节）插入、删除和替换的一步操作。在最简单版本中，替换的成本约为两个单位，除非源和目标相同，在这种情况下成本为零。插入和删除的成本是替换成本的一半。

此代码显示了该算法的动态实现

private int ComputeDistance (string s, string t)
{
    int n=s.Length;
    int m=t.Length;
    int[,] distance=new int[n + 1, m + 1]; // matrix
    int cost=0;
    if(n == 0) return m;
    if(m == 0) return n;
    //init1
    for(int i=0; i <= n; distance[i, 0]=i++);
    for(int j=0; j <= m; distance[0, j]=j++);
    //find min distance
    for(int i=1; i <= n; i++)
    {
        for(int j=1; j <= m;j++)
        {
            cost=(t.Substring(j - 1, 1) == 
                s.Substring(i - 1, 1) ? 0 : 1);
            distance[i,j]=Min3(distance[i - 1, j] + 1,
            distance[i, j - 1] + 1,
            distance[i - 1, j - 1] + cost);
        }
    }
    return distance[n, m];
}

相似度分数

我假设所有关系分数都在 [0, 1] 的范围内，这意味着如果分数达到最大值（等于 1），则这两个字符串绝对相似。

public float GetSimilarity(string string1, string string2) 
{ 
    float dis=ComputeDistance(string1, string2);
    float maxLen=string1.Length;
    if (maxLen < string2.Length)
    maxLen = string2.Length;
    if (maxLen == 0.0F)
    return 1.0F;
    else
    return 1.0F - dis/maxLen; 
}

两个令牌列表之间的相似度

将每个字符串分割成令牌列表后，我们通过计算这两个令牌列表的相似度来捕获两个字符串之间的相似度，这归结为 二分图匹配 问题。二分图匹配中的一个相关经典问题是 分配问题，即在给定所有非负成本 Cost[i,j] （工人 i 到工作 j 的评分）的情况下，找到最大化评分总和的最优工人-工作分配。

现在问题可以描述如下

给定一个图 G(V,E)，G 可以被划分为两个不相交的节点集 X（左）和 Y（右），使得每条边连接 X 中的一个节点和 Y 中的一个节点，并且每条边都有一个非负权重。

  • X 是第一个令牌列表的集合。
  • Y 是第二个令牌列表的集合。

E 是连接每个顶点对 (X ,Y) 的边集，连接 x1 到 y1 的每条边的权重是通过 x1 令牌和 y1 令牌的相似度计算的（使用 GetSimilarity 函数）。

Example: x1= “test”, y1=”tet”, e(x1, y1) = 0.75

任务是找到一个不包含节点重叠的边子集，该子集具有 最大总权重。两个字符串的相似度是通过匹配字符串的数量计算的。

初始化边的权重

GetSimilarity 函数的结果用于计算边的权重。

w(x,y) = GetSimilarity(token[x], token[y])

连接边以最大化总权重

我们使用匈牙利方法来解决二分图匹配问题的最大总权重。用于实现此算法的类是 MatchsMaker.cs。

未来改进

使用 WordNet 计算单词之间的语义相似度

以上部分允许我们获得字符串模式之间的相似度分数。然而，有时我们需要语义度量。这个问题导致我们寻找语义相似度。现在，我正在尝试使用 WordNet[1] 来计算英语词典中单词之间的相似度。

WordNet

WordNet 是一个在线的词汇数据库，提供了大量的英语词汇项。WordNet 被设计用来建立四种词性（POS）：名词、动词、形容词和副词之间的联系。WordNet 中最小的单位是 synset，它代表一个单词的特定含义。它包括单词、其解释以及其含义的同义词。一个单词在一个词性下的特定含义称为一个 sense。一个单词的每个 sense 都在不同的 synset 中。Synsets 等同于 senses = 包含具有同义含义的术语集的结构。每个 synset 都有一个 gloss 来定义它所代表的概念。例如，单词 night、nighttime 和 dark 构成一个 synset，其 gloss 如下：日落后日出前的黑暗时间。Synsets 通过明确的语义关系相互连接。其中一些关系（名词的 hypernymy、hyponymy 和动词的 hypernymy 和 troponymy）构成“种类”关系，而“部分”关系（名词的 holonymy 和 meronymy）则构成“部分”关系。例如，tree 是 plant 的一种，tree 是 plant 的 hyponym，plant 是 tree 的 hypernym。类似地，trunk 是 tree 的一部分，我们有 trunk 是 tree 的 meronym，tree 是 trunk 的 holonym。对于一个单词和一个词性，如果存在多个 sense，WordNet 会按照最常用的顺序排列。

基于 WordNet 及其 .NET API（由 Troy Simpson 提供），我使用同义词和上位词关系来捕获令牌的语义相似度。给定一对单词，一旦找到连接这两个单词的路径，我将根据两个因素确定它们的相似度：路径的长度和路径中涉及的 sense 的顺序。

为了找到单词之间的连接路径，我们使用广度优先搜索来检查它们是否是同义词。在 WordNet 中搜索单词之间的连接是一项昂贵的操作，因为搜索空间很大。我们定义了两个限制来减少计算时间。第一个是只考虑同义词关系（稍后将考虑上位词和下位词），因为穷尽所有关系成本太高。这个限制也在一些相关工作中被采用。另一个限制是限制搜索路径的长度。如果搜索者在有限长度内找不到已连接的路径，我们将停止搜索并将结果视为未找到路径。因此，这种情况应该用编辑距离代替。

相似度分数

由于考虑了同义词，我们首先使用以下公式计算单词的语义相似度分数

WordSim(s,t)=SenWeight(s)*SenWeight(t) / PathLength
  • 其中 s 和 t：表示正在比较的源词和目标词。
  • SenseWeight：表示根据该 sense 的顺序和总 sense 计数计算出的权重。
  • PathLength：表示从 s 到 t 的连接路径的长度。

（这项工作是一个实验，在此版本中不可用，即将发布。）

使用代码

将相似度项目添加到您的工作区。创建一个如下所示的方法

public Test()
{
   string s1="The code project's article";
   string s2="Article of The CodeProject";
   MatchsMaker match=new MatchsMaker(s1, s2) ;
   Console.WriteLine(match.Score) ;
}

其中 s1, s2 是用于捕获相似度的两个字符串。match.Score 是两个字符串的相似度分数。在此示例中，分数为 0.94。

参考文献

© . All rights reserved.