Authors
Anna Harutyunyan, Glencora Borradaile, Chris Chambers, & Christopher Scaffidi
Abstract
Users often need to test, debug or reuse spreadsheets. We present a new algorithm that can identify differences between two spreadsheets, providing a basis for future tools to help users compare two versions of a spreadsheet (thereby seeing what is new and needs testing) or two different spreadsheets (thereby seeing which is more appropriate for reuse in a situation).
This algorithm, RowColAlign, is a two-dimensional generalization of the classic dynamic programming algorithm for solving the one dimensional longest common subsequence problem.
In addition, we present a new planted model for generating test cases to evaluate this algorithm and others like it, including the greedy SheetDiff algorithm presented in prior work. In our evaluation, our new RowColAlign algorithm made no errors at all on test cases, including test cases comparable to relatively large spreadsheets. Moreover, further analysis revealed that it is unexpected for our new algorithm to make errors except when spreadsheets contain an unrealistically small number of distinct values.
These results are extremely encouraging, revealing our algorithm's potential as the basis for future spreadsheet tools.
Sample
The tool computes the difference between two spreadsheets (as a set of modified/inserted/deleted rows, columns, and cells). Shading indicates where rows and columns differ by insertion/deletion, and grey numbers indicate where individual cells differ due to edits.
Publication
2012, IEEE Symposium on Visual Languages and Human-Centric Computing, October
Full article
Planted-model evaluation of algorithms for identifying differences between spreadsheets
