更好的 Diff 合并( M)
算法
- 双向 -- 智能生成编辑脚本( 插入和删除) , 描述如何将一个数组转换成另一个数组 .
- 三向合并 - 给一个共同的祖先版本,以及两个更新的版本,生成一个合并的结果,不仅合并了非相冲突的变化,而且精密地解决冲突.
特征
- 致力于各种投入. 按字符,单词,行,或任意符号化使用字符串(因此支持HTML等事物). 或使用与 任意数组。 。 。 .
- 快点. 大约比名人快四倍
diff-merge-patch图书馆 (Neil Fraser,谷歌). - 优质成果. 单位测试显示,编辑比基于流行的Myers-LCS方法的库更精准,如
diff-merge-patch(见下文). - 多种算法. 因为不同的用例可能从不同的算法中受益. 其中包括一些小说.
- 字迹. 以 Typescript 写成,作为正则 Javascript 分发;包括 Typescript 声明.
- 单位检验覆盖率100%. 还有各种各样的角箱测试.
使用量
StringEngine 最简单的引用,用于字符串
产生字符串之间的差异.
import { StringEngine, DiffAlgorithm } from '@asmartbear/diff-merge'
/***** Differences by character *****/
prev = "This is a good test.";
next = "That is a test...";
eng = new StringEngine();
script = eng.getEditsByCharacter(prev, next);
console.log(script.toString());
// Th[is]{at} is a [good ]test.{..}
script.visitEditsForward( edit => {
console.log("type:", edit.isEquality(), edit.isPureInsertion(), edit.isPureDeletion(), edit.isModification());
console.log("prev:", edit.prev.getCopy().join(''));
console.log("next:", edit.prev.getCopy().join(''));
});
// type: true, false, false, false
// prev: Th
// next: Th
// type: false, false, false, true
// prev: is
// next: at
// type: true, false, false, false
// prev: is a
// next: is a
// type: false, false, true, false
// prev: good
// next:
// type: true, false, false, false
// prev: test.
// next: test.
// type: false, ftrue, false, false
// prev:
// next: ..
/***** Differences for prose (by word) *****/
script = eng.getEditsByProse(prev, next);
console.log(script.toString());
// [This]{That} is a [good ]test.{..}
/***** Differences by other things *****/
script = eng.getEditsByLine(prev, next);
script = eng.getEditsByToken(prev, next, /</?[\w-]+[^>]*>/g);
/***** Engine options *****/
eng.opt_algorithm = DiffAlgorithm.SIMPLE; // many times faster, but only basic diffs
eng.opt_algorithm = DiffAlgorithm.HENKEL; // O(N), especially good with lines and code
eng.opt_shift_rightward = false; // faster, but diffs get confused with similar trailing chars
// There's more; see comments in the code.
Engine -- 主类,用于不同数组
将上面的例子改为: Engine 改为 StringEngine启用 getEdits() 而不是上面的字符串指定。 编辑脚本是所使用对象的数组,而不是字符串.
Merge -- 三向合并
这个算法假设已经计算出共享版本和两个新版本之间的差异. 这使得您可以使用任意的标志化和差异引擎选项.
新版本中的第一个叫"现状",第二个叫"应用". 虽然几乎总是合并是对称的,但有时会出现有角相冲突,或者有某些算法选项,需要打出平手. 在这种情况下,领会到"现状"
import { StringEngine, Merge } from '@asmartbear/diff-merge'
orig = "This is a sentence that will be modified twice.";
ver1 = "That was a sentence which will be modified";
orig = "This is sentences that can't be stopped!";
eng = new StringEngine();
orig_to_ver1 = eng.getEditsByCharacter(orig, ver1);
orig_to_ver2 = eng.getEditsByCharacter(orig, ver2);
console.log(orig_to_ver1.toString());
console.log(orig_to_ver2.toString());
// Th[is i]{at wa}s a sentence [that]{which} will be modified[ twice.]
// This is [a ]sentence{s} that [will]{can't} be [modified twice.]{stopped!}
merge = new Merge<string>();
result = merge.merge3( orig_to_ver1, orig_to_ver2 );
console.log(result);
// That was sentences which can't be stopped!
/***** Notice: overlapping deletions and modifications are combined. *****/
merge.opt_combine_overlapping_inserts // can keep both, merge, or keep just status quo
merge.opt_algorithm_combined_overlapping_inserts // when inserts match, we de-duplicate
merge.opt_f_handle_deleted_insert // callback when we delete an insert -- see below.
当一方的插入完全发生在从另一方删除的范围之内时,该插入被忽略. 例如,如果爱丽丝删除了一整段,而鲍勃纠正了该段内的一个打字,那么鲍勃的修改应该被遗忘. 这个 opt_f_handle_deleted_insert 允许用户随时定义回调函数。 例如,您可以在某个地方的用户界面中显示被丢弃的插入列表,以防需要找到重要的东西.
我们所说的"高质量差异"的例子
考虑这两个字符串,其中包含变化以及重复的词和短语:
A: if the word order changes a lot of the time
B: then changes in the word order are changes a lot of the time that we like
有多种方法来解释所发生的变化。 如果从语义角度选择更好的,结果对于人类来说(可能正在尝试去学习"发生的事情")更能理解,同时也会导致更好的合并(因为语义冲突被减少).
这个 diff-merge-patch 库,或任何其他 Myers-LCS 方法,将产生毫无意义的 diffs;这就是图书馆实际创建的 。 第一种是默认输出;第二种是经过其"语义"清理过程后进行. (这里) [brackets] 意思是"删除这个"和 {curly} "插入这个"的意思:
DMP1: [I]{then changes a lot o}f the {time are }word order changes {th}a[ lo]t [of]{we} [t]{s}h[e]{ould} [t]{l}I[m]{k}e
DMP2: [if th]{then changes a lot of the time ar}e word order changes [a lot of the tim]{that we should lik}e
相较于此库中的默认算法,一种小说中最长的子集(不是最长的子集!)方法:
THIS: [if ]the[ word order]{n} changes a lot of the time{ are word order changes that we should like}
另一个例子是,一个词被围绕一个小变化重新排序,我们的小说算法理解了这一点,但经典的DMP并没有,而是显示这个常用词被删除并重新插入:
A: Will be slightly edited in the edited version
B: Will be edited a little bit in the edited version
DMP1: Will be [sl]{ed}I[gh]t[ly ]ed{ a l}it{tl}e[d]{ bit} in the edited version.
DMP2: Will be [slightly edited]{edited a little bit} in the edited version.
THIS: Will be [slightly ]edited {a little bit }in the edited version.
另一处,我们把句子结尾处的改动解释得完美, Myers-LCS 打破:
A: The quick brown fox jumps over the lazy dogs.
B: These quickish browne fox jumps about the lacidasical dogs...right?
DMP2: The{se} quick{ish} brown{e} fox jumps [over]{about} the la[zy dogs.]{cidasical dogs...right?}"
THIS: The{se} quick{ish} brown{e} fox jumps {ab}o[ver]{ut} the la[zy]{cidasical} dogs.{..right?}
最后,一个长句,从实际的 实例 从文献中,DMP1使变化变得一团糟,而DMP2则会产生大块的插入和删除,这些插入和删除错过了语义上的相近之处,并且与这种算法逐个字比较好得多(WORD)),并在此包含另一个算法,它从一个亨克尔通过到更好的组等块,然后使用默认算法来分析等分相间的片段,则更好(BOTH:
A: with the boat train arriving, people talking loudly, chains being dropped, and the screws the beginning, and the steamer suddenly hooting
B: with the boat train arriving; with people quarrelling outside the door; chains clanking; and the steamer giving those sudden stertorous snorts
DMP1: with the boat train arriving[,]{; with} people [t]{qu}a{rre}l[k]{l}ing [l]ou{tsi}d[ly,]{e the door;} chains [be]{clank}ing[ dropped,]{;} and the s[cr]{t}e[ws th]{am}e{r} [be]gi[nn]{v}ing[, and] th[e ]{o}s[t]e[amer] sudden[ly] [h]{stert}o{r}o[ti]{us s}n[g]{orts}
DMP2: with the boat train arriving[,]{; with} people [talk]{quarrell}ing [l]ou[dly, chains being dropped, and the screws the beginning, and the steamer suddenly hooting]{tside the door; chains clanking; and the steamer giving those sudden stertorous snorts}
THIS: with the boat train arriving[,]{; with} people [t]{qu}a{rre}l[k]{l}ing [l]ou{tsi}d[ly,]{e the door;} chains [be]{clank}ing[ dropped, and the screws the beginning,]{;} and the steamer {giving those }sudden[ly] [h]{stert}o{r}o{us snor}t[ing]{s}
WORD: with the boat train arriving[,]{; with} people [talking]{quarrelling} [loudly, chains being dropped, and]{outside} the [screws]{door;} [the]{chains} [beginning,]{clanking;} and the steamer [suddenly]{giving} [hooting]{those sudden stertorous snorts}
BOTH: with the boat train arriving[,]{; with} people [talking]{quarrelling} [loudly,]{outside the door;} chains [being dropped, and the screws the beginning,]{clanking;} and the steamer [suddenly]{giving} [hooting]{those sudden stertorous snorts}
捐款
这是一个仅限无害环境管理的TypeScript包;需要20+节点.
npm install
npm test # vitest, all tests must pass
npm run typecheck # tsc --noEmit
npm run lint # biome check
npm run build # tsc → dist/
npm run bench # vitest bench (relative timing vs DMP)
#罗斯/README