优化字符串.替换方法

本文关键字：方法 替换 字符串 优化 | 更新日期: 2023-09-27 18:36:05

我有一个网站上不允许的200+单词的列表。下面的string.Replace方法需要~80ms。如果我将s < 1000增加 10.00 倍以s < 10,000则此延迟将达到 ~834 毫秒，则增加 10.43。我对此功能的可扩展性感到担忧，尤其是在列表大小增加的情况下。有人告诉我字符串是不可变的，text.Replace()正在内存中创建 200 个新字符串。有没有类似于Stringbuilder的东西？

List<string> FilteredWords = new List<string>();
FilteredWords.Add("RED");
FilteredWords.Add("GREEN");
FilteredWords.Add("BLACK");
for (int i = 1; i < 200; i++)
{ FilteredWords.Add("STRING " + i.ToString()); }
string text = "";
//simulate a large dynamically generated html page
for (int s = 1; s < 1000; s++)
{ text += @"Lorem ipsum dolor sit amet, minim BLACK cetero cu nam.
            No vix platonem sententiae, pro wisi congue graecis id, GREEN assum interesset in vix.
            Eum tamquam RED pertinacia ex."; }
// This is the function I seek to optimize
foreach (string s in FilteredWords)
{ text = text.Replace(s, "[REMOVED]"); }

优化字符串.替换方法

使用StringBuilder.Replace并尝试将其作为批处理操作执行。 也就是说，您应该尝试只创建一次StringBuilder，因为它有一些开销。 它不一定会快很多，但会更节省内存。

您可能也应该只进行一次卫生，而不是每次请求数据时。 如果要从数据库中读取数据，则应考虑在将数据插入数据库时对其进行一次清理，以便在读取数据并将其显示到页面时要执行的工作更少。

如果您期望大多数文本相对不错，而不是先扫描整个文本以查找匹配的单词，那么可能是更好的方法。您还可以同时规范化单词文本以捕获一些标准替换。

即

通过匹配单个单词（即像"'w+"这样的正则表达式）来扫描字符串，而不是对每个检测到的单词查找（潜在规范化值）在字典中替换单词。

您可以简单地先扫描以获取"要替换的单词"列表，而不是稍后替换单个单词，也可以同时扫描并构建生成的字符串（使用 StringBuilder 或 StreamWriter ，显然不是 String.Concat/+）。

注意：Unicode 提供了大量好的字符可供使用，所以不要指望你的努力会非常成功。 即尝试在以下文本中找到"酷"："你是 сооl"。

示例代码（依靠 Regex.Replace 进行标记化，并为匹配构建字符串和HashSet）。

var toFind = FilteredWords.Aggregate(
      new HashSet<string>(), (c, i) => { c.Add(i); return c;});
text = new Regex(@"'w+")
   .Replace(text, m => toFind.Contains(m.Value) ? "[REMOVED]" : m.Value));

可能有更好的方法，但这就是我解决问题的方式。

您将需要创建一个树结构，其中包含要替换的单词字典。该类可能是这样的：

public class Node 
{
    public Dictionary<char, Node> Children;
    public bool IsWord;
}

为儿童使用字典可能不是最佳选择，但它在这里提供了最简单的示例。此外，您将需要一个构造函数来初始化Children字段。IsWord字段用于处理一个经过编辑的"单词"可能是另一个经过编辑的"单词"的前缀的可能性。例如，如果要同时删除"红色"和"补救"。

您将根据每个替换单词中的每个字符构建树。例如：

public void AddWord ( string word ) 
{
    // NOTE: this assumes word is non-null and contains at least one character...
    Node currentNode = Root;
    for (int iIndex = 0; iIndex < word.Length; iIndex++)
    {
        if (currentNode.Children.ContainsKey(word[iIndex])))
        {
            currentNode = currentNode.Children[word[iIndex];
            continue;
        }
        Node newNode = new Node();
        currentNode.Children.Add(word[iIndex], newNode);
        currentNode = newNode;
    }
    // finished, mark the last node as being a complete word..
    currentNode.IsWord = true;
}

您需要在那里的某个地方处理区分大小写的问题。此外，您只需要构建一次树，之后您可以从任意数量的线程中使用它，而不必担心锁定，因为您只会从中读取。（基本上，我是说：将其存储在静态的某个地方。

现在，当您准备好从字符串中删除单词时，您需要执行以下操作：

  • 创建一个字符串生成器实例来存储结果
  • 解析源字符串，查找"单词"的开始和停止。你如何定义"单词"很重要。为简单起见，我建议从Char.IsWhitespace开始定义单词分隔符。
  • 确定字符范围是"单词"后，从树的根开始，找到与"word"中的第一个字符关联的子节点。
  • 如果找不到子节点，则会将整个单词添加到StringBuilder
  • 如果找到子节点，则继续与当前节点的子节点进行下一个字符匹配，直到字符用完或节点用完为止。
  • 如果到达"单词"的末尾，请检查最后一个节点的IsWord字段。如果true排除了该单词，请不要将其添加到StringBuilder中。如果false IsWord，则不会替换该单词，并将其添加到StringBuilder
  • 重复此操作，直到用尽输入字符串。

您还需要在StringBuilder中添加单词分隔符，希望在解析输入字符串时很明显。如果您小心地只使用输入字符串中的开始和停止索引，您应该能够在不创建任何垃圾字符串的情况下解析整个字符串。

完成所有这些操作后，使用StringBuilder.ToString()获得最终结果。

您可能还需要考虑 Unicode 代理代码点，但您可能不用担心它。

请注意，我直接在这里输入了此代码，因此可能包含语法错误，拼写错误和其他意外误导。

真正的正则表达式解决方案是：

var filteredWord = new Regex(@"'b(?:" + string.Join("|", FilteredWords.Select(Regex.Escape)) + @")'b", RegexOptions.Compiled);
text = filteredWord.Replace(text, "[REMOVED]");

我不知道这是否更快（但请注意，它也只替换整个单词）。

相关文章：