65.9K
CodeProject 正在变化。 阅读更多。
Home

single_pass_search： 通过单次遍历迭代器进行通用序列搜索

吉姆·佐切利斯
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.94/5 (15投票s)

2008年7月13日

CPOL

12分钟阅读

viewsIcon

51242

downloadIcon

366

本文介绍了一个通用的序列搜索模板函数，它比std::search更通用。

目录

引言

std::search 是一个著名且非常有用和强大的STL算法。能否有一个更通用的序列搜索算法？我们真的能做出比 std::search 更通用的东西吗？也许更高效？或者有没有可能做得比 std::search 更通用，同时又更高效？

主要优点

single_pass_search 是一个模板函数，它执行通用的序列搜索，类似于 std::search [a5] STL算法。single_pass_search 最重要的优点和它相对于 std::search 的主要优势在于，它能够通过一对单次遍历（输入）迭代器来搜索搜索范围中的子序列，[a6,b1] 而 std::search 则要求搜索范围至少可以通过前向迭代器 [a7,b2] 来访问。

例如，single_pass_search 可以直接通过一对 istream [a9] 迭代器轻松搜索文件，而 std::search 则需要引入一个中间容器，以便至少通过一对前向迭代器来获取文件数据。对于像 istream [a10] 这样的数据源，使用 single_pass_search 而不是 std::search [a5] 要简单得多，也更有效率，而且内存消耗也更少，因为 std::search 算法还需要一个中间容器和一些流缓冲逻辑。

次要优点

此外，single_pass_search 的另一个有趣优势是其优于 std::search STL算法的时间复杂度。[a5] single_pass_search 使用的内部算法是对原始的 **Knuth-Morris-Pratt** 算法 [c3] 的改进，该算法由 **David R. Musser** 和 **Gor V. Nishanov** [c5,c6] 实现，并进一步修改，以便与单次遍历迭代器无缝配合作为输入。对于包含 n 个元素和一个包含 m 个元素的模式序列的搜索范围，single_pass_search 的最坏情况时间复杂度为 O(n + m)。[c3,c5] 在相同情况下，std::search 的最坏情况时间复杂度预计不会优于 O(n x m)，因为在所有最著名的STL实现中，[a1,a2,a3,a4] std::search 仅使用直观的（蛮力）搜索算法实现。[c1]

限制

需要澄清的是，single_pass_search 只能通过输入迭代器 [a6,b1] 访问搜索范围，而不能访问模式序列。对于模式序列，仍然需要前向迭代器 [a7,b2]，这与 std::search STL算法类似。[a5] 然而，通过输入迭代器访问模式序列并不那么重要，因为模式序列通常包含非常少的元素，与搜索范围中的元素相比，将所有这些元素复制到中间容器在处理能力和内存消耗方面都相对便宜。

怪异之处和缺点

另一方面，single_pass_search 的主要怪异之处和缺点与其返回值有关。在检测到搜索范围中第一个满足搜索条件的子序列后，single_pass_search 会返回一个指向该子序列 **最后一个元素** 的迭代器。在相同情况下，std::search [a5] 会返回一个指向该子序列 **第一个元素** 的迭代器，这是一种更直观的行为。毕竟，用指向第一个元素来表示和引用一个序列是一个公认的做法。

然而，single_pass_search 的这种怪异之处是有充分理由的，并且实际上是为了支持单次遍历（输入）迭代器而产生的。更具体地说，在检测到搜索范围中一个满足搜索条件的子序列后，我们无法回溯到它的第一个元素，因为单次遍历迭代器不允许我们这样做！[a6,b1] 只有指向该子序列最后一个元素的迭代器仍然是有效的，并且可以表示找到的子序列。

此外，single_pass_search 的这个缺点可能不像乍一看那样不方便。首先，由于我们进行精确模式匹配，因此由于无法访问找到的子序列的元素而没有信息丢失。实际上，在搜索开始之前我们就知道了这个子序列的所有元素。

此外，在某些情况下，有一个指向找到的子序列最后一个元素的方便迭代器可能非常方便！例如，让我们考虑一个需要计算给定搜索范围内某个特定模式出现次数的场景。每当找到一个匹配的子序列时，指向该子序列最后一个元素的迭代器就可以方便地通过仅将其递增一次来恢复对下一个子序列的搜索。（参见 示例）如果我们有一个指向第一个子序列元素的迭代器，那么我们就必须额外处理跳过当前找到的子序列的任务，然后再继续搜索下一个子序列。

语法描述

single_pass_search 是一个重载名称，实际上有四个 single_pass_search 函数，每个函数提供一组不同的输入参数。

template <typename InputIterator, typename ForwardIterator>
inline InputIterator single_pass_search(
        InputIterator searchRange,
        InputIterator searchRangeEnd,
        ForwardIterator pattern,
        ForwardIterator patternEnd)
[输入] searchRange 一个输入迭代器，[a6] 指向搜索范围的第一个元素。
[输入] searchRangeEnd 一个输入迭代器，[a6] 表示搜索范围的结束。
[输入] pattern 一个前向迭代器，[a7] 指向模式序列的第一个元素。
[输入] patternEnd 一个前向迭代器，[a7] 指向模式序列的末尾。
[输出] 返回值 成功时，返回值为一个输入迭代器 [a6]，指向搜索范围中第一个满足搜索条件的子序列的最后一个元素。失败时，返回值为 searchRangeEnd。

在搜索范围 [searchRange, searchRangeEnd) 内搜索一个子序列，该子序列与模式序列 [pattern, patternEnd) 逐个元素比较相同。在找到第一个满足这些条件的子序列后，它会返回一个指向该子序列最后一个元素的迭代器，否则当搜索范围耗尽时返回 searchRangeEnd。

template <typename InputIterator, typename ForwardIterator, typename BinaryPredicate>
InputIterator single_pass_search(
        InputIterator searchRange,
        InputIterator searchRangeEnd,
        ForwardIterator pattern,
        ForwardIterator patternEnd,
        BinaryPredicate pred)
[输入] searchRange 一个输入迭代器，[a6] 指向搜索范围的第一个元素。
[输入] searchRangeEnd 一个输入迭代器，[a6] 表示搜索范围的结束。
[输入] pattern 一个前向迭代器，[a7] 指向模式序列的第一个元素。
[输入] patternEnd 一个前向迭代器，[a7] 指向模式序列的末尾。
[输入] pred 一个二元谓词，[a8] 当执行两个元素之间的相等测试时，将使用它代替 operator==。
[输出] 返回值 成功时，返回值为一个输入迭代器 [a6]，指向搜索范围中第一个满足搜索条件的子序列的最后一个元素。失败时，返回值为 searchRangeEnd。

在搜索范围 [searchRange, searchRangeEnd) 内搜索一个子序列，该子序列与模式序列 [pattern, patternEnd) 通过用户定义的谓词 pred 逐个元素比较相同。在找到第一个满足这些条件的子序列后，它会返回一个指向该子序列最后一个元素的迭代器，否则当搜索范围耗尽时返回 searchRangeEnd。

template< typename SinglePassRange, typename ForwardRange>
inline typename boost::range_iterator<SinglePassRange>::type
single_pass_search(
        SinglePassRange& searchRange,
        ForwardRange& patternRange )
[输入] searchRange 一个 Boost 单次遍历范围对象引用，[b4] 定义了搜索范围。
[输入] patternRange 一个 Boost 前向范围对象引用，[b4] 定义了模式序列。
[输出] 返回值 成功时，返回值为一个 Boost 单次遍历迭代器 [b1]，指向搜索范围中第一个满足搜索条件的子序列的最后一个元素。失败时，返回值为 boost::end(searchRange)。

在由 searchRange 定义的搜索范围内搜索一个子序列，该子序列与由 pattern 定义的模式序列逐个元素比较相同。在找到第一个满足这些条件的子序列后，它会返回一个指向该子序列最后一个元素的迭代器，否则当搜索范围耗尽时返回 boost::end(searchRange)。

重要提示： 为了使用 Boost-range 对象，需要将 USE_BOOST_RANGE 预处理器标志设置为 1。（例如，通过在 #include "single_pass_search.h" 代码行之前写入：#define USE_BOOST_RANGE 1）。

template< typename SinglePassRange, typename ForwardRange, typename BinaryPredicate>
inline typename boost::range_iterator<SinglePassRange>::type
single_pass_search(
        SinglePassRange& searchRange,
        ForwardRange& patternRange,
        BinaryPredicate pred)
[输入] searchRange 一个 Boost 单次遍历范围对象引用，[b4] 定义了搜索范围。
[输入] patternRange 一个 Boost 前向范围对象引用，[b4] 定义了模式序列。
[输入] pred 一个二元谓词，[a8] 当执行两个元素之间的相等测试时，将使用它代替 operator==。
[输出] 返回值 成功时，返回值为一个 Boost 单次遍历迭代器 [b1]，指向搜索范围中第一个满足搜索条件的子序列的最后一个元素。失败时，返回值为 boost::end(searchRange)。

在由 searchRange 定义的搜索范围内搜索一个子序列，该子序列与由 pattern 定义的模式序列通过用户定义的谓词 pred 逐个元素比较相同。在找到第一个满足这些条件的子序列后，它会返回一个指向该子序列最后一个元素的迭代器，否则当搜索范围耗尽时返回 boost::end(searchRange)。

重要提示： 为了使用 Boost-range 对象，需要将 USE_BOOST_RANGE 预处理器标志设置为 1。（例如，通过在 #include "single_pass_search.h" 代码行之前写入：#define USE_BOOST_RANGE 1）。

内部算法

single_pass_search 内部使用 **良好后缀偏移**（匹配偏移）技术。[c4,c2,c3] 传统上，**良好后缀偏移** 用于提高速度，但它还有一个有趣的属性，可以消除在搜索过程中对被搜索数据进行多次遍历的需要。因此，single_pass_search 函数背后的核心思想是使用 **良好后缀偏移** 技术，不是为了提高性能，而是主要为了能够通过单次遍历迭代器进行通用的序列搜索。当然，算法优势带来的任何性能提升也是受欢迎的，尽管性能仍然是次要目标。

最早和最著名的利用 **良好后缀偏移** 技术的算法包括 **Morris-Pratt** [c2] 和 **Knuth-Morris-Pratt** [c3] 算法。最近，在优秀的论文 **"A Fast Generic Sequence Matching Algorithm"** [c5] 中，**David R. Musser** 和 **Gor V. Nishanov** 提出了 **Algorithm-L**，它显著改进了 **Knuth-Morris-Pratt** [c3] 算法，而后者本身是较旧的 **Morris-Pratt** [c2] 算法的改进。single_pass_search 的内部实现实际上是 **Algorithm-L** 的一个改进版本，[c5,c6] 设计用于与单次遍历迭代器无缝配合作为输入，并进一步优化以获得更好的性能。

复杂度和性能

当搜索一个包含 n 个元素的搜索范围中的一个包含 m 个元素的模式序列时，single_pass_search 的最坏情况时间复杂度为 O(n + m)，[c3,c5] 这显然优于 std::search STL算法的 O(n x m) 复杂度。[a5] 此外，**David R. Musser** 和 **Gor V. Nishanov** 在其相关论文 [c5,c6] 中进行了全面的性能测试，这些测试有力地表明，single_pass_search 内部使用的 **Algorithm-L** 在大多数使用场景下都优于直观搜索算法 [c1]。

此外，我还尝试进一步优化了已经很高效的 **Algorithm-L**，在实践中取得了更高的性能。namely，single_pass_search 能够检测在发生不匹配时不需要回溯的模式，并包含专门的代码来非常高效地处理这些频繁出现的案例。因此，尽管性能仍然是次要目标，但考虑到目前在所有著名的STL实现 [a1,a2,a3,a4] 中 std::search 仅仅基于直观（蛮力）搜索算法实现 [c1]，single_pass_search 预计将与 std::search STL算法 [a5] 相比表现相当不错。

结论

关于 single_pass_search 最有趣的一点是，它几乎可以完成 std::search STL算法所做的一切，而且方式更通用（通过单次遍历迭代器），并且具有更优的最坏情况复杂度。这是一个代码可以重新设计得既更通用又更高效的罕见案例！当然，single_pass_search 的使用不如我希望的那么直观，但如果你需要这种通用性，这可能是一个小小的代价。

示例

下面是一个简单的示例程序的源代码，它计算一个给定文件中某个特定字符串模式的出现次数。此示例代码应该可以在大多数现代 C++ 编译器上顺利编译。编译后，可执行程序需要两个命令行参数才能运行：第一个参数定义要搜索的文件的路径，第二个参数确定我们要搜索的字符串模式。

在学习下面的源代码时，很容易区分出计算模式出现次数的 do-while 循环。这个 do-while 循环的极简和小型几乎表明 single_pass_search 在实践中非常方便使用。（另请参见：语法描述）

#include "single_pass_search.h"

#include <iostream>
#include <fstream>
#include <iterator>
#include <string>

int main(int argc, char* argv[])
{
   std::ifstream infile;

   //argv[1]: file path, argv[2]: pattern string
   if (argc != 3)
   {
       std::cout << "Usage: <executable> <file-path> <pattern-string>" << std::endl;
       return -1;
   }

   if (*argv[1] != 0)
        infile.open(argv[1], std::ios::in);

   if ( infile.is_open() )
   {
      typedef std::istreambuf_iterator<char> stream_it_t;
      std::string pattern(argv[2]);

      stream_it_t it, end_it;
      long count = -1;

      do //now count the pattern occurrences (see also: Syntax description)
      {
         it = dpx::single_pass_search(stream_it_t(infile), end_it, pattern.begin(), pattern.end());
         ++count;

      } while (it != end_it);

      infile.close();

      std::cout << "Found " << count << " occurrences of \"" << pattern << "\"" << std::endl;
   }
   else
      std::cout << "Failed to open input file" << std::endl;

   getchar();

   return 0;
}

修订历史

  • 2008年10月11日
    • 性能改进。

  • 2008年7月13日
    • 初始发布。

参考文献

© . All rights reserved.