Лучший алгоритм для вставки текста до и после токена в C #? - PullRequest
Новая
       10

Лучший алгоритм для вставки текста до и после токена в C #?

1 голос
/ 20 февраля 2009

Я работаю над функцией поиска для приложения MVC C #, которое будет помещать (возможно, большой) кусок текста через фильтр, а с учетом поискового запроса разместит HTML <span> с выделенным стилем перед после каждого поискового запроса.

У меня работает простой алгоритм, но у меня такое ощущение, что он будет медленным, возможно, из-за количества строк, которые нужно будет создать (2 * количество совпадений). 

public static string Surround(string original, string head, string tail, string match, StringComparison comparer)
{
    var ret = original;

    if (ret.IndexOf(match, 0, comparer) != -1)
    {
        var lastIndex = 0;

        while ((lastIndex = ret.IndexOf(match, lastIndex, comparer)) != -1)
        {
            ret = ret.Insert(lastIndex, head);
            var tailIndex = lastIndex + match.Length + head.Length;
            lastIndex = tailIndex;
            ret = ret.Insert(tailIndex, tail);
        }
    }

    return ret;
}

Мне интересно, кто-нибудь может дать несколько советов для лучшего алгоритма, который будет работать лучше для больших кусков текста? Я думал об использовании строителя строк, но мне также пришло в голову, что я могу подойти к этому совершенно неправильно. Любое понимание будет с благодарностью.

Ответы [ 5 ]

6 голосов
/ 20 февраля 2009

Регулярное выражение сделает работу, и код должен быть намного проще. Однако вам нужно будет проверить, действительно ли он обеспечивает лучшую производительность. Примерно так: 

public static string Surround(
    string original, string head, string tail, string match)
{
    return Regex.Replace(
        original, match, head + "$0" + tail, RegexOptions.IgnoreCase);
}

Еще лучше, если вы можете передать заменяющее целое при сохранении 2N строки: 

public static string Surround(string original, string replacer, string match)
{
    return Regex.Replace(original, match, replacer, RegexOptions.IgnoreCase);
}

Surround("foo bar baz", "<span>$&</span>", "bar");  //call like so
1 голос
/ 20 марта 2011

На самом деле RegEx плохо работают с большими кусками текста. Попробуйте вместо этого использовать NFA.

http://swtch.com/~rsc/regexp/regexp1.html

1 голос
/ 20 февраля 2009

StringBuilder, конечно, будет намного быстрее, но тем не менее, когда вы делаете. Вставьте, вы будете перемещаться вокруг большого количества данных каждый раз. Поэтому было бы лучше создать результат в StringBuilder, используя только .Append. Не. Вставить.

Однако вы также должны иметь возможность использовать RegularExpression для этого, хотя я не знаю синтаксис наизусть (я использую замечательный инструмент под названием RegEx Buddy, чтобы создавать свои регулярные выражения, когда мне это нужно.).

РЕДАКТИРОВАТЬ: очень немногие люди в этом мире имеют возможность отличить регулярное выражение от шума линии перехода. : -)

0 голосов
/ 20 февраля 2009

Решение RegEx определенно более элегантно, чем то, что я создал. Тем не менее, использование StringBuilder, как правило, немного быстрее и не требует поиска термина и пре- / пост-исправлений, которые необходимо экранировать регулярными выражениями. 

private static string Surround(string original, string head, string tail, string match, StringComparison comparisonType)
{
  if (string.IsNullOrEmpty(original) || string.IsNullOrEmpty(match) || (string.IsNullOrEmpty(head) && string.IsNullOrEmpty(tail)))
    return original;

  var resultBuilder = new StringBuilder();
  int matchLength = match.Length;
  int lastIdx = 0;

  for (;;)
  {
    int curIdx = original.IndexOf(match, lastIdx, comparisonType);

    if (curIdx > -1)
      resultBuilder
        .Append(original, lastIdx, curIdx - lastIdx)
        .Append(head)
        .Append(original, curIdx, matchLength)
        .Append(tail);
    else
      return resultBuilder.Append(original.Substring(lastIdx)).ToString();

    lastIdx = curIdx + matchLength;
  }
}

Я надеюсь, что вы можете использовать его.

Обновление Пройдя небольшой тест, я думаю, что мое решение будет быстрее, если вы ищете «короткие» слова. Если слово длинное (т.е. длина> 7), Regex выигрывает, но если слово короткое (т.е. длина <7), тогда мое решение выигрывает. Кто-нибудь знает, почему это? Какая операция так чувствительна к длине? Это IndexOf (string, int, int) или, возможно, Append (string, int, int)? </p>

0 голосов
/ 20 февраля 2009

Ответ Люка хорош, но вы можете сначала экранировать любые специальные символы в «match», если кто-то использует. \ ^ $? и т.д. в их поиске (если вы, конечно, не хотите этого разрешать).

ETA: Разрешение специальных символов позволит выполнить более мощный поиск, но также приведет к неожиданному выводу, поскольку найденный текст будет заменен шаблоном, а не фактическим текстом соответствия. *

...