8

我试图混淆大量数据。我创建了一个要替换的单词（标记）列表，并且正在使用 StringBuilder 类逐个替换单词，如下所示：

 var sb = new StringBuilder(one_MB_string);
 foreach(var token in tokens)
 {
   sb.Replace(token, "new string");
 }

这很慢！有什么简单的方法可以加快速度吗？

标记是大约一千个字符串的列表，每个字符串长度为 5 到 15 个字符。

4

4 回答 4

13

不要在一个巨大的字符串中进行替换（这意味着您要移动大量数据），而是遍历字符串并一次替换一个标记。

为每个标记创建一个包含下一个索引的列表，找到第一个标记，然后将文本复制到标记到结果，然后替换标记。然后检查该标记下一次出现在字符串中的位置，以使列表保持最新。重复直到找不到更多的标记，然后将剩余的文本复制到结果中。

我做了一个简单的测试，这个方法在 208 毫秒内对 1000000 个字符串做了 125000 次替换。

Token 和 TokenList 类：

public class Token {

    public string Text { get; private set; }
    public string Replacement { get; private set; }
    public int Index { get; set; }

    public Token(string text, string replacement) {
        Text = text;
        Replacement = replacement;
    }

}

public class TokenList : List<Token>{

    public void Add(string text, string replacement) {
        Add(new Token(text, replacement));
    }

    private Token GetFirstToken() {
        Token result = null;
        int index = int.MaxValue;
        foreach (Token token in this) {
            if (token.Index != -1 && token.Index < index) {
                index = token.Index;
                result = token;
            }
        }
        return result;
    }

    public string Replace(string text) {
        StringBuilder result = new StringBuilder();
        foreach (Token token in this) {
            token.Index = text.IndexOf(token.Text);
        }
        int index = 0;
        Token next;
        while ((next = GetFirstToken()) != null) {
            if (index < next.Index) {
                result.Append(text, index, next.Index - index);
                index = next.Index;
            }
            result.Append(next.Replacement);
            index += next.Text.Length;
            next.Index = text.IndexOf(next.Text, index);
        }
        if (index < text.Length) {
            result.Append(text, index, text.Length - index);
        }
        return result.ToString();
    }

}

使用示例：

string text =
    "This is a text with some words that will be replaced by tokens.";

var tokens = new TokenList();
tokens.Add("text", "TXT");
tokens.Add("words", "WRD");
tokens.Add("replaced", "RPL");

string result = tokens.Replace(text);
Console.WriteLine(result);

输出：

This is a TXT with some WRD that will be RPL by tokens.

注意：此代码不处理重叠标记。例如，如果您有标记“菠萝”和“苹果”，则代码无法正常工作。

编辑：
要使代码使用重叠标记，请替换此行：

next.Index = text.IndexOf(next.Text, index);

使用此代码：

foreach (Token token in this) {
    if (token.Index != -1 && token.Index < index) {
        token.Index = text.IndexOf(token.Text, index);
    }
}
于 2009-04-02T23:41:25.160 回答
5

好的，你明白为什么要花很长时间了吧？

您有 1 MB 的字符串，对于每个令牌，replace 正在遍历 1 MB 并制作一个新的 1 MB 副本。好吧，不是一个精确的副本，因为找到的任何标记都将替换为新的标记值。但是对于每个令牌，您读取 1 MB，更新 1 MB 存储空间，并写入 1 MB。

现在，我们能想出更好的方法吗？不如不为每个令牌迭代 1 MB 字符串，而是遍历一次。

在走之前，我们将创建一个空的输出字符串。

当我们遍历源字符串时，如果我们找到一个标记，我们将token.length()向前跳转字符，并写出混淆的标记。否则我们将继续下一个字符。

本质上，我们将这个过程从里到外翻过来，在长字符串上执行 for 循环，并在每一点寻找一个标记。为了加快速度，我们需要快速循环标记标记，因此我们将它们放入某种关联数组（一组）中。

我明白为什么它需要很长时间，但不确定修复。对于我正在执行替换的每个 1 MB 字符串，我有 1 到 2000 个要替换的 tokan。因此，逐个字符地寻找一千个标记中的任何一个似乎并不快

一般来说，什么是编程时间最长的？新的记忆。

现在，当我们创建一个 StringBuffer 时，可能发生的情况是分配了一些空间（比如 64 字节，并且每当我们追加超过其当前容量时，它可能会增加一倍的空间。然后复制旧字符缓冲区到新的。（​​有可能我们可以 C 的 realloc，而不必复制。）

因此，如果我们从 64 字节开始，为了达到 1 MB，我们分配并复制：64，然后是 128，然后是 256，然后是 512，然后是 1024，然后是 2048 ......我们这样做二十次以达到 1 MB . 在到达这里时，我们分配了 1 MB 只是为了把它扔掉。

通过使用类似于 C++reserve()函数的东西进行预分配，至少可以让我们一次性完成所有操作。但对于每个令牌来说，它仍然是一次性的。您至少要为每个令牌生成一个 1 MB 的临时字符串。如果您有 2000 个令牌，那么您将分配大约 20 亿字节的内存，最终都是 1 MB。每个 1 MB 一次性文件都包含前一个结果字符串的转换，并应用了当前标记。

这就是为什么这需要这么长时间。

现在是的，决定在每个字符上应用哪个标记（如果有的话）也需要时间。您可能希望使用正则表达式，它在内部构建一个状态机来运行所有可能性，而不是像我最初建议的那样进行集合查找。但真正让你感到沮丧的是分配所有内存的时间，用于 2000 个 1 MB 字符串的副本。

丹·吉布森建议：

对您的标记进行排序，这样您就不必为每个字符寻找一千个标记。排序需要一些时间，但最终可能会更快，因为您不必搜索每个字符的数千个标记。

这就是我将它们放入关联数组（例如，Java HashSet）的原因。但是另一个问题是匹配，例如，如果一个标记是“a”而另一个是“an”——如果有任何共同的前缀，也就是说，我们如何匹配？

这就是 Keltex 的答案派上用场的地方：他将匹配委托给 Regex，这是一个好主意，因为 Regex 已经定义了（贪婪匹配）并实现了如何做到这一点。一旦匹配成功，我们就可以检查捕获的内容，然后使用 Java Map（也是一个关联数组）为匹配的未混淆标记找到混淆标记。

我想把我的答案集中在如何解决这个问题上，而且首先要解决为什么会出现问题。

于 2009-04-02T22:07:26.307 回答
2

如果您可以通过正则表达式找到您的标记，则可以执行以下操作：

RegEx TokenFinder = new Regex("(tokencriteria)");
string newstring = myRegEx.Replace(one_MB_string, new MatchEvaluator(Replacer));

然后将 Replacer 定义为：

private string Replacer(Match match)
{
    string token= match.Groups[1].Value;
    return GetObfuscatedString(token);
}
于 2009-04-02T22:06:28.850 回答
1

一次构建一个标记的字符串会更快吗，只在需要时替换？为此，GetObfuscatedString()可以这样实现：

string GetObfuscatedString(string token)
{
    if (TokenShouldBeReplaced(token))
        return ReplacementForToken(token)
    else
        return token;
}

现在，您可以像这样将每个令牌添加到构建器：

StringBuilder sb = new StringBuilder(one_MB_string.Length);
foreach (string token in tokens)
{
    sb.Append(da.GetObfuscatedString(token));
}

您只需要在字符串上进行一次传递，它可能会更快。

于 2009-04-02T22:01:21.140 回答