1 #Region "Microsoft.VisualBasic::1be3c1f8e7f71683ca9bbc0deb31892c, Microsoft.VisualBasic.Core\ComponentModel\Algorithm\Levenshtein\DamerauLevenshteinDistance.vb"
2
3     ' Author:
4     
5     '       asuka (amethyst.asuka@gcmodeller.org)
6     '       xie (genetics@smrucc.org)
7     '       xieguigang (xie.guigang@live.com)
8     
9     ' Copyright (c) 2018 GPL3 Licensed
10     
11     
12     ' GNU GENERAL PUBLIC LICENSE (GPL3)
13     
14     
15     ' This program is free software: you can redistribute it and/or modify
16     ' it under the terms of the GNU General Public License as published by
17     ' the Free Software Foundation, either version 3 of the License, or
18     ' (at your option) any later version.
19     
20     ' This program is distributed in the hope that it will be useful,
21     ' but WITHOUT ANY WARRANTY; without even the implied warranty of
22     ' MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
23     ' GNU General Public License for more details.
24     
25     ' You should have received a copy of the GNU General Public License
26     ' along with this program. If not, see <http://www.gnu.org/licenses/>.
27
28
29
30     ' /********************************************************************************/
31
32     ' Summaries:
33
34     '     Module DamerauLevenshteinDistance
35     
36     '         Function: DamerauLevenshtein
37     
38     
39     ' /********************************************************************************/
40
41 #End Region
42
43 Imports Microsoft.VisualBasic.Text.Levenshtein.LevenshteinDistance
44
45 Namespace ComponentModel.Algorithm.DynamicProgramming
46
47     Public Module DamerauLevenshteinDistance
48
49         Public Function DamerauLevenshtein(Of T)(down As T(), across As T(), equals As GenericLambda(Of T).IEquals, insert#, remove#, substitute As Func(Of T, T, Double), transpose As Func(Of T, T, Double)) As Double
50             Dim matrix As New List(Of Double())
51
52             For i As Integer = 0 To down.Length - 1
53                 Dim ds As Double() = New Double(across.Length - 1) {}
54                 Dim d = down(i)
55
56                 For j As Integer = 0 To across.Length - 1
57                     Dim a = across(j)
58
59                     If i = 0 AndAlso j = 0 Then
60                         ds(j) = 0
61                     ElseIf i = 0 Then
62                         ds(j) = ds(j - 1) + insert
63                     ElseIf j = 0 Then
64                         ds(j) = matrix(i - 1)(j) + remove
65                     Else
66                         ds(j) = {
67                             matrix(i - 1)(j) + remove,
68                             ds(j - 1) + insert,
69                             matrix(i - 1)(j - 1) + If(equals(d, a), 0, substitute(d, a))
70                         }.Min
71
72                         If i > 1 AndAlso j > 1 AndAlso equals(down(i - 1), a) AndAlso equals(d, across(j - 1)) Then
73                             ds(j) = System.Math.Min(ds(j), matrix(i - 1)(j - 2) + If(equals(d, a), 0, transpose(d, down(i - 1))))
74                         End If
75                     End If
76                 Next
77             Next
78
79             Dim distance = matrix(down.Length - 1)(across.Length - 1)
80             Return distance
81         End Function
82     End Module
83 End Namespace