0

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

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

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

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

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

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

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

4

1 回答 1

1

有一种算法叫做Aho–Corasick string matching algorithm基于trie的算法,对于一个类别,它可以检查该类别中的单词是否出现在Text中。

您可以构建 p 次尝试,它的性能将优于 O(m * n * p * x)。(我认为将是 O(p * m * (n + x) ) )

这是Aho–Corasick_string_matching_algorithm

于 2014-12-11T11:05:56.490 回答