Delphi：高效快速的Unicode文本搜索

Question

在Unicode文本/字符串中是否有快速高效的文本搜索？我需要搜索单词的一部分，而不仅仅是整个单词。

SearchBuf？

谢谢！

- maxfax

---

你使用的是哪个版本的 Delphi？你尝试过使用 System.Pos 和 StrUtils.PosEx 函数了吗？ - RRUZ

请查看此处：https://dev59.com/VHA75IYBdhLWcg3waIQJ。 - Rudy Velthuis

我有Delphi 2010。哪个更快：SearchBuf还是Pos/PosEx？ - maxfax

使用分析器并找出答案吧！记住，对于你来说更快的算法（根据你的字符串值）可能对其他人来说会更慢。也许一个算法在长度小于87个字符的字符串上更快，而另一个算法在超过88个字符的字符串上是对数级别更快，并且在字符串超过182个字符时相对于其他算法甚至更快。再次强调，这些只是根据猜测得出的结论。或许百分号字符将会减慢某个算法的运行速度，但对另一个算法则没有影响。你需要测试才能知道。 - Warren P

Answer 1

正如已经指出的，最快的方法取决于许多因素，最重要的是您是否需要反复搜索。第二个问题是，对于您来说，拥有“最快”的方法比拥有相当快的方法更重要，以及您愿意为优化投入多少时间。 反复搜索 如果您需要反复搜索，则我知道的字符串搜索效率最高的方法是使用后缀数组（通常与Burrows-Wheeler变换结合使用）。这种方法在生物信息学中被广泛使用，因为人们经常需要处理大量的字符串搜索和真正的大型数据集（例如这里）。一个非常好的后缀数组（和BWT）库是libdivsufsort C库，但不幸的是我不知道这个库的Delphi版本。（我相信这个库能够处理Unicode字符串。） 单次搜索 如果您不需要重复搜索，暴力字符串搜索算法可能是高效的，例如汇编优化的FastCode版本的Pos和相关函数。然而，这些是在Delphi转换为Unicode之前编写的，我不知道是否有类似的优化Unicode实现。如果我今天要编写一个并希望将其优化为现代处理器（能够使用SSE4.2指令集）的算法，我会认真研究PCMPESTRI汇编指令（参考pdf文件；也可以参见这里，但我不知道那段代码是否有效），它可以处理Unicode字符串搜索所需的2字节字符。

- PhiS

---

+1 因为你谈到了BWT解决方案，这是我知道的最好的解决方案（虽然有几个变体，但它们都有更多或更少相同的前提条件）。而SSE4.2解决方案总是很诱人的。 - Arnaud Bouchez

Answer 2

从实现来看，SearchBuf比Pos/PosEx慢。但它确实有其他选项，比如整个单词搜索和大小写不敏感搜索。

对于您的目的而言，Pos的UnicodeString版本比PosEx慢（至少在Delphi 2010中，Pos使用最慢的rep scansw汇编语言，而PosEx则使用了两个宽字符展开比较）。因为我猜想您想要一个搜索的起始偏移量（创建子字符串以调用Pos非常慢），所以您可能想使用PosEx。 Bower-More算法可能会更快一些，您需要在应用程序上进行尝试，并针对真实数据进行猜测，看看是否值得。

如果您想要搜索英文文本，则值得尝试使用UTF-8进行存储。搜索将更快，因为使用的内存更少。

但我猜测您的应用程序的主要瓶颈将在存储/检索部分（即访问磁盘或解/压缩），而不在搜索部分。使用软件分析器来猜测哪些部分值得优化：

• 先做对再做快。在做快之前，要做清晰。做快时，保持正确。—— Kernighan和Plauger，《程序设计风格的元素》
• 过早优化是万恶之源。—— Donald Knuth，引用C. A. R. Hoare
• 性能的关键在于优雅，而不是一堆特殊情况。必须抵制调整的诱惑。—— Jon Bentley和Doug McIlroy
• 规则可以概括为：“1.不要过早优化。2.在确实需要之前不要优化。3.即使如此，在了解需要什么以及何处之前也不要优化。”——Herb Sutter

- Arnaud Bouchez

---

只是顺便提一下：我只使用 AnsiString 搜索，但在我的测试中，通常（不总是）FastCode 暴力搜索比 Boyer-Moore 搜索更快。 - PhiS

@Phis 这是因为使用 AnsiString 的 FastCode PosEx() 版本更快（即使是在 Delphi 2010 中使用的版本）：它使用 DWORD 对齐搜索，而在 Delphi 2010 中实现的 UnicodeString 版本仍然使用 WideChar 读取。这就是为什么我写了关于可能使用 AnsiString 的原因。内存/磁盘使用将更低（小两倍），因此更快。对于非英文文本（甚至是中文等更糟糕的情况），AnsiString 将比使用 UnicodeString 更慢，因为 MBCS 是有成本的。 - Arnaud Bouchez

Answer 3

一种快速高效的搜索算法是对于某些情况，如果被搜索的数据不会发生改变并且在同一缓冲区内容中反复搜索，只需搜索一次并构建某种查找表。其中一个可能的解决方案是BoyerMoore（由Rudy在评论中提供链接），但对于真正高范围的Unicode字符（例如范围$0000...$FFFF），它的效果并不好，尽管仍然比重复的Pos或SearchBuf调用更快，但当我使用真正高范围的Unicode数据集（例如中文文本）进行测试时，它消耗了大量内存。我的观点是没有所谓的“完美”解决方案。

也许你可以编写一个比Pos更快但不像BoyerMoore那样占用太多内存的解决方案，如下：

1. 为所有字符点构建一个表，并存储每个字符出现的第一个位置。我会使用稀疏排序数组，对于每个已经完成的搜索，存储该初始字符的每个起始位置。这将避免你通过大型Unicode字符串进行暴力搜索以查找初始字符匹配项。

2. 如果表中不包含特定字符的条目，则必须进行暴力搜索（仅一次）以构建该数据集。如果你通过暴力搜索一次，而代码点U+1234没有出现，则U+1234的条目应该是一个空数组`[]`，表示你不必再次搜索，并且可以快速失败在初始字符不匹配的搜索中。

3. 一旦你找到了像这样的非空搜索初始字符位置列表`[123,456,789]`，即初始代码点匹配，你可以继续通过在string[123...x]、string[456..x]等进行逐个字符检查，直到数组中的元素用尽。任何不匹配都会跳到查找表中的下一个元素。

同样，有些特殊情况下，所有这些额外工作可能会导致代码比Pos还要慢，除非你能确定需要在完全相同的大字符串中搜索许多不同的子字符串，否则所有这些“优化”都是浪费时间的；忘记它吧，即使BoyerMoore字符串搜索也会更慢，当你无法多次重复使用查找数据表时。

如果你只想要一个手动优化为汇编语言的Pos()函数，以在不产生或消耗任何中间表存储的库函数限制内尽可能地运行得快，那么恭喜你，Pos()已经是你可以获得的最快的（我相信它几年前就被FastCode人员优化过）。

- Warren P

---

你的算法很有趣...但我不确定它是否会更快。你在其中使用了许多分支和小的分配（嵌套列表），而一个简单的暴力展开搜索版本可能在现代CPU上更快，具有多个管道。我不认为嵌套列表的内存消耗是一个好的速度解决方案。我们必须在真实数据上找出来...你实现并测试过吗？PhiS回答中的BWT算法是一个更成熟的算法。 - Arnaud Bouchez

是的，我也对更正式的算法描述感兴趣。 - Premature Optimization

本算法的回报仅适用于具有大静态缓冲区的情况，并且您可以通过构建此预搜索表来避免暴力搜索。在文本缓冲区（例如文本编辑器程序）很少更改的情况下，它对我很有效。当涉及的字符串较短且搜索：更改比小于10时，它可能没有用处。 - Warren P

基本上没有什么东西是固有的“总是更快”的，只是在某些情况下可能会获得更快的测量结果。即使是关于快速CPU、大缓存和多个流水线的声明，也有足够的依赖和小细节附加，简短的答案是：没有确定的静态分析，唯一有意义的答案是测试和测量。 - Warren P