0

我有一个网站上不允许出现的 200 多个单词的列表。下面的string.Replace方法大约需要 80 毫秒。如果我将这个延迟增加s < 100010.00 倍s < 10,000到 ~834 毫秒，增加了 10.43。我担心这个功能的可扩展性，尤其是当列表增加时。有人告诉我字符串是不可变的，并且text.Replace()正在内存中创建 200 个新字符串。有没有类似于 aStringbuilder的东西？

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]"); }
4

4 回答 4

2

如果您希望大部分文本比首先扫描整个文本以匹配单词可能是更好的方法。您还可以同时规范化单词文本以捕获一些标准替换。

即通过匹配单个单词（即正则表达式，如"\w+"）扫描字符串，而不是在要替换的单词字典中查找每个检测到的单词（可能是标准化值）。

您可以先简单地扫描以获取“要替换的单词”列表，然后再替换单个单词，或者同时扫描并构建结果字符串（使用StringBuilderor 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));
于 2013-10-19T06:05:54.410 回答
2

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

您也应该只做一次这种清洁，而不是每次请求数据时。如果您正在从数据库中读取数据，您应该考虑在将数据插入数据库时​​对其进行一次清理，这样在读取数据并将其显示到页面时要做的工作就更少了。

于 2013-10-19T06:06:14.137 回答
1

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

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

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

使用儿童词典可能不是最佳选择，但它提供了最简单的示例。此外，您将需要一个构造函数来初始化该Children字段。该IsWord字段用于处理编辑过的“单词”可能是另一个编辑过的“单词”的前缀的可能性。例如，如果您想同时删除“red”和“redress”。

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

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;
}

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

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

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

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

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

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

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

于 2013-10-19T06:21:59.373 回答
0

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

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

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

于 2013-10-19T14:23:25.483 回答