Как найти одинаковые части в массиве строк?

Question

У меня есть следующие строки:

astra-srv:658712/sys/broker/state/astra-srv:658712_svc_core
astra-srv:658712/sys/broker/state/astra-srv:658712_svc_client_notify
astra-srv:658712/sys/broker/state/astra-srv:658712_svc_mailer
astra-srv:658712/svc

Я бы хотел из этого получить массив, который бы включал в себя два элемента (только исходя из переданных строк, естественно может быть больше):

[]{astra-srv:658712/svc, astra-srv:658712/sys/broker/state}

Мне как-то совсем в голову решение не приходит, все, что у меня получилось - это результат "astra-srv:658712/s"

Answer 1

"astra-srv:658712/svc" входит только в одну строку и такая строка в ответе ведь не может быть? (а нельзя было проще строки придумать?!)

Задача вычислительно сложная (что-то порядка O(n^3)?).

Ищем в интернете "алгоритм LCS (longest common sequense)" (или сразу его реализацию на C#).
Создаем словарь ответов.
Выбираем первую строку и ищем LCS попарно со всеми остальными строками. Если результат LCS не присутствует в словаре ответов, то добавляем его (проверяем на минимальную длину). Повторяем со всеми строками.
Если нам нужно больше подпоследовательностей то поступаем так. К примеру в строке aaa222bbb найденная подпоследовательность это 222 (добавили в словарь ответов). Тогда из исходного массива удаляем строку aaa222bbb и добавляем две новые строки aaa и bbb.
Повторяем поиск 2. и удаление 3. пока что-то новое находится.

Подозреваю, что в ответе будет много "мусора", поэтому нужны еще какие-то ограничения.

Answer 2

Вообще, исходя из вашего задания и данных, вы должны получить общий префикс astra-srv:658712 - потому что только эта строка является общей для всех строк. Но, допустим, мы хотим получить префиксы, которые состоят из минимум 2 секций.

Ваша задача это типичный поиск префиксов, решается префиксным деревом (или в простонародье trie)

Смысл алгоритма в том, чтобы при исходных данных

astra-srv:658712/sys/broker/state/astra-srv:658712_svc_core
astra-srv:658712/sys/broker/state/astra-srv:658712_svc_client_notify
astra-srv:658712/sys/broker/state/astra-srv:658712_svc_mailer
astra-srv:658712/svc

Каждую строчку разделить по слешу / и построить дерево типа такого

astra-srv:658712
    sys
        broker
            state
                astra-srv:658712_svc_core
                astra-srv:658712_svc_client_notify
                astra-srv:658712_svc_mailer
    svc

отсюда видно, что нужные вам узлы, либо имеют более одного потомка как state, либо не имет потомков, как svc. По хорошему astra-srv:658712 имеет два потомка, то есть это самый общий префикс, но раз мы договорились, что префикс как минимум должет включать 2 секции, то мы проигнирируем astra-srv:658712

Теперь к коду. Нам надо определить узел префиксного дерева и методы для добавления туда строки и для извлечения общих префиксов. Методы простые как топор, потому не комментирую

class TrieNode
{
    private Dictionary<string, TrieNode> childen = new Dictionary<string, TrieNode>();

    public void Add(string[] data, int index = 0)
    {
        if (index >= data.Length) return;
        var item = data[index];
        if (!childen.ContainsKey(item)) childen.Add(item, new TrieNode());
        childen[item].Add(data, index + 1);
    }

    public void CollectSimilarPaths(List<string> currentPath, List<String> result)
    {
        if (currentPath.Count > 1 && (childen.Count == 0 || childen.Count > 1))
        {
            result.Add(string.Join("/", currentPath));
            return;
        }

        foreach (var kv in childen)
        {
            currentPath.Add(kv.Key);
            kv.Value.CollectSimilarPaths(currentPath, result);
            currentPath.RemoveAt(currentPath.Count - 1);
        }
    }
}

Чтобы воспользоваться этой структорой, определим данные в строках

var data = new[] {
    "astra-srv:658712/sys/broker/state/astra-srv:658712_svc_core",
    "astra-srv:658712/sys/broker/state/astra-srv:658712_svc_client_notify",
    "astra-srv:658712/sys/broker/state/astra-srv:658712_svc_mailer",
    "astra-srv:658712/svc"
};

Корень дерева

var root = new TrieNode();

Закидываем в дерево строки, предварительно порубив из по /

foreach (var line in data)
    root.Add(line.Split("/"));

Извлекаем похожие префиксы длиной более 1

var similar = new List<string>();
root.CollectSimilarPaths(new List<string>(), similar);

Вывод на печать

foreach (var line in similar)
    Console.WriteLine(line);

В консоли видим

astra-srv:658712/sys/broker/state
astra-srv:658712/svc

БЛОГ НА HUSL

Как найти одинаковые части в массиве строк?

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