Chunking is broken.

[schernichkin]

Chunking will obscure diff results on chunk boundaries if row count does not match.

Steps to reproduce:

1. Create two tables lager then chunk size different in one row (row should be present only in one table, but not in other).
2. Run diff.

Result: Diff will indicate deleted row correctly, but will also report identical row deletion and addition on each chunk boundary after the deleted row.

Excepted result: chunking should not affect diff results.

Just to not bother with enomorous chunks:

1. Change default chunk size to 2.
2. Run

    val lhs = ReportContent(
      Array(Array("No"),
            Array("0"),
            Array("1"),
            Array("2")), 1,1)
    val rhs = ReportContent(
      Array(Array("No"),
        Array("1"),
        Array("2")), 1,1)
    var diff = TableDiff.produceReportDiff(lhs, rhs)
    println(StringTableDiff.diffReportToString(diff))

Result will be:

+----------+
|No        |
+----------+
|[-0-]{+2+}|
|1         |
|[-2-]     |
+----------+

1. Change default chunk back to 1000, run the same program. Result will be:

+-----+
|No   |
+-----+
|[-0-]|
|1    |
|2    |
+-----+

[smootoo]

Thanks for the detailed bug report. I'll get it fixed.

[schernichkin]

As far as I know, longest common subsequence search algorithm, used in TableDiff, does not support any sort of chunking. And it's quite simple to show that such algorithm most likely does not exist at all: for given comparison algorithm of arbitrary complexity which supports chunking, lets split our sequence of n elements to n chunks of size 1. Assuming managing chunks introduces constant complexity, we will end up with linear algorithm. There is no known algorithm for finding shortest edit distance (diff) with linear complexity, hence introducing chunking will always produce inaccurate results or will lead to non-constant chunk management which renders whole idea of chunking pointless.

If we really concerned about quadratic complexity of longest common subsequence search algorithm used by TableDiff and still want accurate results, we should remove chunking completely and consider other algorithm. I think O(NP) is a good candidate, because it claimed to be almost linear when the number of changes is small (most frequent use case of TableDiff is comparing identical or almost identical tables). Here some implementations of O(NP) by various languages.

[schernichkin]

One single note regarding O(NP). O(NP) implementation, discribed in the original paper, does not compute the edit path, it only computes Levenshtein distance. To extract the edit path, which is essential for Diff tool, we should alter original unidirectional implementation to make it bi-directional. Such attemp was made but the final algorithm was claimed to be only 25% faster than the O(ND).

O(ND) is well reseached area and we already have a Java implementation which can be converted to Scala with minimal efforts. Vanilla O(NP) is claimed to be only 2 times faster then O(ND) (P = D/2 − (N − M)/2, but we want to compare similar tables, thus (N − M) will trend to zero). In my opinion we should stick to O(ND) for now.

[smootoo]

This PR fixes the problems joining 2 chunks when rows have been added or deleted. #4
I'll have a look at using a new algorithm as you suggest.