1

有谁知道如何在文本中进行单遍搜索和替换？我正在开发一个高性能程序，其中每个微优化都很重要。以下是说明我目前所做的示例：

#include <iostream>
#include <string>

/*!
\brief Replaces all common character escape sequences with text representations
\note Some character seqences messes up the trace output and must be replaces
* with text represantions, ie. the newline character will the replaced with "\n"
* etc.
\returns The formatted string
*/
std::wstring ReplaceAll(std::wstring &str)
{
    SearchAndReplace(str, L"\a", L"\\a");   // control-g, C-g
    SearchAndReplace(str, L"\b", L"\\b");   // backspace, <BS>, C-h
    SearchAndReplace(str, L"\t", L"\\t");   // tab, <TAB>, C-i
    SearchAndReplace(str, L"\n", L"\\n");   // newline, C-j
    SearchAndReplace(str, L"\v", L"\\v");   // vertical tab, C-k
    SearchAndReplace(str, L"\f", L"\\f");   // formfeed character, C-l
    SearchAndReplace(str, L"\r", L"\\r");   // carriage return, <RET>, C-m
    return str;
}

/*!
\brief Wide string search and replace
\param str [in, out] String to search & replace
\param oldStr [in] Old string
\param newStr [in] New string
*/
std::wstring SearchAndReplace(std::wstring &str, const wchar_t *oldStr, const wchar_t *newStr) const
{
    size_t oldStrLen = wcslen(oldStr);
    size_t newStrLen = wcslen(newStr);
    size_t pos = 0;

    while((pos = str.find(oldStr, pos)) != string::npos)
    {
        str.replace(pos, oldStrLen, newStr);
        pos += newStrLen;
    }

    return str;
}

int main()
{
    std::wstring myStr(L"\tThe quick brown fox jumps over the lazy dog.\n\tThe quick brown fox jumps over the lazy dog\n\n");
    std::wcout << L"Before replace: " << myStr;
    std::wcout << L"After replace: " << ReplaceAll(myStr);
    return 0;
}

上面的代码显然效率低下，因为它需要多次遍历同一个字符串。单遍搜索和替换功能应该非常灵活，以至于它可以处理要替换的不同字符数组（即不仅仅是列出的转义字符ReplaceAll()）。

4

5 回答 5

2

对于手头的任务，您不需要任何复杂的算法！首先，您正在搜索要替换的“字符串”实际上是字符和不同的字符（另一个回复中提到的更复杂的算法是处理与序列匹配的字符串列表）。此外，您的主要问题是您一直在调整序列的大小。无论如何，您不能就地进行替换，因为字符串会随着每次替换而增长。一个相当简单的方法应该比你当前的方法有更好的性能，据我所知，你离开始微优化还很远——你需要让你的代码首先以正确的方式做事。例如，我会尝试以下几行：

struct match_first
{
    wchar_t d_c;
    match_first(wchar_t c): d_c(c) {}
    template <typename P>
    bool operator()(P const& p) const { return p.first == this->d_c; }
};

void Replace(std::wstring& value)
{
    std::wstring result;
    result.reserve(value.size());
    std::wstring special(L"\a\b\f\n\r\t\v");
    std::pair<wchar_t, std::wstring> const replacements[] = {
        std::pair<wchar_t, std::wstring>(L'\a', L"\\a"),
        std::pair<wchar_t, std::wstring>(L'\b', L"\\b"),
        std::pair<wchar_t, std::wstring>(L'\f', L"\\f"),
        std::pair<wchar_t, std::wstring>(L'\n', L"\\n"),
        std::pair<wchar_t, std::wstring>(L'\r', L"\\r"),
        std::pair<wchar_t, std::wstring>(L'\t', L"\\t"),
        std::pair<wchar_t, std::wstring>(L'\v', L"\\v")
    };

    std::wstring::size_type cur(0);
    for (std::wstring::size_type found(cur);
         std::wstring::npos != (found = value.find_first_of(special, cur));
         cur = found + 1) {
        result.insert(result.end(),
                      value.begin() + cur, value.begin() + found);

        std::pair<wchar_t, std::wstring> const* replacement
            = std::find_if(std::begin(replacements), std::end(replacements),
                           match_first(value[found]));
        result.insert(result.end(),
                      replacement->second.begin(), replacement->second.end());
    }
    result.insert(result.end(), value.begin() + cur, value.end());

    value.swap(result);
}

该算法的思想是对源字符串进行一次遍历，查找所有需要替换的字符串，如果找到，则将不被替换的字符部分和替换字符串复制到正在构建的新字符串中。几乎没有什么东西可以通过一些努力来加快速度，但是这个只移动每个字符一次，而不是原始代码不断改组字符的尾部，而不是向前看一个字符，每个找到的字符都被替换。

于 2013-08-18T14:55:52.393 回答
2

您可以使用哈希表来存储所有对<from,to>并在字符串上运行一次。

对于每个字符，检查它是否存在于哈希表中，如果存在则替换它。

它将一次性完成任务。

于 2013-08-18T13:47:14.413 回答
0

如果您正在寻找更好的性能，您的代码可能会因为这一行而效率低下：

str.replace(pos, oldStrLen, newStr);

这可能会导致：

  1. 字符串重新分配（如果新字符串比旧字符串长）。
  2. 内存移动操作（如果新字符串比旧字符串短或长，那么它后面的所有字符都将移动到新位置）

一个愚蠢的 STL 实现甚至可以为每次替换动态分配缓冲区。内存分配可能很慢，并且很容易变成瓶颈。

分离输入和输出字符串/缓冲区，并将输出缓冲区预分配为大于输入缓冲区的字符串可能更有效。如果将输入和输出字符串分开，则可以保证您的程序会复制inputString.size()字符，并且只会分配一次初始内存（可预测的性能）。如果您就地替换字符，则有可能不会移动任何字符并且不会发生重新分配，并且每次替换字符串中的每个字符都可能会移动多次（更难预测性能）和新的/delete 将被多次调用。

替换可以这样完成：

  1. reserve()预分配大于输入字符串的 空输出字符串（使用）。
  2. 重复直到你用完字符：
    1.1 读几个字符。
    2.2. 看看它们是否与您要替换的东西相匹配。（如果将可替换字符存储在 map/hashtable 中可能会非常快，它的查找速度可能为 o(log n) 或 o(1)）。
    3.3. 如果它们与您想要替换的内容匹配，请编写新字符串。如果没有，请原样写入字符。

另见马尔可夫链

于 2013-08-19T02:15:49.723 回答
0

有许多算法旨在以线性时间执行字符串搜索。尽管它们中的大多数是字符串搜索算法，但您实现它们以在线性时间内执行字符串搜索和替换。它们的线性运行时间需要一些预处理，请务必仔细阅读预处理条件。名单：

要使用这些字符串搜索算法来实现搜索和替换算法，您需要执行以下操作（注意，我所做的分析是专门针对 KMP 的）：

  1. 使用 KMP 查找句子中给定单词的所有出现（跟踪它们的起始索引和找到的单词）。将这些存储在 hashmap 中，让我们不断查找和插入。
  2. 创建一个新的动态字符串（考虑一个动态数组 ADT）。
  3. 遍历句子中的每个字符和每个位置i，检查该位置是否在您的哈希图中。如果是这样，找到单词的相应替换（存储在另一个哈希映射中 - O(1) 查找）并一次替换一个字符，直到j- i，j你的下一个位置，大于你的字符串长度替换减 1，继续并重复，直到您遍历整个句子。

备注：对于第 3 步，您将在逐个迭代字符时将字符复制到新字符串中。如果你到达一个单词，你复制替换和跳过k位置，k匹配单词的字符串长度在哪里。

...最后：释放与原始字符串关联的所有内存，并返回新字符串或将指针设置为等于新字符串。

最后，这应该最终成为2 * sum[i = 1 to n] of O(1)线性时间。

于 2013-08-18T13:59:09.703 回答
0

搜索和替换的主要问题是尝试就地执行它通常效率很低。创建一个新字符串是 O(n) 时间和空间；就地替换很难做到这一点。

可以对字符串进行两次传递；第一个只是计算结果的长度（或者可能构造一个分散-收集列表）。完成后，如有必要，可以调整字符串的大小，然后可以完成替换通道，从字符串的末尾开始，一直到开头。然而，根据我的经验，大量的编码几乎没有什么价值。（此外，如果某些替换是删除，则它不起作用。）

所以我会使用类似下面的东西（它使用 C++11 lambda，只是因为），尽管它不是最理想的：更好的是对替换向量进行排序以便可以使用二进制搜索，或者 - 在某种情况下就像替换控制字符 - 将它们放入由目标字符（具有最小值和最大值）索引的向量中，以便查找只需要两次比较。（或者您可以构建一个只需要一次比较的压缩表，但这也是很多工作。）

#include <algorithm>
#include <initializer_list>
#include <string>
#include <utility>
#include <vector>

template<typename Char, typename String=std::basic_string<Char>>
class Translator {
  public:
    Translator(const std::initializer_list<std::pair<Char, String>> trans) {
      std::for_each(trans.begin(), trans.end(),
                    [&](const std::pair<Char, String>& fromto) {
                    from_.push_back(fromto.first);
                    to_.push_back(fromto.second);
                    });
    }
    void push_translated(String& res, Char ch) { 
      size_t pos = from_.find(ch);
      if (pos == String::npos) res += ch; else res += to_[pos];
    }
    String translate(const String& orig) {
      String rv;
      std::for_each(orig.begin(), orig.end(), [&](Char ch){push_translated(rv, ch);});
      return rv;
    }
  private:
    String from_;
    std::vector<String> to_;
};

上面的初始化列表的使用很可爱，但也应该有一个构造函数，它接受一个std::map或一个std::vector对或一些这样的，因为有时你会想在运行时构建替换，而不是在编译时。

如果您想使用上面的代码，这里有一个简单的驱动程序（对于您的应用程序，您可能想要Translator<wchar_t>）：

#include <iostream>
int main(int argc, char** argv) {
  Translator<char> trans{
    {'\a', "\\a"},
    {'\b', "\\b"},
    {'\f', "\\f"},
    {'\n', "\\n"},
    {'\r', "\\r"},
    {'\t', "\\t"},
    {'\v', "\\v"}
  };
  for (int i = 1; i < argc; ++i) {
    std::cout << trans.translate(argv[i]) << std::endl;
  }
  return 0;
}
于 2013-08-19T01:05:01.590 回答