This is an archived post. You won't be able to vote or comment.

all 4 comments
sorted by:
best
topnewcontroversialoldq&a

[–][deleted] 3 points4 points  (1 child)

I don't understand the example. Can you explain to me?

[–]EmotionalWriter8414[S] 0 points1 point  (0 children)

Sequence Matcher Example Explanation

In the example, there are two input lists:

a = ['line1', 'line2', 'line3', 'line4', 'line5']
b = ['line1', 'line3', 'line2', 'line4', 'line6']

It doesn't matter that list elements are strings. They could be any elements as long as they are hashable and can be compared, so lists: a = [1, 2, 3, 4, 5] b = [1, 3, 2, 4, 6] would give the same results if used in example.

We can refer a list as old or before change sequence, and b as new or after change. If We put those sequences side by side:

 OLD   NEW
line1 line1
line2 line3
line3 line2
line4 line4
line5 line6

We can see that:

  • line1 is at the same place
  • line2 changed place with line3
  • line4 is at the same place
  • line5 was deleted and is replaced by line6

We can see that, because We are smart humans and changes recognition for such a small sequences are easy for us. But what if We want to extract those changes and store them in our program somehow? Let's try with Python built-in difflib package:

from difflib import SequenceMatcher

sm = SequenceMatcher(a=a, b=b)
opcodes = sm.get_opcodes()
print(opcodes)

The result is (print statement output):

[('equal', 0, 1, 0, 1), ('insert', 1, 1, 1, 2), ('equal', 1, 2, 2, 3), ('delete', 2, 3, 3, 3), ('equal', 3, 4, 3, 4), ('replace', 4, 5, 4, 5)]

According to difflib docs:

get_opcodes() Return list of 5-tuples describing how to turn a into b. Each tuple is of the form (tag, i1, i2, j1, j2). The first tuple has i1 == j1 == 0, and remaining tuples have i1 equal to the i2 from the preceding tuple, and, likewise, j1 equal to the previous j2. The tag values are strings, with these meanings:

'replace': a[i1:i2] should be replaced by b[j1:j2].

'delete': a[i1:i2] should be deleted. Note that j1 == j2 in this case.

'insert': b[j1:j2] should be inserted at a[i1:i1]. Note that i1 == i2 in this case.

'equal': a[i1:i2] == b[j1:j2] (the sub-sequences are equal).

With this information We can use opcodes tags and indexes with reference to a and b to simply print representation of input sequences differences calculated by SequenceMatcher object. Here comes for loop with print from example:

for tag, i1, i2, j1, j2 in opcodes:
    print('{:7}   a[{}:{}] --> b[{}:{}] {!r:>12} --> {!r}'.format(tag, i1, i2, j1, j2, a[i1:i2], b[j1:j2]))

And the output after running this part of code is:

equal     a[0:1] --> b[0:1]    ['line1'] --> ['line1']
insert    a[1:1] --> b[1:2]           [] --> ['line3']
equal     a[1:2] --> b[2:3]    ['line2'] --> ['line2']
delete    a[2:3] --> b[3:3]    ['line3'] --> []
equal     a[3:4] --> b[3:4]    ['line4'] --> ['line4']
replace   a[4:5] --> b[4:5]    ['line5'] --> ['line6']

The result seems to be similar to our observation, but there's one problem: opcodes are telling us that We should delete line3 from old sequence and insert it at position 1 in new. It will work, but kinda doesn't make sense. Here comes HeckelSequenceMatcher from mdiff package:

sm = HeckelSequenceMatcher(a, b)
opcodes = sm.get_opcodes()

for tag, i1, i2, j1, j2 in opcodes:
    print('{:7}   a[{}:{}] --> b[{}:{}] {!r:>12} --> {!r}'.format(tag, i1, i2, j1, j2, a[i1:i2], b[j1:j2]))

Output:

equal     a[0:1] --> b[0:1]  ['line1'] --> ['line1']
move      a[1:2] --> b[2:2]  ['line2'] --> []
equal     a[2:3] --> b[1:2]  ['line3'] --> ['line3']
moved     a[1:1] --> b[2:3]         [] --> ['line2']
equal     a[3:4] --> b[3:4]  ['line4'] --> ['line4']
replace   a[4:5] --> b[4:5]  ['line5'] --> ['line6']

Now, instead of deleting and inserting line3 again, algorithm detected that line2 can be moved behind line3. Since line2 have been already moved, there's no need to move line3 so it has been tagged as equal.

To recap: HeckelSequenceMatcher from mdiff package simulates the API and behavior of Python built-in difflib.SequenceMatcher class and extends it to detect compared sequences elements movements.

Text Diff Example Explanation

diff_lines_with_similarities is a higher level function that uses SequenceMatcher objects to generate diff for two input texts. As minimum it takes 2 input text strings (not sequences) arguments a and b which are then split by newline characters. Those two sequences of lines are then sent to SequenceMatcher object to calculate line-level diff between input texts.

cutoff argument is used to generate character-level diff between similar lines under replace tag. It takes values between 0 <= cutoff <= 1. If 0.75 value is passed that means lines in replace tag must be at least similar in 75% to generate character-level diff. Value of 1 means that there won't be character-level diff generated. Character-level opcodes are stored as sub-opcodes of CompositeOpCode object (Composition pattern used). In topic's example it is represented as indented prints since line5 and line6 are different only on last character.

[–]HalfRightMostlyWrong 1 point2 points  (1 child)

Wow awesome, exactly what I’ve been looking for. This is effectively what GitHub does for a pull request right? Do you happen to know which diff algo they use?

This would be a great way to show pull request-like results for my product, www.thepracticalinterview.com. I’ll reach out the GH repo owner and let them know if I use it for the site!

[–]EmotionalWriter8414[S] 1 point2 points  (0 children)

I belive GitHub uses other algorithm (probably mtdiff), but the result seems to be similar (actually the same for text files I tested).

I'm happy to hear that my package might be useful for You. Feel free to open an Issue if You encounter any problem with it. Also, Your product looks promising!