| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -13,49 +13,86 @@ | |||
| 13 | 13 | ||
| 14 | 14 | -------------- | |
| 15 | 15 | ||
| 16 | - This module provides classes and functions for comparing sequences. It | ||
| 17 | - can be used for example, for comparing files, and can produce information | ||
| 18 | - about file differences in various formats, including HTML and context and unified | ||
| 19 | - diffs. For comparing directories and files, see also, the :mod:`filecmp` module. | ||
| 20 | - | ||
| 21 | - | ||
| 22 | - .. class:: SequenceMatcher | ||
| 23 | - :noindex: | ||
| 24 | - | ||
| 25 | - This is a flexible class for comparing pairs of sequences of any type, so long | ||
| 26 | - as the sequence elements are :term:`hashable`. The basic algorithm predates, and is a | ||
| 27 | - little fancier than, an algorithm published in the late 1980's by Ratcliff and | ||
| 28 | - Obershelp under the hyperbolic name "gestalt pattern matching." The idea is to | ||
| 29 | - find the longest contiguous matching subsequence that contains no "junk" | ||
| 30 | - elements; these "junk" elements are ones that are uninteresting in some | ||
| 31 | - sense, such as blank lines or whitespace. (Handling junk is an | ||
| 32 | - extension to the Ratcliff and Obershelp algorithm.) The same | ||
| 33 | - idea is then applied recursively to the pieces of the sequences to the left and | ||
| 34 | - to the right of the matching subsequence. This does not yield minimal edit | ||
| 35 | - sequences, but does tend to yield matches that "look right" to people. | ||
| 36 | - | ||
| 37 | - **Timing:** The basic Ratcliff-Obershelp algorithm is cubic time in the worst | ||
| 38 | - case and quadratic time in the expected case. :class:`SequenceMatcher` is | ||
| 39 | - quadratic time for the worst case and has expected-case behavior dependent in a | ||
| 40 | - complicated way on how many elements the sequences have in common; best case | ||
| 41 | - time is linear. | ||
| 42 | - | ||
| 43 | - **Junk**: :class:`SequenceMatcher` accepts an ``isjunk`` predicate and an | ||
| 44 | - ``autojunk`` flag. Items that are considered as junk will not be considered | ||
| 45 | - to find similar content blocks. This can produce better results for humans | ||
| 46 | - (typically breaking on whitespace) and faster (because it reduces the number | ||
| 47 | - of possible combinations). But it can also cause pathological cases where | ||
| 48 | - too many items considered junk cause an unexpectedly large (but correct) | ||
| 49 | - diff result. | ||
| 50 | - You should consider tuning them or turning them off depending on your data. | ||
| 51 | - Moreover, only the second sequence is inspected for junk. This causes the diff | ||
| 52 | - output to not be symmetrical. | ||
| 53 | - When ``autojunk=True``, it will consider as junk the items that account for more | ||
| 54 | - than 1% of the sequence, if it is at least 200 items long. | ||
| 16 | + This module provides classes and functions for comparing sequences. | ||
| 17 | + Most of them compare sequences of text lines (for example lists of strings, | ||
| 18 | + or :term:`file objects <file object>`) and | ||
| 19 | + produce :dfn:`diffs` -- reports on the differences. | ||
| 20 | + Diffs can be produced in in various formats, including HTML and context | ||
| 21 | + and unified diffs -- formats produced by tools like | ||
| 22 | + :manpage:`diff <diff(1)>` and :manpage:`git diff <git-diff(1)>`. | ||
| 55 | 23 | ||
| 56 | - .. versionchanged:: 3.2 | ||
| 57 | - Added the *autojunk* parameter. | ||
| 24 | + Comparisons are done using a matching algorithm implemented in | ||
| 25 | + :class:`SequenceMatcher` -- a flexible class for comparing pairs of sequences | ||
| 26 | + of any type, not just text, so long as the sequence elements are | ||
| 27 | + :term:`hashable`. | ||
| 28 | + | ||
| 29 | + | ||
| 30 | + .. _difflib-junk: | ||
| 31 | + | ||
| 32 | + Junk heuristic | ||
| 33 | + -------------- | ||
| 34 | + | ||
| 35 | + :mod:`!difflib` uses a :dfn:`junk` heuristic: some items are deemed to be | ||
| 36 | + :dfn:`junk`, and ignored when searching for similarities. | ||
| 37 | + Ideally, these are uninteresting or common items, such as blank lines | ||
| 38 | + or whitespace. | ||
| 39 | + | ||
| 40 | + This heuristic can speed the algorithm up (because it reduces the number of | ||
| 41 | + possible combinations) and it can produce results that are more understandable | ||
| 42 | + for humans (typically breaking on whitespace). | ||
| 43 | + But it can also cause pathological cases: | ||
| 44 | + | ||
| 45 | + - Inappropriately chosen junk items can cause an unexpectedly **large** (but | ||
| 46 | + still correct) result. | ||
| 47 | + - The default heuristic is **asymmetric**: only the second sequence is | ||
| 48 | + inspected when determining what is considered junk, so comparing A to B can | ||
| 49 | + give different results than comparing B to A and reversing the result. | ||
| 50 | + | ||
| 51 | + By default, if the second input sequence is at least 200 items long, items | ||
| 52 | + that account for more than 1% it are considered *junk*. | ||
| 53 | + | ||
| 54 | + Depending on your data, you should consider turning this heuristic off | ||
| 55 | + (setting :class:`~difflib.SequenceMatcher`'s *autojunk* argument to to ``False``) | ||
| 56 | + or tuning it (using the *isjunk* argument, perhaps to one of the | ||
| 57 | + :ref:`predefined functions <difflib-isjunk-functions>`). | ||
| 58 | + | ||
| 59 | + | ||
| 60 | + The :mod:`!difflib` algorithm | ||
| 61 | + ----------------------------- | ||
| 62 | + | ||
| 63 | + The algorithm used in :class:`SequenceMatcher` predates, and is a little | ||
| 64 | + fancier than, an algorithm published in the late 1980s by Ratcliff and | ||
| 65 | + Obershelp under the hyperbolic name "gestalt pattern matching." | ||
| 66 | + The idea is to find the longest contiguous subsequence common to both inputs, | ||
| 67 | + then recursively handle the pieces of the sequences to the left and to the | ||
| 68 | + right of the matching subsequence. | ||
| 69 | + | ||
| 70 | + .. seealso:: | ||
| 71 | + | ||
| 72 | + `Pattern Matching: The Gestalt Approach <https://jacobfilipp.com/DrDobbs/articles/DDJ/1988/8807/8807c/8807c.htm>`_ | ||
| 73 | + Discussion of a similar algorithm by John W. Ratcliff and D. E. Metzener. This | ||
| 74 | + was published in Dr. Dobb's Journal in July, 1988. | ||
| 75 | + | ||
| 76 | + As an extension to the Ratcliff and Obershelp algorithm, :mod:`!difflib` | ||
| 77 | + searches for the longest *junk-free* contiguous subsequence. | ||
| 78 | + See the :ref:`difflib-junk` section for details. | ||
| 79 | + | ||
| 80 | + .. impl-detail:: Timing | ||
| 58 | 81 | ||
| 82 | + The basic Ratcliff-Obershelp algorithm is cubic time in the worst | ||
| 83 | + case and quadratic time in the expected case. | ||
| 84 | + :mod:`difflib`'s algorithm is quadratic time for the worst case and has | ||
| 85 | + expected-case behavior dependent in a complicated way on how many elements | ||
| 86 | + the sequences have in common; | ||
| 87 | + best case time is linear. | ||
| 88 | + | ||
| 89 | + | ||
| 90 | + .. _difflib-diff-generation: | ||
| 91 | + | ||
| 92 | + Diff generation | ||
| 93 | + --------------- | ||
| 94 | + | ||
| 95 | + .. _differ-objects: | ||
| 59 | 96 | ||
| 60 | 97 | .. class:: Differ | |
| 61 | 98 | ||
@@ -82,6 +119,47 @@ diffs. For comparing directories and files, see also, the :mod:`filecmp` module. | |||
| 82 | 119 | and were not present in either input sequence. These lines can be confusing if | |
| 83 | 120 | the sequences contain whitespace characters, such as spaces, tabs or line breaks. | |
| 84 | 121 | ||
| 122 | + Note that :class:`Differ`\ -generated deltas make no claim to be **minimal** | ||
| 123 | + diffs. To the contrary, minimal diffs are often counter-intuitive for humans, | ||
| 124 | + because they synch up anywhere possible, sometimes at accidental matches | ||
| 125 | + 100 pages apart. | ||
| 126 | + Restricting synch points to contiguous matches preserves some notion of | ||
| 127 | + locality, at the occasional cost of producing a longer diff. | ||
| 128 | + | ||
| 129 | + The :class:`Differ` class has this constructor: | ||
| 130 | + | ||
| 131 | + .. method:: __init__(linejunk=None, charjunk=None) | ||
| 132 | + | ||
| 133 | + Optional keyword parameters *linejunk* and *charjunk* are for filter functions | ||
| 134 | + (or ``None``): | ||
| 135 | + | ||
| 136 | + *linejunk*: A function that accepts a single string argument, and returns true | ||
| 137 | + if the string is junk. The default is ``None``, meaning that no line is | ||
| 138 | + considered junk. | ||
| 139 | + | ||
| 140 | + *charjunk*: A function that accepts a single character argument (a string of | ||
| 141 | + length 1), and returns true if the character is junk. The default is ``None``, | ||
| 142 | + meaning that no character is considered junk. | ||
| 143 | + | ||
| 144 | + These junk-filtering functions speed up matching to find | ||
| 145 | + differences and do not cause any differing lines or characters to | ||
| 146 | + be ignored. Read the description of the | ||
| 147 | + :meth:`~SequenceMatcher.find_longest_match` method's *isjunk* | ||
| 148 | + parameter for an explanation. | ||
| 149 | + | ||
| 150 | + :class:`Differ` objects are used (deltas generated) via a single method: | ||
| 151 | + | ||
| 152 | + | ||
| 153 | + .. method:: Differ.compare(a, b) | ||
| 154 | + | ||
| 155 | + Compare two sequences of lines, and generate the delta (a sequence of lines). | ||
| 156 | + | ||
| 157 | + Each sequence must contain individual single-line strings ending with | ||
| 158 | + newlines. Such sequences can be obtained from the | ||
| 159 | + :meth:`~io.IOBase.readlines` method of file-like objects. The generated | ||
| 160 | + delta also consists of newline-terminated strings, ready to be | ||
| 161 | + printed as-is via the :meth:`~io.IOBase.writelines` method of a | ||
| 162 | + file-like object. | ||
| 85 | 163 | ||
| 86 | 164 | .. class:: HtmlDiff | |
| 87 | 165 | ||
@@ -349,6 +427,12 @@ diffs. For comparing directories and files, see also, the :mod:`filecmp` module. | |||
| 349 | 427 | ||
| 350 | 428 | .. versionadded:: 3.5 | |
| 351 | 429 | ||
| 430 | + | ||
| 431 | + .. _difflib-isjunk-functions: | ||
| 432 | + | ||
| 433 | + Junk definition functions | ||
| 434 | + ------------------------- | ||
| 435 | + | ||
| 352 | 436 | .. function:: IS_LINE_JUNK(line) | |
| 353 | 437 | ||
| 354 | 438 | Return ``True`` for ignorable lines. The line *line* is ignorable if *line* is | |
@@ -363,21 +447,11 @@ diffs. For comparing directories and files, see also, the :mod:`filecmp` module. | |||
| 363 | 447 | parameter *charjunk* in :func:`ndiff`. | |
| 364 | 448 | ||
| 365 | 449 | ||
| 366 | - .. seealso:: | ||
| 367 | - | ||
| 368 | - `Pattern Matching: The Gestalt Approach <https://jacobfilipp.com/DrDobbs/articles/DDJ/1988/8807/8807c/8807c.htm>`_ | ||
| 369 | - Discussion of a similar algorithm by John W. Ratcliff and D. E. Metzener. This | ||
| 370 | - was published in Dr. Dobb's Journal in July, 1988. | ||
| 371 | - | ||
| 372 | - | ||
| 373 | 450 | .. _sequence-matcher: | |
| 374 | 451 | ||
| 375 | 452 | SequenceMatcher objects | |
| 376 | 453 | ----------------------- | |
| 377 | 454 | ||
| 378 | - The :class:`SequenceMatcher` class has this constructor: | ||
| 379 | - | ||
| 380 | - | ||
| 381 | 455 | .. class:: SequenceMatcher(isjunk=None, a='', b='', autojunk=True) | |
| 382 | 456 | ||
| 383 | 457 | Optional argument *isjunk* must be ``None`` (the default) or a one-argument | |
@@ -588,10 +662,13 @@ are always at least as large as :meth:`~SequenceMatcher.ratio`: | |||
| 588 | 662 | 1.0 | |
| 589 | 663 | ||
| 590 | 664 | ||
| 665 | + Examples | ||
| 666 | + -------- | ||
| 667 | + | ||
| 591 | 668 | .. _sequencematcher-examples: | |
| 592 | 669 | ||
| 593 | 670 | SequenceMatcher examples | |
| 594 | - ------------------------ | ||
| 671 | + ........................ | ||
| 595 | 672 | ||
| 596 | 673 | This example compares two strings, considering blanks to be "junk": | |
| 597 | 674 | ||
@@ -639,59 +716,10 @@ If you want to know how to change the first sequence into the second, use | |||
| 639 | 716 | built with :class:`SequenceMatcher`. | |
| 640 | 717 | ||
| 641 | 718 | ||
| 642 | - .. _differ-objects: | ||
| 643 | - | ||
| 644 | - Differ objects | ||
| 645 | - -------------- | ||
| 646 | - | ||
| 647 | - Note that :class:`Differ`\ -generated deltas make no claim to be **minimal** | ||
| 648 | - diffs. To the contrary, minimal diffs are often counter-intuitive, because they | ||
| 649 | - synch up anywhere possible, sometimes accidental matches 100 pages apart. | ||
| 650 | - Restricting synch points to contiguous matches preserves some notion of | ||
| 651 | - locality, at the occasional cost of producing a longer diff. | ||
| 652 | - | ||
| 653 | - The :class:`Differ` class has this constructor: | ||
| 654 | - | ||
| 655 | - | ||
| 656 | - .. class:: Differ(linejunk=None, charjunk=None) | ||
| 657 | - :noindex: | ||
| 658 | - | ||
| 659 | - Optional keyword parameters *linejunk* and *charjunk* are for filter functions | ||
| 660 | - (or ``None``): | ||
| 661 | - | ||
| 662 | - *linejunk*: A function that accepts a single string argument, and returns true | ||
| 663 | - if the string is junk. The default is ``None``, meaning that no line is | ||
| 664 | - considered junk. | ||
| 665 | - | ||
| 666 | - *charjunk*: A function that accepts a single character argument (a string of | ||
| 667 | - length 1), and returns true if the character is junk. The default is ``None``, | ||
| 668 | - meaning that no character is considered junk. | ||
| 669 | - | ||
| 670 | - These junk-filtering functions speed up matching to find | ||
| 671 | - differences and do not cause any differing lines or characters to | ||
| 672 | - be ignored. Read the description of the | ||
| 673 | - :meth:`~SequenceMatcher.find_longest_match` method's *isjunk* | ||
| 674 | - parameter for an explanation. | ||
| 675 | - | ||
| 676 | - :class:`Differ` objects are used (deltas generated) via a single method: | ||
| 677 | - | ||
| 678 | - | ||
| 679 | - .. method:: Differ.compare(a, b) | ||
| 680 | - | ||
| 681 | - Compare two sequences of lines, and generate the delta (a sequence of lines). | ||
| 682 | - | ||
| 683 | - Each sequence must contain individual single-line strings ending with | ||
| 684 | - newlines. Such sequences can be obtained from the | ||
| 685 | - :meth:`~io.IOBase.readlines` method of file-like objects. The delta | ||
| 686 | - generated also consists of newline-terminated strings, ready to be | ||
| 687 | - printed as-is via the :meth:`~io.IOBase.writelines` method of a | ||
| 688 | - file-like object. | ||
| 689 | - | ||
| 690 | - | ||
| 691 | 719 | .. _differ-examples: | |
| 692 | 720 | ||
| 693 | 721 | Differ example | |
| 694 | - -------------- | ||
| 722 | + .............. | ||
| 695 | 723 | ||
| 696 | 724 | This example compares two texts. First we set up the texts, sequences of | |
| 697 | 725 | individual single-line strings ending with newlines (such sequences can also be | |
@@ -758,14 +786,14 @@ As a single multi-line string it looks like this: | |||
| 758 | 786 | .. _difflib-interface: | |
| 759 | 787 | ||
| 760 | 788 | A command-line interface to difflib | |
| 761 | - ----------------------------------- | ||
| 789 | + ................................... | ||
| 762 | 790 | ||
| 763 | 791 | This example shows how to use difflib to create a ``diff``-like utility. | |
| 764 | 792 | ||
| 765 | 793 | .. literalinclude:: ../includes/diff.py | |
| 766 | 794 | ||
| 767 | 795 | ndiff example | |
| 768 | - ------------- | ||
| 796 | + ............. | ||
| 769 | 797 | ||
| 770 | 798 | This example shows how to use :func:`difflib.ndiff`. | |
| 771 | 799 | ||
| Back | FazBrowse Home | New Git URL |
0 commit comments