我有 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: regular expression too big: /(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 场比赛。我读到正则表达式的长度会严重影响性能,但我的正则表达式匹配非常简单,而且创建正则表达式的速度非常快。我想以某种方式绕过限制,或者如果有人有任何想法,可以使用更好的解决方案。谢谢。
最佳答案
您可能会考虑其他机制来识别 10k 单词。
- Trie:有时称为前缀树,拼写检查程序经常使用它来进行单词查找。参见 Trie on wikipedia
- DFA(确定性有限自动机):DFA 通常由编译器中的词法分析器创建,用于识别语言的标记。 DFA 运行得非常快。简单的正则表达式通常被编译成 DFA。参见 DFA on wikipedia
关于Ruby 正则表达式太大/多个字符串匹配,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12574559/