Найти 2 самых похожих Подмассива

Question

Есть многомерный list, примерно такой конструкции:

t, u, u, u, u
a, y, x, u, b
u, u, u, u, u
n, n, n, n,. n

Нужно сравнить каждый список друг с другом, не меняя последовательность, это важно. И получить индексы двух самых похожих. В примере выше это будет 1 и 3 по счету. Буду признателен за хороший код.

Answer 1

Ну, раз хороший код никто не приводит, держите мой плохой :)

using System;
namespace Application
{
    class Program
    {
        static int cmp(int i, int j, int[,] s)
        {
            int sum = 0;
            for(int k = 0; k < s.GetLength(1); ++k)
            {
                sum += (s[i,k]-s[j,k])*(s[i,k]-s[j,k]);
            }
            return sum;
        }
        static void Main(string[] args)
        {
            int[,] s = {{0, 1, 1, 1, 1},{0, 0, 1, 0, 1},
            {1, 1, 1, 1, 1},{0, 0, 0, 0, 0}};

            int min = int.MaxValue, r1 = 0, r2 = 0;
            for(int i = 0; i < s.GetLength(0); ++i)
                for(int j = i+1; j < s.GetLength(0); ++j)
                {
                    int diff = cmp(i,j,s);
                    if (diff < min)
                    {
                        min = diff;
                        r1 = i;
                        r2 = j;
                    }
                }
            Console.WriteLine(r1+" and "+r2);

        }
    }
}

Answer 2

Еще такой вариант, для строк, спасибо @alexander-petrov. Его можно применить и для массивов, ведь строка это тоже массив символов

Метод Сходства Джаро-Винклера

public static double JaroSimilarity(string s1, string s2) {
    if (s1 == s2) return 1;
    if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s1)) return 0;

    // theoretical distance
    var distance = (int) Math.Floor((Math.Max(s1.Length, s2.Length)-1) / 2.0);

    // get common characters
    var commons1 = GetCommonCharacters(s1, s2, distance);
    var commons2 = GetCommonCharacters(s2, s1, distance);
    if (string.IsNullOrEmpty(commons1) || string.IsNullOrEmpty(commons2)) return 0;

    // calculate transpositions
    var transpositions = 0.0;
    for (var i = 0; i < Math.Min(commons1.Length, commons2.Length); i++)
        if (commons1[i] != commons2[i])
            transpositions++;
    transpositions /= 2.0;

    // return the Jaro distance
    return (1 + (double)commons1.Length / s1.Length + (double)commons2.Length / s2.Length - transpositions / commons1.Length) / 3.0;
}

private static string GetCommonCharacters(string s1, string s2, int allowed_distance) {
    var c2 = s2.ToCharArray();
    var commonCharacters = new StringBuilder();

    for (var i = 0; i < s1.Length; i++) {
        // compare if char does match inside given allowedDistance
        // and if it does add it to commonCharacters
        for (var j = Math.Max(0, i - allowed_distance); j < Math.Min(i + allowed_distance + 1, s2.Length); j++) {
            if (c2[j] != s1[i]) continue;
            commonCharacters.Append(s1[i]);
            c2[j] = ' ';
            break;
        }
    }

    return commonCharacters.ToString();
}

private static int GetPrefixLength(string s1, string s2, int min_prefix_length = 4) {
    var n = Math.Min(Math.Min(min_prefix_length, s1.Length), s2.Length);

    for (var i = 0; i < n; i++) {
        if (s1[i] != s2[i]) // return index of first occurrence of different characters 
            return i;
    }

    // first n characters are the same   
    return n;
}

public static double JaroWinkler(string s1, string s2, double prefix_scale = 0.1) {
    var jaro_distance = JaroSimilarity(s1, s2);
    var prefix_length = GetPrefixLength(s1, s2);

    return jaro_distance + prefix_length * prefix_scale * (1.0 - jaro_distance);
}

И вот применение:

public static void MassiveTest() {
    var ss = new string[] { "01111", "00101", "11111", "00000" };

    var max_similarity = 0.0;
    var res1 = -1; var res2 = -1;

    for (var i = 0; i < ss.Length; i++)
        for (var j = i + 1; j < ss.Length; j++) {

            var similarity = JaroWinkler(ss[i], ss[j]);
            if (max_similarity > similarity) continue;

            max_similarity = similarity;
            res1 = i;
            res2 = j;
        }
    Console.WriteLine($"Most similar are {res1 + 1} and {res2 + 1}");
}

PS Можно преобразовать и для массивов, но для строк оно куда полезнее. А преобразовать одноциферный массив в строку - не проблема. В общем есть задел для апдейта, если кто хочет :)

БЛОГ НА HUSL

Найти 2 самых похожих Подмассива

Ответы (2 шт):