s*******e
发帖数: 4188 | 1 我们都知道经典的file diff，有现成的算法把added/removed/modified lines找出来。
现在我有一个二维的情况。我有一个m x n的table，增加、减少了一些rows，又增加、
减少了一些columns，又修改了一些cell里的data，最后变成了一个k x l的table。怎
样能得到这两个table的diff？
如果你知道现成的算法，please give me a pointer。或者有什么idea讨论讨论。 |
w********9
发帖数: 8613 | 2
来。
看起来不像很常用。如果用得不多，转换成file的比较好了。如果有些值重复多，问题
就复杂了。
【在 s*******e 的大作中提到】
: 我们都知道经典的file diff，有现成的算法把added/removed/modified lines找出来。
: 现在我有一个二维的情况。我有一个m x n的table，增加、减少了一些rows，又增加、
: 减少了一些columns，又修改了一些cell里的data，最后变成了一个k x l的table。怎
: 样能得到这两个table的diff？
: 如果你知道现成的算法，please give me a pointer。或者有什么idea讨论讨论。
|
k*********t
发帖数: 2999 | 3 1. find match between rows of A and B.
2. string match between each matched pair of rows.
来。
【在 s*******e 的大作中提到】
: 我们都知道经典的file diff，有现成的算法把added/removed/modified lines找出来。
: 现在我有一个二维的情况。我有一个m x n的table，增加、减少了一些rows，又增加、
: 减少了一些columns，又修改了一些cell里的data，最后变成了一个k x l的table。怎
: 样能得到这两个table的diff？
: 如果你知道现成的算法，please give me a pointer。或者有什么idea讨论讨论。
|
s*******e
发帖数: 4188 | 4 For #1, if there are added columns, no two rows will be the same. How do you
match the rows?
【在 k*********t 的大作中提到】
: 1. find match between rows of A and B.
: 2. string match between each matched pair of rows.
:
: 来。
|
k*********t
发帖数: 2999 | 5 near-duplicate search. There are many ways to compute the matching score.
you
【在 s*******e 的大作中提到】
: For #1, if there are added columns, no two rows will be the same. How do you
: match the rows?
|
w********9
发帖数: 8613 | 6 这个问题是个比较复杂比较全面的approximate longest string match问题，而不止是
局部的。要顾及深度和matching的程度。单元的数据重复性强时，不同的好算法会有取
舍问题，造成有不同的结果。 |
s*******e
发帖数: 4188 | 7 是这样，问题的解可能不止一个。我们可以这样定义最优解：identify added/deleted
rows/columns以后，使得modified cells个数最少。这个最优解也可能不止一个，我
只要找出任意一个就行了。
我希望能得到一个算法，能证明它总能得到最优解。
或者找个approximate的算法，但我要有个good idea在那些情况下得到的不是最优解。
【在 w********9 的大作中提到】
: 这个问题是个比较复杂比较全面的approximate longest string match问题，而不止是
: 局部的。要顾及深度和matching的程度。单元的数据重复性强时，不同的好算法会有取
: 舍问题，造成有不同的结果。
|
s*******e
发帖数: 4188 | 8 如果按照某种criteria找到了一对一对的matching rows，再去一对一对地比较这rows
，会得到一些added/deleted cells，但很难保证（证明）这些cells在同一个column上。
如果有什么idea，请继续contribute。
【在 k*********t 的大作中提到】
: near-duplicate search. There are many ways to compute the matching score.
:
: you
|
|
k*********t
发帖数: 2999 | 9 The first step (match rows) actually does row alignment, and the second step
(matching strings in each matched row) does the column alignment. Then the
target 2D alignment is achieved by the alternative 1D alignments. I am not
sure whether it is an optimal solution.
Direct 2D alignment may be achieved by matching local 2D features. But it
can be difficult since the permutation can be arbitrary.
rows
上。
【在 s*******e 的大作中提到】
: 如果按照某种criteria找到了一对一对的matching rows，再去一对一对地比较这rows
: ，会得到一些added/deleted cells，但很难保证（证明）这些cells在同一个column上。
: 如果有什么idea，请继续contribute。
|
G*****m
发帖数: 5395 | 10 this should be a heuristic solution
the solution space is 2d while only a 1d path is searched
step
the
【在 k*********t 的大作中提到】
: The first step (match rows) actually does row alignment, and the second step
: (matching strings in each matched row) does the column alignment. Then the
: target 2D alignment is achieved by the alternative 1D alignments. I am not
: sure whether it is an optimal solution.
: Direct 2D alignment may be achieved by matching local 2D features. But it
: can be difficult since the permutation can be arbitrary.
:
: rows
: 上。
|
w********9
发帖数: 8613 | 11 我还是觉得这个问题实用性一般不强。通常的表格都是有定义的，新旧表格的行或列都
有标识，对应和增减应该很容易判断。去掉增减部分，比较其它的修改部分应该不难。
如果每个表格内的单元数据值重复性不强，这个问题就不难。转化成file的比较就可以
了。
1. 把表格的每行变成一行（单元用独特的符号隔离），比较后得出行的增减情况；
2. 按列再做一次；
3. 同时去除增减的行和列后做两表对应单元的比较。
一般的问题不简单。尤其是要求保证能找出一个最佳解（和找出所有最佳解应该没有区
别）。 |
