GOPHERSPACE.DE - P H O X Y
gophering on hngopher.com
HN Gopher Feed (2017-07-03) - page 1 of 10
 
___________________________________________________________________
Myers Diff Algorithm - Code and Interactive Visualization
99 points by robertelder
http://blog.robertelder.org/diff-algorithm/
___________________________________________________________________
 
fny - 1 hours ago
My God that code is terrifying. It looks like output from a code
obfuscator.
 
taeric - 5 hours ago
Haven't read it yet.  Curious about the implication of the title.
Expecting article to be that it could be asymptotically faster, but
practically slower. :)  (That probably says more about how I choose
to read headlines than anything else.)Edit: Read the article now.
Incredibly happy to see that the implication was on purpose.  :)
 
rajathagasthya - 3 hours ago
Another explanation of Myers diff algorithm that I found
interesting: https://blog.jcoglan.com/2017/02/12/the-myers-diff-
algorithm...
 
gefh - 4 hours ago
I don't want a diff algorithm that finds the mathematically
smallest edit distance, I want one that preserves meaningful chunks
of code. I never delete the closing } from one function and then
the entire function following it except its last }.
 
  adekok - 3 hours ago
  i.e.:1) convert code sample 1 to AST 2) convert code sample 2 to
  AST 3) do text-based diffs while paying attention to the ASTsA
  closing brace is really part of the function started by the
  function definition and opening brace.  As such, a closing brace
  from function X should never "match" an opening brace from
  function Y.I imagine that simple chopping code into multiple text
  blocks, one for each function, before passing it to a "diff"
  routine would accomplish most of that.  After all, we already
  chop code into text blocks by filename...
 
    slavik81 - 2 hours ago
    Chopping up the code by function is not enough. The same
    problem exists for blocks within functions, like with a
    sequence of if statements.
 
      adekok - 2 hours ago
      Yes... that should go without saying.
 
  taeric - 4 hours ago
  This is a bit of a holy grail, that in practice isn't actually
  that important.  https://stackoverflow.com/questions/523307
  /semantic-diff-uti... has a good overview of some of the
  possibilities.Makes for amazing demos.  Might some day be what we
  are all using.  My hopes have been dampened severely by how long
  this has taken to make any head way.  (And, honestly, it couples
  your diff tool to the rest of your tool chain rather heavily.  I
  can see why it has a hard time taking off.)
 
    ProblemFactory - 4 hours ago
    I think you could get 90% of the utility of semantic syntax
    tree diff by standard text diff + some simple rules.For example
    preferring to split on empty (whitespace-only) lines. Almost
    all languages and coding styles use empty lines as a "semantic
    separator" marker.
 
    zaptheimpaler - 4 hours ago
    As a newbie to how diff-ing is done in production, does git use
    vanilla edit-distance diffing too?
 
      peff - 4 hours ago
      Git uses Myers diff, but recently added some heuristics to
      "shift" the hunks in semantically meaningful ways. See
      https://github.com/mhagger/diff-slider-tools for the
      experiments that led to this feature.It also supports a few
      other diff algorithms: `--patience` and `--histogram`, but in
      my experience they produce the same output as Myers in most
      cases.
 
  srean - 3 hours ago
  A plausible approach would be to instrument the editor to log
  'edit -events'. Then one could fit/learn an appropriate
  probabilistic model/grammar. After that given two pieces of text
  A and B it becomes a question of finding the most probable edits
  that takes you from A to B.This is far from a new idea. Age old
  Levenstein distance can be seen as a special case. Here the edit
  model is very simple. All letter addition, deletion, and
  substitutions are equally likely. More realistic a model one uses
  the better the results will look like provided one has enough
  data to train.One could train models for specific languages
  (natural as well as programming). If we have language specific
  syntax highlighting, why not language specific edit models. One
  could do personalized models, etc etc.
 
s_bywater - 1 hours ago
Wweereee
 
pbnjay - 2 hours ago
This algorithm is actually really useful in genomic sequencing -
daily usage for me right now. Cool to see it pop up here, although
I think it's less generally useful than other edit distance
methods.