performance - 提高文本匹配性能的数据结构

Question

我正在努力将一些文本归类到最适合该文本的类别中。作为第一步，我正在编写一个简单的文本匹配代码。我正在将文本集中的一段文本中的单词与指示某些类别的单词进行比较。

这个简单搜索的复杂度变得太大了 O(n^4)!

文本:许多好莱坞电影都很棒。电影爱好者沉迷于他们。 (n个词在1个句子和m个这样的句子中)

类别可以是:电影、歌曲、体育等(p 个类别，每个类别有 x 个单词)

电影的指示词-[电影、电影院、电影...](一个类别的 x 个词)

因此，搜索时间变为 O(m *n * p * x)，这可能太大了。

你能建议我一些数据结构/方法来解决简化复杂性的问题吗？

Answer 1

有一种算法叫做Aho–Corasick字符串匹配算法，它是基于trie的，对于一个类别，它可以检查类别中的词是否出现在文本中。

你可以建立 p 次尝试，它会比 O(m * n * p * x) 表现得更好。 (我认为将是 O(p * m * (n + x) ) )

这里是 Aho–Corasick_string_matching_algorithm