寻找高效的字符串替换算法

Question

我正在尝试创建一个接受 multilpe 替换的字符串替换器。

想法是它会扫描字符串以查找子字符串并将这些子字符串替换为另一个子字符串。

例如，我应该可以要求它用“bar”替换每个“foo”。这样做很简单。

当我尝试为此函数添加多个替换项时，问题就出现了。因为如果我要求它用“foo”替换“bar”，用“bar”替换“biz”，运行这些顺序替换会导致“foo”变成“biz”，而这种行为是无意的。

我尝试将字符串拆分为单词，并运行每个单词中的每个替换函数。然而，这也不是防弹的，因为仍然会导致意外行为，因为您可以要求它替换不是整个单词的子字符串。另外，我发现效率很低。

我正在考虑以某种方式运行每个替换器在整个字符串中出现一次，然后存储这些更改并合并它们。但是我认为我过度设计了。

在网络上搜索关于如何使用 string.replace 和正则表达式的简单结果，它没有解决我的问题。

这个问题已经解决了吗？是否有可以在这里有效地用于此字符串操作的算法？

Answer 1

如果您在搜索所有要替换的子字符串时修改您的字符串，您最终会修改不正确的字符串状态。一个简单的出路可能是首先获取要更新的所有索引的列表，然后遍历索引并进行替换。这样，"bar" 的索引就已经计算好了，即使您稍后将任何子字符串替换为 "bar" 也不会受到影响。

添加一个粗略的 Python 实现给你一个想法：

import re
string = "foo bar biz"
replacements = [("foo", "bar"), ("bar", "biz")]
replacement_indexes = []
offset = 0
for item in replacements:
    replacement_indexes.append([m.start() for m in re.finditer(item[0], string)])

temp = list(string)
for i in range(len(replacement_indexes)):
    old, new, indexes = replacements[i][0], replacements[i][1], replacement_indexes[i]
    for index in indexes:
        temp[offset+index:offset+index+len(old)] = list(new)
        offset += len(new)-len(old)

print(''.join(temp)) # "bar biz biz"

Answer 2

这是我会采用的方法。

我从我的文字和一组替换开始：

string text = "alpha foo beta bar delta";

Dictionary<string, string> replacements = new()
{
    { "foo", "bar" },
    { "bar", "biz" },
};

现在我创建了一组“打开”或“不打开”的部件。打开的部分可以替换其文本。

var parts = new List<(string text, bool open)>
{
    (text: text, open: true)
};

现在我运行通过每次更换并建立一个新的零件清单。如果零件是打开的，我可以进行更换，如果它是关闭的，只需原封不动地添加它。正是这最后一点防止了替换的双重映射。

主要逻辑如下：

foreach (var replacement in replacements)
{
    var parts2 = new List<(string text, bool open)>();
    foreach (var part in parts)
    {
        if (part.open)
        {
            bool skip = true;
            foreach (var split in part.text.Split(new[] { replacement.Key }, StringSplitOptions.None))
            {
                if (skip)
                {
                    skip = false;
                }
                else
                {
                    parts2.Add((text: replacement.Value, open: false));
                }
                parts2.Add((text: split, open: true));
            }
        }
        else
        {
            parts2.Add(part);
        }
    }
    parts = parts2;
}

产生以下结果：

现在只需要重新加入备份：

string result = String.Concat(parts.Select(p => p.text));

给出：

alpha bar beta biz delta

根据要求。

Answer 3

假设您给定的字符串是

str = "Mary had fourteen   little lambs"

所需的替换由以下哈希（又名哈希图）给出：

h = { "Mary"=>"Butch", "four"=>"three", "little"=>"wee", "lambs"=>"hippos" }

表示我们要用 "Butch" 替换 "Mary"（如果它出现在字符串中的任何位置），依此类推。因此我们要return下面的字符串：

"Butch had fourteen   wee hippos"

请注意，我们不希望将 'fourteen' 替换为 'threeteen'，我们希望保留 'fourteen' 和 'wee' 之间的额外空格。

首先将散列h的键收集到一个数组（或列表）中：

keys = h.keys
  #=> ["Mary", "four", "little", "lambs"]

大多数语言都有一个方法或函数 sub 或 gsub，其工作方式类似于以下内容：

str.gsub(/\w+/) do |word|
  if keys.include?(word)
    h[word]
  else
    word
  end
end
  #=> "Butch had fourteen   wee hippos"

正则表达式 /\w+/（例如 Python 中的 r'\w+'）匹配一个或多个单词字符，尽可能多（即贪婪匹配）。单词字符是字母、数字和下划线（'_'）。因此它将依次匹配 'Mary'、'had'、'fourteen'、'little' 和 'lambs'.

每个匹配的单词都传递给“块”do |word| ...end 并由变量 word 保存。然后块计算计算 returns 字符串，该字符串将替换原始字符串副本中 word 的值。当然，不同的语言使用不同的结构和格式来做到这一点。

gsub 传递给块的第一个单词是 'Mary'。然后执行以下计算：

if keys.include?("Mary") # true
  # so replace "Mary" with:
  h[word] #=> "Butch
else # not executed
  # not executed
end

接下来，gsub 将单词 'had' 传递给块并将该字符串分配给变量 word。然后执行以下计算：

if keys.include?("had") # false
  # not executed
else
  # so replace "had" with:
  "had"
  # that is, leave "had" unchanged
end

对正则表达式匹配的每个单词进行类似的计算。

我们看到标点符号和其他 non-word 个字符不是问题：

str = "Mary, had fourteen   little lambs!"

str.gsub(/\w+/) do |word|
  if keys.include?(word)
    h[word]
  else
    word
  end
end
  #=> "Butch, had fourteen   wee hippos!"

我们可以看到gsub并没有顺序执行替换：

h = { "foo"=>"bar", "bar"=>"baz" }
keys = h.keys
  #=> ["foo", "bar"]
"foo bar".gsub(/\w+/) do |word|
  if keys.include?(word)
    h[word]
  else
    word
  end
end
  #=> "bar baz"

请注意，需要keys 的线性搜索才能评估

keys.include?("Mary")

如果 keys 有很多元素，这可能是相对 time-consuming。

在大多数语言中，可以通过将 keys 设为一个集合（唯一元素的无序集合）来加快速度。确定一个集合是否包含给定元素非常快，与确定哈希是否具有给定键相当。

另一种形式是写

 str.gsub(/\b(?:Mary|four|little|lambs)\b/) { |word| h[word] }
   #=> "Butch had fourteen   wee hippos"

其中正则表达式是从 h.keys 以编程方式构建的。此正则表达式为“匹配指示的四个单词之一，前后有单词边界 (\b)。尾随单词边界阻止 'four' 匹配 'fourteen'。由于 gsub现在只考虑替换那四个字块可以简化为{ |word| h[word] }.

同样，这会保留标点符号和多余的空格。

如果出于某种原因我们希望能够替换部分单词（例如，将 'fourteen' 替换为 'threeteen'），只需从正则表达式中删除单词边界即可：

 str.gsub(/Mary|four|little|lambs/) { |word| h[word] }
   #=> "Butch had threeteen   wee hippos"

当然，不同的语言提供了这种方法的变体。例如，在 Ruby 中，可以这样写：

g = Hash.new { |h,k| k }.merge(h)

The 创建一个散列 g，它具有与 h 相同的 key-value 对，但具有额外的属性，如果 g 没有key k, g[k] (key k 的值) returns k.这让我们可以简单地写成：

str.gsub(/\w+/, g)
  #=> "Butch had fourteen   wee hippos"

见第二版String#gsub。

另一种方法（我将展示它是有问题的）是从字符串构建一个单词数组（或列表），适当地替换这些单词，然后重新加入生成的单词以形成一个字符串。例如，

words = str.split
  #=> ["Mary", "had", "fourteen", "little", "lambs"]
arr = words.map do |word|
  if keys.include?(word)
    h[word]
  else
    word
  end
end
  ["Butch", "had", "fourteen", "wee", "hippos"]
arr.join(' ')
  #=> "Butch had fourteen wee hippos"

这会产生类似的结果，只是多余的空格已被删除。

现在假设字符串包含标点符号：

str = "Mary, had fourteen   little lambs!"
words = str.split
  #=> ["Mary,", "had", "fourteen", "little", "lambs!"]
arr = words.map do |word|
  if keys.include?(word)
    h[word]
  else
    word
  end
end
  #=> ["Mary,", "had", "fourteen", "wee", "lambs!"]
arr.join(' ')
  #=> "Mary, had fourteen wee lambs!"

我们可以通过写作来处理标点符号

words = str.scan(/\w+/)
  #=> ["Mary", "had", "fourteen", "little", "lambs"]
arr = words.map do |word|
  if keys.include?(word)
    h[word]
  else
    word
  end
end
  #=> ["Butch", "had", "fourteen", "wee", "hippos"]

此处str.scan returns 是正则表达式/\w+/（一个或多个单词字符）的所有匹配项的数组。明显的问题是 arr.join(' ').

时所有标点符号都丢失了

Answer 4

您可以通过使用正则表达式以简单的方式实现：

import re

replaces = {'foo' : 'bar', 'alfa' : 'beta', 'bar': 'biz'}

original_string = 'foo bar, alfa foo. bar other.'
expected_string = 'bar biz, beta bar. biz other.'

replaced = re.compile(r'\w+').sub(lambda m: replaces[m.group()] if m.group() in replaces else m.group(), original_string)
assert replaced == expected_string

我没有检查性能，但我相信它可能比使用“嵌套 for 循环”更快。

寻找高效的字符串替换算法

Looking for efficient string replacement algorythm

string

algorithm

logic

replace