c#算法,用于过滤一组包含在其他短语中的所有短语
给定一组短语,我想筛选包含任何其他短语的所有短语。这里包含的意思是,如果一个短语包含另一个短语的所有单词,那么它应该被过滤掉。短语中单词的顺序无关紧要
到目前为止,我得到的是:
- 根据每个短语中的单词数对集合进行排序李>
- 对于集合中的每个短语X:
- 对于集合其余部分中的每个短语Y:
- 如果X中的所有单词都在Y中,那么X包含在Y中,丢弃Y
- 对于集合其余部分中的每个短语Y:
如果给出一个大约一万个短语的列表,这是很慢的。 还有更好的选择吗
你可以在下面搜索框中键入要查询的问题!
给定一组短语,我想筛选包含任何其他短语的所有短语。这里包含的意思是,如果一个短语包含另一个短语的所有单词,那么它应该被过滤掉。短语中单词的顺序无关紧要
到目前为止,我得到的是:
如果给出一个大约一万个短语的列表,这是很慢的。 还有更好的选择吗
# 1 楼答案
按内容对短语进行排序,即“Z A”->;'“Z”,那么从最短的短语到较长的短语很容易消除
# 2 楼答案
你的算法在词组的数量上是二次的,这可能是减慢速度的原因。在这里,我用单词索引短语,以在常见情况下得到二次型
# 3 楼答案
您可以建立一个索引,将单词映射到短语,并执行以下操作:
在此之后,
matched
将包含与目标短语中的所有单词匹配的所有短语。通过将matched
初始化为只包含words[0]
的所有短语集,然后只在words[1..words.length]
上迭代,可以很好地优化它。过滤太短而与目标短语不匹配的短语也可以提高性能除非我弄错了,否则一个简单的实现的最坏情况复杂性(当搜索短语匹配所有短语时)是
O(n·m)
,其中n
是搜索短语中的单词数,m
是短语数# 4 楼答案
这就是寻找一组集合的极小值的问题。朴素的算法和问题定义如下:
有一些次二次算法可以做到这一点(比如this),但考虑到N是10000,实现的效率可能更重要。最佳方法在很大程度上取决于输入数据的分布。考虑到输入集是主要不同的自然语言短语,redtuna建议的方法应该可以很好地工作。下面是该算法的python实现
这仍然是二次的,但在我的机器上,它在350ms内运行一组10k短语,其中包含50%的最小值,单词来自指数分布