问题标签 [lcs]

所以基本上我正在处理一个长度不等的训练和测试数据集（一堆数组），如下所示：

我是机器学习领域的新手，我被困在如何使这些不等长的输入数组变得等​​长，从而可以轻松地利用现有的机器学习算法。

目前我可以考虑使用最大公共序列来查找不同长度的输入数组之间的相似性..

但基本上在我得到 LCS 信息之后，我怎样才能将输入数组转换为等长的数组..？

我走对了吗？谁能给我一些帮助？

我有两个有向无环图，我需要计算这些图的最长公共子序列（LCS）。对于两个字符串/子序列，我使用动态编程 (DP) 的 LCS 算法，但是如何将此算法修改为图形？

任何想法？

整个任务：

令 G 是一个有向无环图，其中每个顶点都用有限字母表中的符号标记。不同的顶点可以用相同的符号来标记。G 中的每条有向路径都具有通过连接路径中的顶点符号形成的迹线。图 G 的序列是 G 中某个有向路径的迹的子序列。

设计一种计算两个给定有向无环图的最长公共序列的有效算法。

示例：字符串 DYNAMIC、PROGRAM 和 DEPTHFIRST 是图片的有向无环图序列。String PROGRAM 是它的踪迹。

在这之后我完全脑筋急转弯，我需要找到两个文件之间最长的公共子字符串，一个小文件和一个大文件。我什至不知道从哪里开始搜索，这是我到目前为止所拥有的

到目前为止，我所做的是将每个文件放入一个字符串生成器中，然后放入一个字符串中以消除双空格（它在 MobyDick.txt 上出现了很多）。我找到了这段代码

此代码有帮助，但仅适用于小文件，每次我使用大文件运行它时，都会出现“内存不足：java 堆空间”错误。我需要正确的算法来摆脱堆空间问题，而且我不能增加 java 内存，任何人都可以帮助或指出正确的方向吗？

我正在尝试从该期刊制作 java 代码：

期刊贪婪 LCS

这段代码是关于 afroza begum 计算最长公共子序列的一种贪婪方法。

这是我的[编辑]代码：

但是当我运行该程序时，在某些情况下它有真实的输出，但在另一种情况下它是错误的。该代码有什么问题？谁能给我解释一下？谢谢

编辑：

我的代码现在可以完美运行了，但与那本日记中的伪代码似乎相去甚远。有人可以解释一下吗？为什么我不能完全从期刊中制作代码？当我使用该期刊中给出的伪代码进行制作时，它总是出错。谢谢。

使用标准的 linuxdiff命令，我找不到在其输出中避免以下类型分组的方法（此处的输出列表unified format假设

这个问题针对的是每一行与另一个文件中的对应行略有不同的情况，并且在其对应行旁边查看每一行更有用。

我不想在比较输出中显示这样的组：

- line 1 - line 2 - line 3 + line 1 modified + line 2 modified + line 3 modified

要得到这个：

- line 1 + line 1 modified - line 2 + line 2 modified - line 3 + line 3 modified

当然，这是一个方便的问题，因为这可以通过编写自己的代码来后处理差异输出来完成，或者使用自己的算法与 lcs 算法不同。我认为像 wdiff 等变体不会有太大帮助，因为plain diff -U0输出格式非常适合我的需求，除了这个分组属性，而 wdiff 引入了其他方面对我的情况不是最佳的。

我正在寻找一种命令行方式，或者可以在代码中使用的库，而不是 UI 工具。

在比较两者时，我只能找到有关如何在两个单独的字符串中为最长重复子字符串制定算法的提示。但我需要帮助的是如何在一个 SINGLE looooong 字符串（从文本文件中读取）中找到最长的重复子字符串。我找不到任何关于如何做到这一点的提示。谁能帮帮我？

我已经按照此视频中的说明实施了最长的常见子序列问题。它只是执行第一组代码并生成一个空列表。这个实现有什么问题？

I am trying to find the LCS between two sequences: TACGCTGGTACTGGCAT and AGCTGGTCAGAA. I want my answer to output as a matrix so that I can backtrack which sequence is common (GCTGGT). When I use my code below, I am getting the following error. IndexError: list index out of range. How can I avoid this error in my code below?

我试图找到两个 DNA 序列的 LCS。我正在输出矩阵形式以及包含最长公共序列的字符串。但是，当我在代码中同时返回矩阵和列表时，我收到以下错误：IndexError: string index out of range

如果我要删除涉及变量 temp 和 higestcount 的编码，我的代码将很好地输出我的矩阵。我正在尝试对矩阵使用类似的编码来生成我的列表。有没有办法避免这个错误？根据序列 AGCTGGTCAG 和 TACGCTGGTGGCAT，最长的公共序列应该是 GCTGGT。

我知道 LCS 问题需要时间 ~ O(m n) 其中 m 和 n 分别是两个序列 X 和 Y 的长度。但是我的问题要容易一些，所以我希望算法比〜O（ mn）更快。

这是我的问题：

输入：

一个正整数 Q，两个序列 X=x1,x2,x3.....xn 和 Y=y1,y2,y3...yn，长度均为 n。

输出：

是的，如果 X 和 Y 的 LCS 的长度至少为 n - Q；

假的，否则。

众所周知的算法在这里花费 O(n^2)，但实际上我们可以做得更好。因为每当我们在任一序列中消除多达 Q 个元素而没有找到共同元素时，结果都会返回 False。有人说应该有一个和 O(Q*n) 一样好的算法，但我想不通。

更新：已经找到答案了！

有人告诉我我可以只计算表 c[i,j] 的对角线块，因为如果 |ij|>Q，则意味着两个序列中已经有超过 Q 个不匹配的元素。所以我们只需要计算|ij|<=Q时的c[i,j]。