不是莱文斯坦距离
4.95/5 (22投票s)
“文本亲和度”：类似人类的相似文本排名
引言
最后，我需要读取服务报告，并将其中出现的技术术语映射到数据库中已知的术语（如果你想详细了解，是为了计费目的）。
我构建了一个应用程序，用于选择一个“参考字符串”（来自服务报告），并从数据库中获取大量“假设”——按与参考字符串的相似度进行排序。
莱文斯坦（Levenshtein）算法在排序方面的表现让我很失望。
幸运的是，在晚上，我得到了一个灵感，如何以完全不同的方式定义文本相似度——我将其命名为“TextAffinity”。
为了演示，我在这里重新构建了上述应用程序，使用大约2000首歌曲标题作为假设数据（而不是技术术语）。
查看一些结果
在左侧，您可以看到莱文斯坦算法的结果：只有一个假设似乎与查询的参考字符串相关（以人类理解而言）。
而右侧的TextAffinity显示了数据库中所有21个包含匹配词的假设。
莱文斯坦算法有什么问题？
莱文斯坦算法假设了一小组原子性的char操作（insert、replace、delete），并计算如何以最小的步骤数应用它们，将一个假设转换成一个参考string。
CodeProject上有很多关于不同实现的提示——我推荐这个，因为它的图形演示更容易理解这个（确实很棘手的！）算法。
但是，在char上应用原子操作并不是人类大脑通常识别文本“相似”的方式。
人类观察匹配的char组——特别是**_单词_**（空格之间的char组）。
TextAffinity - 概念定义与实现
TextAffinity将连续匹配的char视为特定长度的一个匹配。
将参考字符串与假设进行比较会产生几个匹配长度和一个“NoMatchChars”值：即参考字符串和假设中不匹配字符的数量。
一个TextAffinity对象存储这些信息。
将几个假设与同一个参考字符串进行比较会产生几个TextAffinity对象，而挑战在于根据其重要性对它们进行排序。
以下是两个TextAffinity对象的比较方式
- 从大到小遍历匹配长度并进行比较——在第一次出现差异时终止——较大的获胜。
- 如果一个TextAffinity的匹配长度用完——另一个获胜。
- 如果两者在同一迭代中都用完，那么较小的NoMatchChars获胜。
优化
我们可以简单地将负的NoMatchChars附加到MatchLengths中。这样，3)就是多余的，因为它在之前的步骤中已经完成。
注意：算法1) + 2) 不过是数学中所谓的**“词典序”**（<-请点击链接）
此外：框架中已经有一个高性能的词典序比较方法：static string.CompareOrdinal(x, y)。
因此，现在的挑战是将我们连接起来的MatchLengths和NoMatchChars转换为string，同时尊重NoMatchChars的负号值。
这并不复杂：一个偏移量解决了有符号值的问题，并且Convert类可以将char <-> int进行转换
/// <summary> implements IComparable<TextAffinity> - to be used as Sortkey </summary>
public class TextAffinity : IComparable<TextAffinity> {
private readonly string _SortKey; // MatchLengths and negative count of no-matching-chars, all encoded whithin a string
private const int _Offs = 32767; // offset enables numb-char-conversion for negative numbs too.
private static int Char2Numb(char c) { return Convert.ToInt32(c) - _Offs; }
private static char Numb2Char(int n) { return Convert.ToChar(_Offs + n); }
public TextAffinity(IEnumerable<int> orderedMatchLengths, int noMachChars) {
var numbs = orderedMatchLengths.Concat(new int[] { -noMachChars }).ToArray(); // append reciprocal noMatchChars
if (noMachChars > _Offs) throw new ArgumentException("must <= " + _Offs, "noMachChars");
if (numbs.Any(n => n > _Offs)) throw new ArgumentException("all of them must <= " + _Offs, "orderedMatchLengths");
_SortKey = new string(numbs.Select(Numb2Char).ToArray()); // convert to String
}
public int CompareTo(TextAffinity other) { return string.CompareOrdinal(_SortKey, other._SortKey); }
public override string ToString() { return string.Join(" ", _SortKey.Select(Char2Numb)); }
}
注意：_SortKey中的char不可读——可能地球上没有哪种字体能以有意义的方式显示它们。但它是一个可排序的string。
由于TextAffinity实现了IComparable<TextAffinity>，因此它可以很容易地用于排序
// string reference, string[] hypotheses
var afffac = new TextAffinityFactory(reference);
var rankedHypotheses = from h in hypotheses orderby afffac.GetAffinity(h) descending select h;
（这还只是简单部分。）
找出所有匹配
给定参考字符串：" daring end "，假设字符串：" dark sprints end "
首先，我尝试了一种天真、排列组合的方式：构建两者的所有可能char组，并查看哪些与哪些匹配。结果很好——但是性能……呃……不好。
但另一个晚上我回想起莱文斯坦算法是如何计算其结果的：即使用一个矩阵，其中列代表假设，行代表参考。
在这样的矩阵中，我标记出行和列的匹配项
显而易见，匹配的char组以对角线下降的形式出现。我还假设输入找到的匹配的长度。
请注意，位于(0/0)的匹配char ' '并未与(1/1)到(3/3)的位置相连接。
这种异常规则是，只有当匹配的另一端也是' '时，' '才加入匹配。这个粗略的规则将单词匹配长度增加2分，这导致单词匹配比其他char匹配组具有更强的偏好。
看：因为' end '作为一个完整的单词匹配，所以它算作5，而'dar'只算作3。
我再次创建了一个小类，这次用于存储Match信息，即Match的Start（X / Y）及其Length
private class Match : IComparable<Match> {
public int Y, X;
public int Length = 1;
public Match(int y, int x) { this.Y = y; this.X = x; }
/// <summary> defines order by Length descending </summary>
public int CompareTo(Match other) { return other.Length - Length; }
}
它也是IComparable，因为根据TextAffinity的定义，按MatchLength排序至关重要。
看看填充我的矩阵的循环
Match[,] matchMatrix = new Match[yLength, xLength];
for (var x = 0; x < xLength; x++) if (xChars[x] == ' ') AddNewMatch(0, x); // init top row
for (var y = 0; y < yLength; y++) if (yChars[y] == ' ') AddNewMatch(y, 0); // init left column
for (int y = 1; y < yLength; y++) { // inner matrix
var cy = yChars[y];
for (int x = 1; x < xLength; x++) {
if (xChars[x] == cy) {
var mtPrev = matchMatrix[y - 1, x - 1];
if (mtPrev==null) AddNewMatch(y, x);
else { // lengthen mtPrev
mtPrev.Length += 1;
matchMatrix[y, x] = mtPrev;
}
}
}
}
你看：我的matchMatrix不是一个简单的int矩阵，而是一个Match对象的矩阵！
当在位置x/y处发生字符匹配时（第7行），我尝试从左上角的相邻单元格获取前一个匹配，延长它，并将其也分配给当前单元格。
这反映了我在上面将Match长度输入到网格中所做的工作。
否则——未检测到之前的Match——AddNewMatch()方法会创建一个新的Match，将其分配给矩阵以及一个Match列表（此处未显示）。
接下来我将对这个Match列表进行排序，检查其条目并对它们进行一些复杂的操作。
消除重叠匹配
上图显示了所有可能的匹配，但其中一些与其他匹配冲突。例如，第3行中的“r”不能同时匹配第3列和第8列！
规则仍然很简单——代码很棘手。规则是：优先选择更长的匹配；从它们开始。
让我们试着用颜色来阐明这一点
你能看到吗？我从最长的对角线到最短的对角线遍历，并投射出它们的水平和垂直“毒性阴影”，其他匹配无法存在于这些阴影中。
只剩下4个不同长度的匹配——它们排序后的匹配长度是：(5 3 2 1)
然后回想一下“单词偏好异常”，它阻止空格连接非单词的匹配。如果没有这个异常，(0/0)位置的匹配字符就会连接，我们将得到总的匹配长度(5 4 2)。
现在——想象一下，除了给定的" dark sprints end "，还有一个假设：" Spring enemy "。
在给定的参考字符串：" daring end "，但没有单词偏好规则的情况下，" Spring enemy "将包含匹配的char组"ring en"，并且将（包括周围的空格）导致(7 1 1)——这将大大胜过(5 4 2)- (" dark sprints end ")。
但人类认为" dark sprints end "比" Spring enemy "与" daring end "更相似——对吗？
所以坚持使用单词异常，它使" dark sprints end "(5 3 2 1)胜过" Spring enemy "(4 2 1 1 1)
但首先是消除重叠的代码
int[] yMatchMask = new int[yLength];
int[] xMatchMask = new int[xLength];
matches.Sort();
for (var id = 0; id <= matches.Count - 1; id++) {
var match = matches[id];
for (var i = 0; i <= match.Length - 1; i++) {
var y = match.Y + i;
var x = match.X + i;
if (yMatchMask[y] == 0 && xMatchMask[x] == 0) { // both matchMasks must be free at y/x
yMatchMask[y] = id + 1;
xMatchMask[x] = id + 1;
}
}
}
对于y方向和x方向，我创建了一个int数组作为一种“掩码”。
然后，循环遍历降序排列的matches（如上所述），并将匹配的id输入到position.X处的xMask中，并将id输入到position.Y处的yMask中——但仅当两个掩码在该位置尚未被占用时。
由于较长的匹配先处理，较短的匹配会被剔除。
从xMatchMask派生noMatchChars和matchLengths
例如：4 2 2 2 0 0 0 0 0 3 3 0 0 1 1 1 1 1是网格图像中所示的参考/假设样本的最终xMatchMask。
请注意，ids值按匹配长度降序排列，而位置则反映了矩阵列上的匹配位置。
var matchIds = xMatchMask.Where(id => id > 0).ToArray();
var noMatchChars = xLength + yLength - matchIds.Length * 2; // NoMatchChars sums x-Nomatches and y-Nomatches
var matchLengths = from grp in matchIds.GroupBy(i => i) let length = grp.Count() where length > 1 orderby length descending select length;
return new TextAffinity(matchLengths, noMatchChars);
- 首先从matchMask中选择
matchIds - 然后计算
noMatchChars - 如果
matchIds组包含多个元素，则matchLengths是这些组的长度。 - 将这些信息传递给
TextAffinity构造函数——我们已经看到，它是如何构建一个Sortkey-string以实现最佳比较性能的。
单词偏好异常 - 代码回顾
抱歉，在“找出所有匹配”部分，我给出了一个非常简化的代码——没有那个烦人的异常。
现在，这里是它_真正_的运作方式——完整的故事
/// <summary> the evaluated Affinity is IComparable - u can use it in orderby-Sortations </summary>
public TextAffinity GetAffinity(string hypothesis) {
var xChars = MakeCharArray(hypothesis);
var yChars = Chars;
var yLength = yChars.Length;
var xLength = xChars.Length;
Match[,] matchMatrix = new Match[yLength, xLength];
List<Match> matches = new List<Match>();
Action<int, int> AddNewMatch = (y, x) => {
var mt = new Match(y, x);
matches.Add(mt);
matchMatrix[y, x] = mt;
};
Action<Match> CutWordStartFromMatch = mt => {
for (var i = mt.Length; i-- > 0; ) if (xChars[mt.X + i] == ' ') {
if (++i == mt.Length) return; // i is the index after ' '
//cut is done by inserting a new, shorter match (and update all dependant data)
var mt2 = new Match(mt.Y + i, mt.X + i) { Length = mt.Length - i };
matches.Add(mt2);
mt.Length = i;
for (i = mt2.Length; i-- > 0; ) matchMatrix[mt2.Y + i, mt2.X + i] = mt2;
return;
}
};
// mark the matrix:
for (var x = 0; x < xLength; x++) if (xChars[x] == ' ') AddNewMatch(0, x); // init top row
for (var y = 0; y < yLength; y++) if (yChars[y] == ' ') AddNewMatch(y, 0); // init left column
for (int y = 1; y < yLength; y++) { // inner matrix
var cy = yChars[y];
for (int x = 1; x < xLength; x++) {
var mtPrev = matchMatrix[y - 1, x - 1];
if (xChars[x] == cy) {
if (mtPrev.Null() || (cy == ' ' && xChars[mtPrev.X] != ' ')) {
AddNewMatch(y, x); // AddNewMatch either on no mtPrev or on invalid word
}
else { // lengthen mtPrev
mtPrev.Length += 1;
matchMatrix[y, x] = mtPrev;
}
}
else { // on Un-Match mtPrev cannot be a word-Match. check,
// whether there a beginning ' ' is to cut off
if (mtPrev.NotNull() && mtPrev.Length > 1 &&
xChars[mtPrev.X] == ' ') CutWordStartFromMatch(mtPrev);
}
}
}
// create matchMasks:
int[] yMatchMask = new int[yLength];
int[] xMatchMask = new int[xLength];
matches.Sort();
for (var id = 0; id <= matches.Count - 1; id++) {
var match = matches[id];
for (var i = 0; i <= match.Length - 1; i++) {
var y = match.Y + i;
var x = match.X + i;
if (yMatchMask[y] == 0 && xMatchMask[x] == 0) { // both matchMasks must be free at y/x
yMatchMask[y] = id + 1;
xMatchMask[x] = id + 1;
}
}
}
return new TextAffinity(xMatchMask, yLength);
}
首先，尝试理解 #33 ff：即使可能存在一个匹配的' '，并且可能存在一个前一个匹配mtPrev：如果mtPrev不是以' '开头，则不要将' '附加到mtPrev。
现在请注意第14行的匿名方法CutWordStartFromMatch()。
然后看第41行——检测不匹配项。
如果是这样，检查是否有前一个匹配，如果它以' '开头，这会违反单词偏好异常（因为当前发生了不匹配）。如果是这样，则通过调用以下方法进行修复：CutWordStartFromMatch().
结论
我不确定深入到如此细微的算法泥潭中是否是一个好主意。
因为本文最重要的点是，仅仅是为了介绍我**_文本相似度的新概念_**，以及它比常见的莱文斯坦算法**_更好的结果_**，
好的——通过高性能矩阵操作检测匹配可能也是一个不错的知识点。
而且，“匹配掩码技巧”来消除重叠匹配也可能不错。
将int[]转换为string绝对很有趣——不是吗？
但那个单词异常的东西——哎呀！
很难解释，占据了大量的文章空间，需要观众——也就是你——付出大量的脑力，并抱有坚定的理解意愿——为此我感到抱歉。
再补充一点：TextAffinity 方法比莱文斯坦方法快大约 40%——正如所附源代码中实现的那样。我的测试表明，排序数据不是时间消耗者，但填充矩阵是。
当莱文斯坦在每个矩阵单元格中输入复杂的“成本评估结果”时，TextAffinity 大部分时间只是读取。只有在发生字符匹配时，TextAffinity 才会在单元格中输入一些内容。