4 ms·

Does anyone know much about prose diff? Very few diff apps work well with prose, and I wonder to what extent this is driven at the level of the algorithm.

nolemurs 10y ago
> I wonder to what extent this is driven at the level of the algorithm. Almost entirely. Most programming diff algorithms operate on a line-by-line basis. That means that a single character change in a line marks the whole line as changed. For prose, a single 'line' is usually a paragraph, so it's pretty obvious why they don't work well. You might check out gnu `wdiff` for what a word-by-word diff could look like. I haven't really looked into the area deeply, so I don't know what the state of the art is.
- rwmj 10y ago
  This makes me wonder if anyone has implemented diff by comparing the Abstract Syntax Trees of the two code-bases. I guess it's probably easier than regular diff (assuming you've already got the ASTs from somewhere).
  - nolemurs 10y ago
    I would think diffing trees would be necessarily more complex than diffing lines - you can think of the line-by-line description of a file as a tree with at most one child per node, so any algorithm for diffing trees should also automatically be able to diff lines. Tree diff algorithms definitely exist (I know React.js uses diffs on a virtual DOM to minimize operations), but I'm not sure what the state of the art is for those.
    - Robin_Message 10y ago
      Tree diff varies between O(N^2) and O(N^4) for simple solutions of varying complexity of matches possible, with a complex fully general algorithms coming in at O(N^2 log^2 N). Tree diff is harder because the range of operations is bigger. React.js cheats by insisting on keys for arrays so matching is much easier.
  - deleted 10y ago
    [deleted]
daxelrod 10y ago
I've maintained prose in git with the default diff algorithm using one sentence per line, and it's worked pretty well. My specific use case was a document tweaked for two different audiences, and I've been able to make changes in one version and rebase the other version on top of it relatively easily.
WorldMaker 10y ago
I've done some explorations here. From the simple perspective, using a fixed width line in a prose markup language that is mostly whitespace agnostic like Markdown creates okay diffs in a line-based diff tool. I did some work with tokenized diffs: https://github.com/WorldMaker/tokdiff https://github.com/WorldMaker/tokdiff That particular tool/experiment uses the Pygments tokenizer used for syntax highlighting and produces interesting somewhat semantically meaningful code diffs. I think the same principles would apply if you used something like a part of speech tagger on prose. From a different approach, I put some effort into better line-based and file-based diffs of Inform 7 which is a prose format that is less whitespace agnostic than Markdown and also built as a single monolithic file, by converting it to an intermediate format. The code that does this is here: https://github.com/WorldMaker/APrincessOfMoons/blob/master/i7stanza.py https://github.com/WorldMaker/APrincessOfMoons/blob/master/i... That works by splitting the file at things that resembles headers, converting newlines to pilcrows (the paragraph symbol), and essentially reformatting to more of a fixed width format. (All of which is trivially reversible.) You can see the commits in that repository as an example of what the intermediate format looks and diffs like. That format handler is written as a plugin to a venerable tool I wrote called musdex: https://github.com/WorldMaker/musdex https://github.com/WorldMaker/musdex I wrote that to better source control zip files as the contents of their zip rather than a binary blob, by letting the zip/unzip operations be automatable as a part of source control operations (pre- and post-commit hooks). This I've used for some of the modern file formats like .docx which are built as zip files of XML files and other assets. For instance, you want write the document in Word, interacting with the .docx, and source control its XML contents. That too gives more useful diffs than source controlling the .docx on its own.
accordionclown 10y ago
in the same way that one-sentence-per-line gives you much more fine-grained diffs than one-paragraph-per-line, notching it down to one-phrase-per-line gives the best results. a simple javascript routine can do that split, and then rejoin the lines after you do a diff. i've written this up extensively, to no notice. http://zenmagiclove.com/simple/breaker.html https://github.com/bbirdiman/breakerbreaker *** i've since found that a dozen changes suffice: replace ". " -- with -- ". \n" replace ", " -- with -- ", \n" replace "? " -- with -- "? \n" replace "! " -- with -- "! \n" replace ": " -- with -- ": \n" replace "; " -- with -- "; \n" replace ") " -- with -- ") \n" replace "] " -- with -- "] \n" replace "} " -- with -- "} \n" replace "-- " -- with -- "-- \n" replace "' " -- with -- "' \n" replace '" ' -- with -- '" \n' *** and, of course, to revert those changes, you simply change " \n" to " " and boom.

nolemurs 10y ago

> I wonder to what extent this is driven at the level of the algorithm. Almost entirely. Most programming diff algorithms operate on a line-by-line basis. That means that a single character change in a line marks the whole line as changed. For prose, a single 'line' is usually a paragraph, so it's pretty obvious why they don't work well. You might check out gnu `wdiff` for what a word-by-word diff could look like. I haven't really looked into the area deeply, so I don't know what the state of the art is.

rwmj 10y ago
This makes me wonder if anyone has implemented diff by comparing the Abstract Syntax Trees of the two code-bases. I guess it's probably easier than regular diff (assuming you've already got the ASTs from somewhere).
- nolemurs 10y ago
  I would think diffing trees would be necessarily more complex than diffing lines - you can think of the line-by-line description of a file as a tree with at most one child per node, so any algorithm for diffing trees should also automatically be able to diff lines. Tree diff algorithms definitely exist (I know React.js uses diffs on a virtual DOM to minimize operations), but I'm not sure what the state of the art is for those.
  - Robin_Message 10y ago
    Tree diff varies between O(N^2) and O(N^4) for simple solutions of varying complexity of matches possible, with a complex fully general algorithms coming in at O(N^2 log^2 N). Tree diff is harder because the range of operations is bigger. React.js cheats by insisting on keys for arrays so matching is much easier.
- deleted 10y ago
  [deleted]

daxelrod 10y ago

I've maintained prose in git with the default diff algorithm using one sentence per line, and it's worked pretty well. My specific use case was a document tweaked for two different audiences, and I've been able to make changes in one version and rebase the other version on top of it relatively easily.

WorldMaker 10y ago

I've done some explorations here. From the simple perspective, using a fixed width line in a prose markup language that is mostly whitespace agnostic like Markdown creates okay diffs in a line-based diff tool. I did some work with tokenized diffs: https://github.com/WorldMaker/tokdiff https://github.com/WorldMaker/tokdiff That particular tool/experiment uses the Pygments tokenizer used for syntax highlighting and produces interesting somewhat semantically meaningful code diffs. I think the same principles would apply if you used something like a part of speech tagger on prose. From a different approach, I put some effort into better line-based and file-based diffs of Inform 7 which is a prose format that is less whitespace agnostic than Markdown and also built as a single monolithic file, by converting it to an intermediate format. The code that does this is here: https://github.com/WorldMaker/APrincessOfMoons/blob/master/i7stanza.py https://github.com/WorldMaker/APrincessOfMoons/blob/master/i... That works by splitting the file at things that resembles headers, converting newlines to pilcrows (the paragraph symbol), and essentially reformatting to more of a fixed width format. (All of which is trivially reversible.) You can see the commits in that repository as an example of what the intermediate format looks and diffs like. That format handler is written as a plugin to a venerable tool I wrote called musdex: https://github.com/WorldMaker/musdex https://github.com/WorldMaker/musdex I wrote that to better source control zip files as the contents of their zip rather than a binary blob, by letting the zip/unzip operations be automatable as a part of source control operations (pre- and post-commit hooks). This I've used for some of the modern file formats like .docx which are built as zip files of XML files and other assets. For instance, you want write the document in Word, interacting with the .docx, and source control its XML contents. That too gives more useful diffs than source controlling the .docx on its own.

accordionclown 10y ago

in the same way that one-sentence-per-line gives you much more fine-grained diffs than one-paragraph-per-line, notching it down to one-phrase-per-line gives the best results. a simple javascript routine can do that split, and then rejoin the lines after you do a diff. i've written this up extensively, to no notice. http://zenmagiclove.com/simple/breaker.html https://github.com/bbirdiman/breakerbreaker *** i've since found that a dozen changes suffice: replace ". " -- with -- ". \n" replace ", " -- with -- ", \n" replace "? " -- with -- "? \n" replace "! " -- with -- "! \n" replace ": " -- with -- ": \n" replace "; " -- with -- "; \n" replace ") " -- with -- ") \n" replace "] " -- with -- "] \n" replace "} " -- with -- "} \n" replace "-- " -- with -- "-- \n" replace "' " -- with -- "' \n" replace '" ' -- with -- '" \n' *** and, of course, to revert those changes, you simply change " \n" to " " and boom.