java中的序列比较
我正在寻找一个标准算法/代码(Java),它比较两个整数列表(旧的和新的)并给出第三个结果列表,该列表提供将“旧”列表转换为“新”列表的操作。
例如:
old-> 1, 2, 3, 4
new-> 9, 2, 3, 6, 4
所以结果应该是这样的:
1-, 9+, 2, 3, 4-, 6+, 4+
这里,后缀:
- = Deleted item from old list.
+ = New added item to old list.
和其余的(无后缀)是未更改的数字(即值和索引)。 我相信使用 LCS(最长公共序列)的东西可以完成这项工作! 但我真的无法弄清楚是否有。
任何指示都将受到高度赞赏。
I'm looking for a standard algorithm/code (Java) which compares two integer lists (old and new) and gives a third result list which provides actions to convert the 'old' list into the 'new' list.
For example:
old-> 1, 2, 3, 4
new-> 9, 2, 3, 6, 4
so the result should be something like:
1-, 9+, 2, 3, 4-, 6+, 4+
Here, the suffix:
- = Deleted item from old list.
+ = New added item to old list.
and the rest (w/o suffix), are numbers which are unchanged (i.e Value as well as Index). I believe something using the LCS (longest common sequence) would do this job!
But I can't really figure-out if there is any.
Any pointers will be highly appreciated.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
Levenshtein距离算法似乎对你有用(本质上是你提到的LCS算法)。 只需将您选择的操作记录在另一个表中(当您选择最小值后,您需要记录哪个操作导致了最小成本,以便以后能够查找)。
然后使用
action[i, j]
递归地返回该过程并将所选操作推送到堆栈中。Levenshtein distance algorithm seems to work for you (essentially the LCS algorithm you mentioned). Just record the action you choose in another table (right after when you choose the minimum, you need to record which action has resulted the min cost to be able to look it up afterward).
Then use
action[i, j]
to recursively go back through the process and pushing the chosen action in a stack.我用 C# 实现了一些东西。 将其移植到 Java ...
(编辑)
这是 Java 版本:
I implemented something in C#. Porting it to Java ...
(edit)
Here is the Java version:
仅供以后参考。 第一个和第二个答案都很好。
第一个答案是我正在寻找的线索。 比较序列的最佳方法。
和,
第二个答案是比较序列的工作代码。 但这并不能给出将一个列表转换为另一个列表的最佳结果。 但对于简单的差异来说很好!
谢谢大家的解答!!
谢谢,
阿布舍克。
Just for future references. Both the 1st and 2nd answers are good.
The 1st answer is clue to what i was looking for. The optimal way to compare sequences.
and,
The 2nd answer is a working code to compare sequences. But this doesn't give a optimal result for coverting one list to another. But good for a simple diff!!
Thanks all for the answers!!
Thanks,
Abhishek.