1

我有一个字符串搜索问题，关于如何实现它，我想到了两个想法。我想知道人们是否可以指出哪种方法会给我带来更高效的性能，或者甚至可以提出更好的方法？

问题是我有一个大约 450kb 的文本文件，其中包含以下格式的数据：

description1, code1\n
description2, code2\n
description3, code3\n
...

它是由逗号分隔的两列数据，每条记录由描述和代码组成。

代码是一个简短的三字符文本，对用户没有直接意义，这就是为什么有与代码配对的描述数据。

描述数据是一个简短的句子，向用户描述代码的含义。

我正在尝试创建一个 GUI，用户可以在其中在可编辑的文本字段中输入搜索关键字，然后用于搜索描述数据。然后系统将返回所有过滤的记录，即所有具有关键字作为子字符串的描述数据以及与之配对的代码供用户选择。这发生在用户键入的每个字符上。

关于如何实现此功能，首先想到的想法是使用描述数据作为键创建键值对集合，例如 a NameValueCollection，然后使用 foreach 循环遍历每条记录并搜索键以查找匹配子串。

第二种思路是把整个文本文件读成一个长字符串，用这个String.IndexOf()方法搜索关键字，只要搜索到了，我就提取那部分记录返回给用户。

想到第二个想法是因为我担心第一个想法可能对性能产生影响。我已经读到使用的IndexOf方法StringComparison.Ordinal比 Boyer–Moore 字符串搜索算法执行得更好，所以我认为以这种方式实现它会有更好的性能？

因此，当在键中搜索子字符串时，它是否提供更快的检索以将整个文件存储为字符串或 NameValueCollection，或者有更好的方法吗？

4

1 回答 1

2

如果您有大量字符串并计划搜索完全相同的子字符串，那么您有很多可用的选项。

一种选择是使用Aho-Corasick 字符串匹配算法在文件的每一行中搜索搜索查询。执行此操作的总运行时间为 O(m + n + z)，其中 m 是查询的长度，z 是总匹配数，n 是文件中所有字符串的字符总数.

一个更好但更复杂的选择是从文件的所有行中构建一个通用的后缀树。然后，您可以在 O(n + z) 时间内找到所有匹配行，其中 n 是要搜索的模式的长度，z 是文件中的总行数。这需要 O(m) 预处理时间，其中 m 是文件中的字符总数。这比第一个选项快得多，但是您可能必须找到一个好的后缀树库，因为后缀树构造算法相当复杂。

希望这可以帮助！

于 2012-12-08T00:06:08.930 回答