2

我有 1,000,000 个要分类的字符串。如果它包含一组单词或短语,我这样做的方法是存储它。单词集约为 10,000。理想情况下,我将能够支持正则表达式,但我现在专注于使其快速运行。例句:

福特、保时捷、马自达……

我真的不想将每个单词与字符串一一匹配,所以我决定使用正则表达式。不幸的是,我遇到了一个正则表达式问题:

Regexp.new("(a)"*253) => /(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a )(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)( a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a) (a)(a)(a)(a)(a)(a)(a)(a)(a)...

Regexp.new("(a)"*254) RegexpError: 正则表达式太大: /(a)(a)(a)(a)(a)(a)(a)(a)(a)(a) (a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a) )(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)(a)...

其中 a 将是我的单词或短语之一。现在,我计划运行 10,000 / 253 场比赛。我读到正则表达式的长度会严重影响性能,但是我的正则表达式匹配非常简单,并且正则表达式的创建速度非常快。我想以某种方式绕过限制,或者如果有人有任何想法,请使用更好的解决方案。谢谢。

4

1 回答 1

1

您可以考虑其他识别 10k 单词的机制。

  • Trie:有时称为前缀树,拼写检查器经常使用它来进行单词查找。参见维基百科上的 Trie
  • DFA(确定性有限自动机):DFA 通常由编译器中的词法分析器创建,用于识别语言的标记。DFA 运行速度非常快。简单的正则表达式通常被编译成 DFA。参见维基百科上的 DFA
于 2012-09-25T03:02:29.133 回答