В этой статье мы обсудим::
- Алгоритм Расстояния Хэмминга
- Алгоритм Расстояния Левенштейна
1. Алгоритм Расстояния Хэмминга:
Расстояние Хэмминга измеряет минимальное число замен, необходимых для изменения одной строки в другую.Расстояние Хэмминга между двумя строками одинаковой длины — это число позиций, в которых соответствующие символы различны.Расстояние Хэмминга названо в честь Ричарда Хэмминга.
В приведенном ниже примере мы возьмем две строки, и если длина строк не равна, то мы покажем исключение, иначе он вычислит расстояние между двумя строками.
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Hamming_Distance { public static class StringDistance { public static int GetHammingDistance(string s, string t) { if (s.Length != t.Length) { throw new Exception("Строки должны иметь одинаковую длину"); } int distance = s.ToCharArray() .Zip(t.ToCharArray(), (c1, c2) => new { c1, c2 }) .Count(m => m.c1 != m.c2); return distance; } } class Program { static void Main() { Console.WriteLine(StringDistance.GetHammingDistance("Лук", "Люк")); Console.WriteLine(StringDistance.GetHammingDistance("Трактор", "Самолет")); Console.WriteLine(StringDistance.GetHammingDistance("Кремень", "Картон")); Console.ReadKey(); } } } |
Вывод:
1
7
5
2. Алгоритм Расстояния Левенштейна:
Расстояние Левенштейна- это строковая метрика для измерения разности между двумя последовательностями. Расстояние Левенштейна между двумя словами-это минимальное количество односимвольных правок (т. е. вставок, удалений или замен), необходимых для изменения одного слова в другое. Он назван в честь Владимира Левенштейна.
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Levenshtein_Distance { public static class StringDistance { /// <summary> /// Compute the distance between two strings. /// </summary> public static int LevenshteinDistance(string s, string t) { int n = s.Length; int m = t.Length; int[,] d = new int[n + 1, m + 1]; // Step 1 if (n == 0) { return m; } if (m == 0) { return n; } // Step 2 for (int i = 0; i <= n; d[i, 0] = i++) { } for (int j = 0; j <= m; d[0, j] = j++) { } // Step 3 for (int i = 1; i <= n; i++) { //Step 4 for (int j = 1; j <= m; j++) { // Step 5 int cost = (t[j - 1] == s[i - 1]) ? 0 : 1; // Step 6 d[i, j] = Math.Min( Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost); } } // Step 7 return d[n, m]; } } class Program { static void Main() { Console.WriteLine(StringDistance.LevenshteinDistance("Лук", "Люк")); Console.WriteLine(StringDistance.LevenshteinDistance("Трактор", "Самолет")); Console.WriteLine(StringDistance.LevenshteinDistance("Кремень", "Картон")); Console.ReadKey(); } } } |
Вывод:
1
7
5