Как быстро заменить различные вхождения в нескольких строках

Question

У меня общая проблема, когда я не нашел правильного решения. У меня есть несколько строк XML с указанным тегом c (например, MIME_SOURCE), и я не знаю, какая строка XML содержит какое значение. Но я должен заменить все вхождения.

С другой стороны, у меня есть словарь, содержащий все возможные значения XML в качестве ключа и значение, которое нужно заменить на значение. Как я уже сказал, я не знаю, что заменить, в котором XML.

Например

Часть первого XML

    <MIME>
        <MIME_SOURCE>\Web\Bilder Groß\1509_131_021_01.jpg</MIME_SOURCE>
    </MIME>
    <MIME>
        <MIME_SOURCE>\Web\Bilder Groß\1509_131_021_01_MitWasserzeichen.jpg</MIME_SOURCE>
    </MIME>
    <MIME>
        <MIME_SOURCE>\Web\Bilder Groß\icon_top.jpg</MIME_SOURCE>
    </MIME>

Часть второго XML:

    <MIME>
        <MIME_SOURCE>\Web\Bilder klein\5478.jpg</MIME_SOURCE>
    </MIME>

Словарь выглядит следующим образом:

{"\Web\Bilder Groß\1509_131_021_01.jpg", "/Web/Bilder Groß/1509_131_021_01.jpg"}

{"\Web\Bilder Groß\1509_131_021_01_MitWasserzeichen.jpg", "/Web/Bilder Groß/1509_131_021_01_MitWasserzeichen.jpg"}

{"\Web\Bilder Groß\icon_top.jpg", "icon_top.jpg"}

{"\Web\Bilder klein\5478.jpg", "5478.jpg"}

Моя главная проблема заключается в том, что, если я переберу словарь для каждой строки XML, усилия будут считаться XML строки умноженные на количество записей в словаре (n * m). В моем случае это действительно плохо, поскольку в словаре может быть около миллиона XML строк и не менее тысячи записей.

В настоящее время я использую string.Replace для каждого ключа словаря для каждого XML.

У вас есть хорошая идея, как ускорить этот процесс?

---

Редактировать:

Я изменил код на следующий:

        var regex = new Regex(@"<MIME_SOURCE>[\s\S]*?<\/MIME_SOURCE>");

        foreach (Match match in regex.Matches(stringForXml))
        {
            DoReplacements...
        }

Это соответствует требованиям на данный момент, поскольку замена будет выполняться только для каждого MIME_SOURCE в XML. Но я также посмотрю на упомянутый алгоритм.

Answer 1

Самый правильный правильный способ - правильно проанализировать ваш XML. Затем вы можете go пройти через него за один проход:

var xml = @"<root>
    <MIME>
        <MIME_SOURCE>\Web\Bilder Groß\1509_131_021_01.jpg</MIME_SOURCE>
    </MIME>
    <MIME>
        <MIME_SOURCE>\Web\Bilder Groß\1509_131_021_01_MitWasserzeichen.jpg</MIME_SOURCE>
    </MIME>
    <MIME>
        <MIME_SOURCE>\Web\Bilder Groß\icon_top.jpg</MIME_SOURCE>
    </MIME>
</root>";

var replacements = new Dictionary<string, string>()
{
    {@"\Web\Bilder Groß\1509_131_021_01.jpg", "/Web/Bilder Groß/1509_131_021_01.jpg"},
    {@"\Web\Bilder Groß\1509_131_021_01_MitWasserzeichen.jpg", "/Web/Bilder Groß/1509_131_021_01_MitWasserzeichen.jpg"},
    {@"\Web\Bilder Groß\icon_top.jpg", "icon_top.jpg"},
    {@"\Web\Bilder klein\5478.jpg", "5478.jpg"}
};

var doc = XDocument.Parse(xml);
foreach (var source in doc.Root.Descendants("MIME_SOURCE"))
{
    if (replacements.TryGetValue(source.Value, out var replacement))
    {
        source.Value = replacement;
    }
}

var result = doc.ToString();

Если вы можете сделать некоторые предположения о структуре вашего XML (например, без пробелов между тегами <MINE_SOURCE>, без атрибутов, et c), затем вы можете использовать некоторое регулярное выражение, позволяющее вам снова сделать один проход:

var result = Regex.Replace(xml, @"<MIME_SOURCE>([^<]+)</MIME_SOURCE>", match =>
{
    if (replacements.TryGetValue(match.Groups[1].Value, out var replacement))
    {
        return $"<MIME_SOURCE>{replacement}</MIME_SOURCE>";
    }
    return match.Value;
});

Вам придется самостоятельно сравнивать различные подходы на ваших собственных данных. Используйте BenchmarkDo tNet.

Answer 2

Как я уже упоминал в комментарии выше, у меня была похожая проблема (см .: c# Самый быстрый поиск строки во всех файлах ).

Используя алгоритм Ахо-Корасика , который был предложен мне в принятом ответе, я смог выполнить поиск строки достаточно быстро, чтобы решить мою проблему (исходя из минут выполнения до нескольких секунд).

Реализация указанного алгоритма может быть найдена здесь .

Вот небольшой пример того, как использовать реализацию, связанную выше. (смотрит какие-то иголки в стоге сена)

static bool anyViaAhoCorasick(string[] needles, string haystack)
{
    var trie = new Trie();
    trie.Add(needles);
    trie.Build();
    return trie.Find(haystack).Any();
}