什么是C#全模拟PHP函数"similar_text()"？

Question

什么是C#全模拟PHP函数similar_text()？

我试过这段代码

int ComputeLevenshteinDistance(string source, string target)
{
if ((source == null) || (target == null)) return 0;
if ((source.Length == 0) || (target.Length == 0)) return 0;
if (source == target) return source.Length;
int sourceWordCount = source.Length;
int targetWordCount = target.Length;
// Step 1
if (sourceWordCount == 0)
return targetWordCount;
if (targetWordCount == 0)
return sourceWordCount;
int[,] distance = new int[sourceWordCount + 1, targetWordCount + 1];
// Step 2
for (int i = 0; i <= sourceWordCount; distance[i, 0] = i++) ;
for (int j = 0; j <= targetWordCount; distance[0, j] = j++) ;
for (int i = 1; i <= sourceWordCount; i++)
{
for (int j = 1; j <= targetWordCount; j++)
{
// Step 3
int cost = (target[j - 1] == source[i - 1]) ? 0 : 1;
// Step 4
distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1, distance[i, j - 1] + 1), distance[i - 1, j - 1] + cost);
}
}
return distance[sourceWordCount, targetWordCount];
}
double CalculateSimilarity(string source, string target)
{
if ((source == null) || (target == null)) return 0.0;
if ((source.Length == 0) || (target.Length == 0)) return 0.0;
if (source == target) return 1.0;
int stepsToSame = ComputeLevenshteinDistance(source, target);
return (1.0 - ((double)stepsToSame / (double)Math.Max(source.Length, target.Length)));
}

结果值不是等效的 php。

PHP Similar_text(( 函数：计算两个string之间的相似性，如中所述

编程经典：实现世界上最好的算法 奥利弗

(国际标准书号0-131-00413-1(。

请注意，此实现不使用 Oliver 伪代码中的堆栈，而是使用递归调用，这可能会也可能不会加快整个过程。另请注意，此算法的复杂性O(N**3)其中N是最长字符串的长度。

Answer 1

首先，你必须实现编辑距离，比如说，列文斯坦一; 让我们

尽可能通用地做到这一点：请参阅检测两个字符串之间的差异

用于编辑序列和更多详细信息。

法典：

using System.Linq;
...
private static double EditDistance<T>(IEnumerable<T> from,
IEnumerable<T> to,
Func<T, double> insertCost,
Func<T, double> deleteCost,
Func<T, T, double> editCost) {
T[] source = from.ToArray();
T[] target = to.ToArray();
// Minimum cost so far
double[][] D = Enumerable
.Range(0, source.Length + 1)
.Select(line => new double[target.Length + 1])
.ToArray();
// Edge: all removes
double sum = 0.0;
for (int i = 1; i <= source.Length; ++i)
D[i][0] = (sum += deleteCost(source[i - 1]));
// Edge: all inserts
sum = 0.0;
for (int i = 1; i <= target.Length; ++i)
D[0][i] = (sum += insertCost(target[i - 1]));
// Having fit N - 1, K - 1 characters let's fit N, K
for (int i = 1; i <= source.Length; ++i)
for (int j = 1; j <= target.Length; ++j) {
// here we choose the operation with the least cost
double insert = D[i][j - 1] + insertCost(target[j - 1]);
double delete = D[i - 1][j] + deleteCost(source[i - 1]);
double edit   = D[i - 1][j - 1] + editCost(source[i - 1], target[j - 1]);
D[i][j] = Math.Min(Math.Min(insert, delete), edit);
}
return D[source.Length][target.Length];
}

现在很容易写Similar_text

常规：

public static double Similar_text(string left, string right) {
left = left ?? "";
right = right ?? "";
return left.Equals(right)
? 1.0
: 1.0 - EditDistance(left, right, 
insert => 1.0, 
delete => 1.0, 
(from, to) => from == to ? 0.0 : 2.0) 
/ Math.Max(left.Length, right.Length);
}

时间复杂度为O(left.Length * right.Length)或O(N**2)，如果两个字符串的长度大致相等(N(