System and method for computing, applying, and displaying document deltas

Abstract

Systems and methods are disclosed herein for computing, applying, and displaying document deltas. Snapshots are stored of documents, and the stored snapshots are flattened. Deltas of the flattened snapshots are computed. The deltas are converted to representations of changes in the document by inverting the flattening. The representations of changes are displayed to a user via a feed. Users of the systems and methods can accept, reject, and comment on the changes.

We claim: 
     
         1 . A computer-implemented method for sharing information related to a collaborative document hosted on a network storage service, the method comprising:
 storing a first snapshot of the collaborative document;   receiving a first edit to the collaborative document from a first user;   modifying the collaborative document based on the first edit;   storing a second snapshot of the modified collaborative document;   flattening, by a processor, the first snapshot into a first one-dimensional string to result in a first flattened snapshot and the second snapshot into a second one-dimensional string to result in a second flattened snapshot; and   determining a change between the collaborative document and the modified collaborative document based on a comparison of the first flattened snapshot and the second flattened snapshot.   
     
     
         2 . The method of  claim 1 , wherein determining the change between the collaborative document and the modified collaborative document comprises:
 determining a smallest subset of the second flattened snapshot that is different from a corresponding subset of the first flattened snapshot.   
     
     
         3 . The method of  claim 1 , further comprising:
 generating a feed comprising a representation of the change; and   sending the feed to a client device for display on the client device.   
     
     
         4 . The method of  claim 1 , further comprising:
 receiving a second edit to the modified collaborative document from a second user;   further modifying the modified collaborative document based on the second edit;   storing a third snapshot of the further modified collaborative document;   flattening the third snapshot into a third one-dimensional string to result in a third flattened snapshot;   determining a further change between the modified collaborative document and the further modified collaborative document based on a comparison of the second flattened snapshot and the third flattened snapshot;   modifying a feed to include a representation of the further change; and   sending the modified feed to a client device for display on the client device   
     
     
         5 . The method of  claim 1 , further comprising:
 flattening the first snapshot into a fourth one-dimensional string to result in a fourth flattened snapshot;   flattening the second snapshot into a fifth one-dimensional string to result in a fifth flattened snapshot; and   determining a second smallest subset of the fifth flattened snapshot that is different from a corresponding subset of the fourth flattened snapshot, wherein the change is identified in the second smallest subset.   
     
     
         6 . The method of  claim 5 , wherein the collaborative document is a spreadsheet document, wherein the fourth and fifth one-dimensional string each contain a plurality of identifiers, wherein each of the identifiers represents a row or column in the spreadsheet document. 
     
     
         7 . The method of  claim 1 , wherein each snapshot of the collaborative document comprises a hierarchy of nodes including a plurality of levels, one master node, and a plurality of non-master nodes containing data, wherein each of the non-master nodes has a parent node in a level above, wherein each of the nodes has zero, one, or more child nodes in a level below, wherein a number of levels between each node in a level and the master node is a same number,
 wherein flattening the first snapshot into the first one-dimensional string comprises:
 selecting a level of the plurality of levels; 
 mapping a first node in the selected level to a first identifier; and 
 adding the first identifier to the first one-dimensional string; and 
   wherein flattening the second snapshot into the second one-dimensional string comprises:
 mapping a second node in a corresponding selected level of the second snapshot to the first identifier, based on a determination that contents of the second node are the same as contents of the first node, and 
 adding the first identifier to the second one-dimensional string. 
   
     
     
         8 . The method of  claim 7 , wherein flattening the second snapshot into the second one-dimensional string further comprises:
 mapping a third node in a corresponding selected level of the second snapshot to a second identifier based on a determination that the data contained in the third node are different from contents of any of the nodes in the selected level of the first snapshot; and   adding the second identifier to the second one-dimensional string.   
     
     
         9 . A system for sharing information related to a collaborative document hosted on a network storage service, comprising:
 a memory; and   one or more processors, coupled to the memory, to:   store a first snapshot of the collaborative document;
 receive a first edit to the collaborative document from a first user; 
 modify the collaborative document based on the first edit; 
 store a second snapshot of the modified collaborative document; 
   flatten, by the one or more processors, the first snapshot into a first one-dimensional string to result in a first flattened snapshot and the second snapshot into a second one-dimensional string to result in a second flattened snapshot; and   determine a change between the collaborative document and the modified collaborative document based on a comparison of the first flattened snapshot and the second flattened snapshot.   
     
     
         10 . The system of  claim 9 , wherein to determine the change between the collaborative document and the modified collaborative document, the one or more processors to:
 determine a smallest subset of the second flattened snapshot that is different from a corresponding subset of the first flattened snapshot.   
     
     
         11 . The system of  claim 9 , the one or more processors further to:
 receive a second edit to the modified collaborative document from a second user;   further modify the modified collaborative document based on the second edit;   store a third snapshot of the further modified collaborative document;   flatten the third snapshot into a third one-dimensional string to result in a third flattened snapshot;   determine a further change between the modified collaborative document and the further modified collaborative document based on a comparison of the second flattened snapshot and the third flattened snapshot; and   modify a feed to include a representation of the further change; and   send the modified feed to a client device for display on the client device.   
     
     
         12 . The system of  claim 10 , the one or more processors further to:
 flatten the first snapshot into a fourth one-dimensional string to result in a fourth flattened snapshot;   flatten the second snapshot into a fifth one-dimensional string to result in a fifth flattened snapshot; and   determine a second smallest subset of the fifth flattened snapshot that is different from a corresponding subset of the fourth flattened snapshot, wherein the determined smallest subset is the second smallest subset.   
     
     
         13 . The system of  claim 12 , wherein the collaborative document is a spreadsheet document, wherein the fourth and fifth one-dimensional string each contain a plurality of identifiers, wherein each of the identifiers represents a row or column in the spreadsheet document. 
     
     
         14 . The system of  claim 10 , wherein each snapshot of the collaborative document comprises a hierarchy of nodes including a plurality of levels, one master node, and a plurality of non-master nodes containing data, wherein each of the non-master nodes has a parent node in a level above, wherein each of the nodes has zero, one, or more child nodes in a level below, wherein a number of levels between each node in a level and the master node is a same number; wherein to flatten the first snapshot into the first one-dimensional string, the one or more processors to:
 select a level of the plurality of levels;   map a first node in the selected level to a first identifier; and   add the first identifier to the first one-dimensional string; and   wherein to flatten the second snapshot into the second one-dimensional string, the one or more processors to:   map a second node in a corresponding selected level of the second snapshot to the first identifier, based on a determination that contents of the second node are the same as contents of the first node; and   add the first identifier to the second one-dimensional string.   
     
     
         15 . The system of  claim 14 , wherein to flatten the second snapshot into the second one-dimensional string further, the one or more processor to:
 map a third node in a corresponding selected level of the second snapshot to a second identifier, based on a determination that the data contained in the third node are different from contents of any of the nodes in the selected level of the first snapshot; and   add the second identifier to the second one-dimensional string.   
     
     
         16 . The system of  claim 14 , wherein to determine the smallest subset, the one or more processors to:
 determine that the first one-dimensional string and the second one-dimensional string contain the first identifier; and   exclude the first identifier from the smallest subset.   
     
     
         17 . The system of  claim 15  wherein to determine the smallest subset the one or more processors to:
 determine that the first one-dimensional string does not contain the second identifier; and 
 include the second identifier in the smallest subset. 
 
     
     
         18 . A non-transitory computer-readable medium comprising instructions that, responsive to being executed by a processor, causing the processor to perform operations comprising:
 storing a first snapshot of a collaborative document;   receiving a first edit to the collaborative document from a first user;   modifying the collaborative document based on the first edit;   storing a second snapshot of the modified collaborative document;   flattening, by a processor, the first snapshot into a first one-dimensional string to result in a first flattened snapshot and the second snapshot into a second one-dimensional string to result in a second flattened snapshot; and   determining a change between the collaborative document and the modified collaborative document based on a comparison of the first flattened snapshot and the second flattened snapshot.   
     
     
         19 . The non-transitory computer-readable medium of  claim 18 , wherein determining the change between the collaborative document and the modified collaborative document comprises:
 determining a smallest subset of the second flattened snapshot that is different from a corresponding subset of the first flattened snapshot.   
     
     
         20 . The non-transitory computer-readable medium of  claim 18 , further comprising:
 generating a feed comprising a representation of the change; and   sending the feed to a client device for display on the client device.