Linux C或C++库来区分和修补字符串？

Question

可能重复:
有没有办法从C++中区分文件？

我有很长的文本字符串,我希望差异和补丁.给出字符串a和b:

string a = ...;
string b = ...;

string a_diff_b = create_patch(a,b);
string a2 = apply_patch(a_diff_b, b);

assert(a == a2);

如果a_diff_b是人类可读的,那将是一个奖励.

实现这一点的一种方法是使用system(3)从中调用diff和patchshell命令diffutils并将它们管道化.另一种方法是自己实现这些功能(我正在考虑原子地处理每一行并使用标准编辑距离n ^ 3算法沿行回溯).

我想知道是否有人知道一个好的Linux C或C++库可以在进程中完成这项工作吗？

Answer 1

我相信

https://github.com/cubicdaiya/dtl/wiki/Tutorial

可能有你需要的东西

Answer 2

您可以谷歌实施迈尔斯差异算法.("一个O(ND)差分算法及其变化")或解决"最长公共子序列"问题的库.

据我所知,C++中diff/patch的情况并不好 - 有几个库(包括diff匹配补丁,libmba),但根据我的经验,它们要么记录得不好,要么有很多外部依赖(差异匹配补丁需要Qt 4,例如)或专门用于您不需要的类型(例如,当您需要unicode时为std :: string),或者不够通用,或者使用具有非常高内存的通用算法要求((M + N)^ 2其中M和N是输入序列的长度).

您也可以尝试自己实现Myers算法((N + M)内存要求),但问题的解决方案极难理解 - 预计至少浪费一周阅读文档.迈尔斯算法有点人类可读的解释,请点击这里.