替换许多字符串的更好方法 - 在C#中进行模糊处理

我正在尝试模糊大量数据.我已经创建了一个我要替换的单词(标记)列表,我正在使用StringBuilder类逐个替换单词,如下所示:

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

这很慢!有什么简单的事情可以加快吗？

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

而不是在一个巨大的字符串中进行替换(这意味着您可以移动大量数据),而是一次完成字符串并替换一个令牌.

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

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

令牌和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{

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

好的,你明白为什么要花很长时间,对吗？

你有1 MB的字符串,并且对于每个令牌,replace是迭代1 MB并创建一个新的1 MB副本.好吧,不是一个精确的副本,因为找到的任何令牌都被替换为新的令牌值.但对于每个令牌,您正在读取1 MB,新增1 MB存储空间,并写入1 MB.

现在,我们能想到更好的方法吗？如何而不是为每个令牌迭代1 MB字符串,我们改为走一次.

在走之前,我们将创建一个空输出字符串.

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

从本质上讲,我们将过程内部化,在长字符串上执行for循环,并在每个点寻找令牌.为了快速实现这一点,我们需要对令牌进行快速循环,因此我们将它们放入某种关联数组(一组)中.

我明白为什么它会花很长时间,但不确定修复.对于我正在进行替换的每个1 MB字符串,我有1到2千个想要替换的东西.因此,逐字逐句寻找一千个令牌中的任何一个并不会更快

一般来说,编程需要花费最长时间？新的记忆.

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

因此,如果我们从64字节开始,要达到1 MB,我们分配和复制:64,然后是128,然后是256,然后是512,然后是1024,然后是2048 ...我们这样做了20次以达到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(也是一个关联数组)来查找匹配的,未经过模糊处理的标记的模糊标记.

我想把我的答案集中在不仅仅是如何解决这个问题,而是为什么首先出现问题.