C-Sharp-Algorithms/Algorithms/Strings/EditDistance.cs at master · aalhour/C-Sharp-Algorithms · GitHub

Name: C-Sharp-Algorithms/Algorithms/Strings/EditDistance.cs at master · aalhour/C-Sharp-Algorithms · GitHub
Rating: 4.6 (7515 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
usingSystem;

namespaceAlgorithms.Strings
{
/// <summary>
/// The Edit Distance computation algorithm.
/// Uses a custom class for receiving the costs.
/// </summary>
publicstaticclassEditDistance
{
/// <summary>
/// Computes the Minimum Edit Distance between two strings.
/// </summary>
publicstaticInt64GetMinDistance(stringsource,stringdestination,EditDistanceCostsMap<Int64>distances)
{
// Validate parameters and TCost.
if(source==null||destination==null||distances==null)
thrownewArgumentNullException("Some of the parameters are null.");
if(source==destination)
return0;

// Dynamic Programming 3D Table
long[,]dynamicTable=newlong[source.Length+1,destination.Length+1];

// Initialize table
for(inti=0;i<=source.Length;++i)
dynamicTable[i,0]=i;

for(inti=0;i<=destination.Length;++i)
dynamicTable[0,i]=i;

// Compute min edit distance cost
for(inti=1;i<=source.Length;++i)
{
for(intj=1;j<=destination.Length;++j)
{
if(source[i-1]==destination[j-1])
{
dynamicTable[i,j]=dynamicTable[i-1,j-1];
}
else
{
longinsert=dynamicTable[i,j-1]+distances.InsertionCost;
longdelete=dynamicTable[i-1,j]+distances.DeletionCost;
longsubstitute=dynamicTable[i-1,j-1]+distances.SubstitutionCost;

dynamicTable[i,j]=Math.Min(insert,Math.Min(delete,substitute));
}
}
}

// Get min edit distance cost
returndynamicTable[source.Length,destination.Length];
}

/// <summary>
/// Overloaded method for 32-bits Integer Distances
/// </summary>
publicstaticInt32GetMinDistance(stringsource,stringdestination,EditDistanceCostsMap<Int32>distances)
{
// Validate parameters and TCost.
if(source==null||destination==null||distances==null)
thrownewArgumentNullException("Some of the parameters are null.");
varlongDistance=newEditDistanceCostsMap<long>(
insertionCost:Convert.ToInt64(distances.InsertionCost),
deletionCost:Convert.ToInt64(distances.DeletionCost),
substitutionCost:Convert.ToInt64(distances.InsertionCost));

returnConvert.ToInt32(EditDistance.GetMinDistance(source,destination,longDistance));
}

/// <summary>
/// Overloaded method for 16-bits Integer Distances
/// </summary>
publicstaticInt16GetMinDistance(stringsource,stringdestination,EditDistanceCostsMap<Int16>distances)
{
// Validate parameters and TCost.
if(source==null||destination==null||distances==null)
thrownewArgumentNullException("Some of the parameters are null.");
varlongDistance=newEditDistanceCostsMap<long>(
insertionCost:Convert.ToInt64(distances.InsertionCost),
deletionCost:Convert.ToInt64(distances.DeletionCost),
substitutionCost:Convert.ToInt64(distances.InsertionCost));

returnConvert.ToInt16(EditDistance.GetMinDistance(source,destination,longDistance));
}
}

}