1

假设您有一个定义值的首字母缩写词列表（例如 AB1、DE2、CC3），并且您需要检查字符串值（例如“Happy:DE2|234”）以查看是否在字符串中找到首字母缩写词。对于缩写词的简短列表，我通常会创建一个使用分隔符（例如 (AB1|DE2|CC3) ）的简单正则表达式，然后查找匹配项。

但是，如果要匹配超过 30 个首字母缩写词，我将如何解决这个问题？使用相同的技术（丑陋）是否有意义，还是有更有效和优雅的方式来完成这项任务？

请记住，示例首字母缩写词列表和示例字符串不是我正在使用的实际数据格式，而只是表达我的挑战的一种方式。

顺便说一句，我阅读了一个与 SO相关的问题，但认为它不适用于我想要完成的任务。

编辑：我忘了包括我需要捕获匹配的值，因此选择使用正则表达式......

4

5 回答 5

4

就我个人而言，我不认为 30 对于正则表达式来说特别大，所以我不会太快排除它。您可以使用一行代码创建正则表达式：

var acronyms = new[] { "AB", "BC", "CD", "ZZAB" };
var regex = new Regex(string.Join("|", acronyms), RegexOptions.Compiled);
for (var match = regex.Match("ZZZABCDZZZ"); match.Success; match = match.NextMatch())
    Console.WriteLine(match.Value);
// returns AB and CD

所以代码比较优雅和可维护。如果您知道首字母缩略词数量的上限，我会进行一些测试，谁知道正则表达式引擎中已经内置了什么样的优化。您还可以从未来的正则表达式引擎优化中免费受益。除非您有理由相信性能将是一个问题，否则请保持简单。

另一方面，正则表达式可能有其他限制，例如默认情况下，如果您有首字母缩写词 AB、BC 和 CD，那么它只会返回其中两个作为“ABCD”中的匹配项。所以它很擅长告诉你有一个首字母缩写词，但你需要小心捕捉多个匹配项。

当性能成为我的问题（> 10,000 个项目）时，我将“首字母缩略词”放在 HashSet 中，然后搜索文本的每个子字符串（从最小首字母缩写词长度到最大首字母缩写词长度）。这对我来说没问题，因为源文本很短。我以前没有听说过，但乍一看，你提到的问题中提到的 Aho-Corasick 算法似乎是解决这个问题的更好的通用解决方案。

于 2009-01-31T05:39:41.050 回答
0

如果首字母缩略词具有固定大小（如上例所示），您可以为所有缩写词计算哈希值（每个应用程序生命周期可以计算一次），然后将字符串拆分为重叠的部分，并为它们计算哈希值。然后，您所要做的就是从一个数组中搜索值到另一个数组中。

您可能可以从首字母缩略词创建后缀/前缀树或类似的东西并使用此信息进行搜索，维基百科中有很多算法可以做到这一点。

您还可以为每个首字母缩略词创建一个确定性自动机，但它与以前的方法非常相似。

于 2009-01-31T04:37:11.300 回答
0

为什么不简单地拆分字符串并比较返回的列表呢？在这种情况下，使用 REGEX 似乎是不必要的开销。我知道您的格式可能会有所不同，但您似乎可以：

  • 根据“标题分隔符”拆分字符串，在您的情况下为冒号：
  • 取结果的后半部分，即首字母缩写词字符串，并根据首字母缩写词分隔符将其拆分，在本例中为管道 |
  • 最后，遍历新拆分的首字母缩略词列表，并使用嵌套的 for 循环将每个首字母缩写词与候选列表进行比较

编辑：如果您只需要知道字符串中是否存在特定的首字母缩写词或一组首字母缩写词，请使用 .Search() 方法而不是 .Match()。

于 2009-01-31T04:42:08.593 回答
0

正则表达式方法似乎足够高效和优雅。当然，您必须在构建表达式时注意未转义的字符，或者由于复杂性或大小限制而无法编译它。

另一种方法是构建一个trie 数据结构来表示所有的首字母缩写词（这可能在某种程度上重复了正则表达式匹配器正在做的事情）。当您逐步遍历字符串中的每个字符时，您将创建一个指向 trie 根的新指针，并将现有指针推进到适当的子节点（如果有）。当任何指针到达叶子时，您会得到匹配。

于 2009-01-31T05:26:49.017 回答
0

这是我想出的。如果您能提供任何建设性的批评，我将不胜感激……

首先，创建一个包含我的每个首字母缩写词的枚举：

enum acronym
{ AB1,DE2,CC3 }

接下来我创建一个枚举的字符串数组：

string[] acronyms = Enum.GetNames(typeof(acronym));

最后，我遍历字符串数组并执行 regex.match 方法：

foreach (string a in acronyms)
{
    Match aMatch = Regex.Match(input, a.ToString(), RegexOptions.None);
    if (aMatch.Success)
    {
        ...<do something>...
        break;
    }
}

看到这有什么问题吗？

于 2009-01-31T05:30:29.523 回答