1	#Region "Microsoft.VisualBasic::77b792e8706343395263a980e89826fe, 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