1*01826a49SYabin Cui## Edit Distance Match Finder 2*01826a49SYabin Cui 3*01826a49SYabin Cui``` 4*01826a49SYabin Cui/* This match finder leverages techniques used in file comparison algorithms 5*01826a49SYabin Cui * to find matches between a dictionary and a source file. 6*01826a49SYabin Cui * 7*01826a49SYabin Cui * The original motivation for studying this approach was to try and optimize 8*01826a49SYabin Cui * Zstandard for the use case of patching: the most common scenario being 9*01826a49SYabin Cui * updating an existing software package with the next version. When patching, 10*01826a49SYabin Cui * the difference between the old version of the package and the new version 11*01826a49SYabin Cui * is generally tiny (most of the new file will be identical to 12*01826a49SYabin Cui * the old one). In more technical terms, the edit distance (the minimal number 13*01826a49SYabin Cui * of changes required to take one sequence of bytes to another) between the 14*01826a49SYabin Cui * files would be small relative to the size of the file. 15*01826a49SYabin Cui * 16*01826a49SYabin Cui * Various 'diffing' algorithms utilize this notion of edit distance and 17*01826a49SYabin Cui * the corresponding concept of a minimal edit script between two 18*01826a49SYabin Cui * sequences to identify the regions within two files where they differ. 19*01826a49SYabin Cui * The core algorithm used in this match finder is described in: 20*01826a49SYabin Cui * 21*01826a49SYabin Cui * "An O(ND) Difference Algorithm and its Variations", Eugene W. Myers, 22*01826a49SYabin Cui * Algorithmica Vol. 1, 1986, pp. 251-266, 23*01826a49SYabin Cui * <https://doi.org/10.1007/BF01840446>. 24*01826a49SYabin Cui * 25*01826a49SYabin Cui * Additional algorithmic heuristics for speed improvement have also been included. 26*01826a49SYabin Cui * These we inspired from implementations of various regular and binary diffing 27*01826a49SYabin Cui * algorithms such as GNU diff, bsdiff, and Xdelta. 28*01826a49SYabin Cui * 29*01826a49SYabin Cui * Note: after some experimentation, this approach proved to not provide enough 30*01826a49SYabin Cui * utility to justify the additional CPU used in finding matches. The one area 31*01826a49SYabin Cui * where this approach consistently outperforms Zstandard even on level 19 is 32*01826a49SYabin Cui * when compressing small files (<10 KB) using an equally small dictionary that 33*01826a49SYabin Cui * is very similar to the source file. For the use case that this was intended, 34*01826a49SYabin Cui * (large similar files) this approach by itself took 5-10X longer than zstd-19 and 35*01826a49SYabin Cui * generally resulted in 2-3X larger files. The core advantage that zstd-19 has 36*01826a49SYabin Cui * over this approach for match finding is the overlapping matches. This approach 37*01826a49SYabin Cui * cannot find any. 38*01826a49SYabin Cui * 39*01826a49SYabin Cui * I'm leaving this in the contrib section in case this ever becomes interesting 40*01826a49SYabin Cui * to explore again. 41*01826a49SYabin Cui * */ 42*01826a49SYabin Cui``` 43