又来算法3000问了

董卓

需求：

　有n(n>20万)个，长度不同的由单词组成的有序序列，求其最大公共有序序列（可粗略估计不精确）、并逐次取其次大公共序列，并满足序列大于限定最短序列、至最少公共次数为止

例子：

　使用人名为例：
　　序列1={张三, 李四, 王五, 宋六}
　　序列2={朱麻子, 张三, 李四, 王五}
　　序列3={朱麻子, 张三, 李四, 宋六}
　　序列4={宋六, 朱麻子, 张三, 李四}，
　限定最短序列=2、最少公共次数=3
　从中提取出最大的公共的最大重复次数序列{张三, 李四}=4次
　随后是{朱麻子, 张三, 李四}=3次，内含的{朱麻子, 张三}不用重复输出
　并至此找不到更多满足条件公共序列，算法到此截止。

这是可以有啥算法呢？

直接暴力搞个约 20万 x  20万 x 序列长度 x 序列长度 / 2 的水平量计算，感觉很烂啊…

是不是类似word2vec之类的可以用？

loadinglab

您提到的问题是寻找最大公共有序序列，它属于计算机科学中的序列比对问题，通常涉及到文本、生物信息学等领域。对于大规模的数据集，确实存在计算复杂度的挑战。

以下是一些可能的方法和思路，以改善效率：

1. **动态规划算法：** 序列比对问题通常可以使用动态规划算法来解决。您可以使用最长公共子序列（LCS）算法，它可以找到两个序列之间的最长公共子序列。在您的情况下，您可以逐一比较每对序列，找到它们之间的最长公共子序列。这将帮助您找到最大的公共序列。

2. **滑动窗口：** 您可以使用滑动窗口技术，先将所有序列排序，然后逐一比较它们。在比较的过程中，您可以维护一个滑动窗口，其中包含当前最大的公共序列。当找到更大的公共序列时，可以更新滑动窗口。这将减少不必要的比较。

3. **基于索引的数据结构：** 对于大规模数据集，您可以考虑使用索引数据结构，如后缀树或后缀数组。这些数据结构可以帮助您更有效地查找和比较序列的子串。

4. **并行计算：** 如果您有大量的序列需要比较，可以考虑使用并行计算来加速处理。将任务分发到多个处理器或计算节点上，以同时处理多个序列。

5. **近似算法：** 如果您可以容忍一定程度的误差，可以尝试使用近似算法，如MinHash或SimHash，来加速计算。这些算法可以用于寻找相似性而不仅仅是完全相同的序列。

对于大规模数据集，确实需要考虑算法的效率和计算资源的限制。以上提到的方法可以帮助您更有效地处理这个问题，但需要权衡精确性和计算复杂度。是否可以使用类似Word2Vec的方法取决于问题的具体性质，但在这种情况下，传统的序列比对方法可能更合适。

lightdog

字典树？

RandomDictator

你这个数据量应该可以直接暴力解吧，没事不要搞过早优化

—— 来自 S1Fun

ninestb

直接遍历每个序列就行，用哈希表统计每个字符在全部序列重的出现次数，时间复杂度为O(n),缺点就是费点内存，以空间换时间嘛。如果还要做后续处理就最多排个序就完事了。

帆影FX

你把每个序列按开头单词扩展成多个序列，比如{张三, 李四, 王五, 宋六}=> {张三, 李四, 王五, 宋六},{ 李四, 王五, 宋六},{王五, 宋六},{宋六}，感觉然后就是求最长公共前缀的问题?

Hydro

所有序列都满足"最短序列和最少公共次数"的要求
又因为较长的重复序列如ABC，一定来构成自较短的序列AB或BC，且较短的序列的公共/重复次数一定大于或等于其构成的较长序列
所以可以先利用限定最短序列的条件滑，再利用最少公共次数（hashmap, in计算）条件剪枝
如果有更长的满足最低重复次数的子串，那么它一定构成自这些更短的子串
对这些更短的子串，如果有首尾相连/嵌的（即具有拼成更长子串的潜力的），拼接起来作为新的序列，在其内找最短序列+1且满足最少公共次数要求的序列，直到找不到为止

这个思路的改进点是提前用最短序列和公共次数剪枝
最大的问题应该是无法方便地得知一个子串向前或向后拓展一个字符以后，新串的公共次数的情况，只能递归再滑

Hydro

等会，20w个看起来像是分词结果的东西，这个问题的实际场景是自然语言处理吗

艾克萨罗斯

标准的后缀树应用场景，不过自己理解和无bug实现有点难……

—— 来自 HONOR LSA-AN00, Android 12上的 S1Next-鹅版 v2.5.4

linhaolin1

看自动后缀机？

苇原雪道

后缀树典型应用

幻想训诂

楼主的序列是连续的吗？我理解的序列是有序子列，间断取词毫无问题啊

Hydro

哦遍历的时候顺便维护个保存了前后字符node的结构就不用再滑了，我傻逼了