cpython-lru_cache-weakref: Lib/difflib.py annotate

annotate Lib/difflib.py @ 17581:c1937faabb23 2.1

Added support for optional explanation parameter to the \versionadded macro. Refactored do_cmd_versionadded() and do_cmd_versionchanged() to do most of the work in a helper function, with the do_cmd_*() wrappers just supplying a portion of the replacement text.

author	Fred Drake <fdrake@acm.org>
date	Wed, 18 Apr 2001 17:29:14 +0000
parents	8172906c6dc8
children	50fb4683a461

rev	line source
16551 7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	1 #! /usr/bin/env python
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	2
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	3 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	4 Module difflib -- helpers for computing deltas between objects.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	5
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	6 Function get_close_matches(word, possibilities, n=3, cutoff=0.6):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	7
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	8 Use SequenceMatcher to return list of the best "good enough" matches.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	9
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	10 word is a sequence for which close matches are desired (typically a
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	11 string).
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	12
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	13 possibilities is a list of sequences against which to match word
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	14 (typically a list of strings).
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	15
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	16 Optional arg n (default 3) is the maximum number of close matches to
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	17 return. n must be > 0.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	18
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	19 Optional arg cutoff (default 0.6) is a float in [0, 1]. Possibilities
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	20 that don't score at least that similar to word are ignored.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	21
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	22 The best (no more than n) matches among the possibilities are returned
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	23 in a list, sorted by similarity score, most similar first.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	24
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	25 >>> get_close_matches("appel", ["ape", "apple", "peach", "puppy"])
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	26 ['apple', 'ape']
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	27 >>> import keyword
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	28 >>> get_close_matches("wheel", keyword.kwlist)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	29 ['while']
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	30 >>> get_close_matches("apple", keyword.kwlist)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	31 []
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	32 >>> get_close_matches("accept", keyword.kwlist)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	33 ['except']
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	34
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	35 Class SequenceMatcher
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	36
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	37 SequenceMatcher is a flexible class for comparing pairs of sequences of any
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	38 type, so long as the sequence elements are hashable. The basic algorithm
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	39 predates, and is a little fancier than, an algorithm published in the late
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	40 1980's by Ratcliff and Obershelp under the hyperbolic name "gestalt pattern
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	41 matching". The basic idea is to find the longest contiguous matching
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	42 subsequence that contains no "junk" elements (R-O doesn't address junk).
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	43 The same idea is then applied recursively to the pieces of the sequences to
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	44 the left and to the right of the matching subsequence. This does not yield
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	45 minimal edit sequences, but does tend to yield matches that "look right"
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	46 to people.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	47
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	48 Example, comparing two strings, and considering blanks to be "junk":
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	49
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	50 >>> s = SequenceMatcher(lambda x: x == " ",
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	51 ... "private Thread currentThread;",
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	52 ... "private volatile Thread currentThread;")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	53 >>>
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	54
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	55 .ratio() returns a float in [0, 1], measuring the "similarity" of the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	56 sequences. As a rule of thumb, a .ratio() value over 0.6 means the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	57 sequences are close matches:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	58
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	59 >>> print round(s.ratio(), 3)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	60 0.866
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	61 >>>
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	62
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	63 If you're only interested in where the sequences match,
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	64 .get_matching_blocks() is handy:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	65
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	66 >>> for block in s.get_matching_blocks():
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	67 ... print "a[%d] and b[%d] match for %d elements" % block
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	68 a[0] and b[0] match for 8 elements
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	69 a[8] and b[17] match for 6 elements
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	70 a[14] and b[23] match for 15 elements
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	71 a[29] and b[38] match for 0 elements
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	72
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	73 Note that the last tuple returned by .get_matching_blocks() is always a
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	74 dummy, (len(a), len(b), 0), and this is the only case in which the last
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	75 tuple element (number of elements matched) is 0.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	76
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	77 If you want to know how to change the first sequence into the second, use
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	78 .get_opcodes():
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	79
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	80 >>> for opcode in s.get_opcodes():
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	81 ... print "%6s a[%d:%d] b[%d:%d]" % opcode
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	82 equal a[0:8] b[0:8]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	83 insert a[8:8] b[8:17]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	84 equal a[8:14] b[17:23]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	85 equal a[14:29] b[23:38]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	86
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	87 See Tools/scripts/ndiff.py for a fancy human-friendly file differencer,
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	88 which uses SequenceMatcher both to view files as sequences of lines, and
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	89 lines as sequences of characters.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	90
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	91 See also function get_close_matches() in this module, which shows how
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	92 simple code building on SequenceMatcher can be used to do useful work.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	93
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	94 Timing: Basic R-O is cubic time worst case and quadratic time expected
16703 8172906c6dc8 Improve accuracy. In the .tex file, note the new "% BUG:" comments: an Tim Peters <tim.peters@gmail.com> parents: 16695 diff changeset	95 case. SequenceMatcher is quadratic time for the worst case and has
8172906c6dc8 Improve accuracy. In the .tex file, note the new "% BUG:" comments: an Tim Peters <tim.peters@gmail.com> parents: 16695 diff changeset	96 expected-case behavior dependent in a complicated way on how many
8172906c6dc8 Improve accuracy. In the .tex file, note the new "% BUG:" comments: an Tim Peters <tim.peters@gmail.com> parents: 16695 diff changeset	97 elements the sequences have in common; best case time is linear.
16551 7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	98
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	99 SequenceMatcher methods:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	100
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	101 __init__(isjunk=None, a='', b='')
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	102 Construct a SequenceMatcher.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	103
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	104 Optional arg isjunk is None (the default), or a one-argument function
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	105 that takes a sequence element and returns true iff the element is junk.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	106 None is equivalent to passing "lambda x: 0", i.e. no elements are
16695 e14c5f34fa05 Fix a few small typos in the docstrings. Fred Drake <fdrake@acm.org> parents: 16551 diff changeset	107 considered to be junk. For example, pass
16551 7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	108 lambda x: x in " \\t"
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	109 if you're comparing lines as sequences of characters, and don't want to
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	110 synch up on blanks or hard tabs.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	111
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	112 Optional arg a is the first of two sequences to be compared. By
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	113 default, an empty string. The elements of a must be hashable.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	114
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	115 Optional arg b is the second of two sequences to be compared. By
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	116 default, an empty string. The elements of b must be hashable.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	117
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	118 set_seqs(a, b)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	119 Set the two sequences to be compared.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	120
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	121 >>> s = SequenceMatcher()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	122 >>> s.set_seqs("abcd", "bcde")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	123 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	124 0.75
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	125
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	126 set_seq1(a)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	127 Set the first sequence to be compared.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	128
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	129 The second sequence to be compared is not changed.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	130
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	131 >>> s = SequenceMatcher(None, "abcd", "bcde")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	132 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	133 0.75
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	134 >>> s.set_seq1("bcde")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	135 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	136 1.0
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	137 >>>
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	138
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	139 SequenceMatcher computes and caches detailed information about the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	140 second sequence, so if you want to compare one sequence S against many
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	141 sequences, use .set_seq2(S) once and call .set_seq1(x) repeatedly for
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	142 each of the other sequences.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	143
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	144 See also set_seqs() and set_seq2().
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	145
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	146 set_seq2(b)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	147 Set the second sequence to be compared.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	148
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	149 The first sequence to be compared is not changed.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	150
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	151 >>> s = SequenceMatcher(None, "abcd", "bcde")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	152 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	153 0.75
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	154 >>> s.set_seq2("abcd")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	155 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	156 1.0
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	157 >>>
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	158
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	159 SequenceMatcher computes and caches detailed information about the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	160 second sequence, so if you want to compare one sequence S against many
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	161 sequences, use .set_seq2(S) once and call .set_seq1(x) repeatedly for
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	162 each of the other sequences.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	163
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	164 See also set_seqs() and set_seq1().
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	165
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	166 find_longest_match(alo, ahi, blo, bhi)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	167 Find longest matching block in a[alo:ahi] and b[blo:bhi].
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	168
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	169 If isjunk is not defined:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	170
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	171 Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	172 alo <= i <= i+k <= ahi
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	173 blo <= j <= j+k <= bhi
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	174 and for all (i',j',k') meeting those conditions,
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	175 k >= k'
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	176 i <= i'
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	177 and if i == i', j <= j'
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	178
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	179 In other words, of all maximal matching blocks, return one that starts
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	180 earliest in a, and of all those maximal matching blocks that start
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	181 earliest in a, return the one that starts earliest in b.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	182
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	183 >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	184 >>> s.find_longest_match(0, 5, 0, 9)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	185 (0, 4, 5)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	186
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	187 If isjunk is defined, first the longest matching block is determined as
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	188 above, but with the additional restriction that no junk element appears
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	189 in the block. Then that block is extended as far as possible by
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	190 matching (only) junk elements on both sides. So the resulting block
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	191 never matches on junk except as identical junk happens to be adjacent
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	192 to an "interesting" match.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	193
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	194 Here's the same example as before, but considering blanks to be junk.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	195 That prevents " abcd" from matching the " abcd" at the tail end of the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	196 second sequence directly. Instead only the "abcd" can match, and
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	197 matches the leftmost "abcd" in the second sequence:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	198
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	199 >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	200 >>> s.find_longest_match(0, 5, 0, 9)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	201 (1, 0, 4)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	202
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	203 If no blocks match, return (alo, blo, 0).
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	204
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	205 >>> s = SequenceMatcher(None, "ab", "c")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	206 >>> s.find_longest_match(0, 2, 0, 1)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	207 (0, 0, 0)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	208
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	209 get_matching_blocks()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	210 Return list of triples describing matching subsequences.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	211
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	212 Each triple is of the form (i, j, n), and means that
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	213 a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in i
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	214 and in j.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	215
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	216 The last triple is a dummy, (len(a), len(b), 0), and is the only triple
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	217 with n==0.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	218
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	219 >>> s = SequenceMatcher(None, "abxcd", "abcd")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	220 >>> s.get_matching_blocks()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	221 [(0, 0, 2), (3, 2, 2), (5, 4, 0)]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	222
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	223 get_opcodes()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	224 Return list of 5-tuples describing how to turn a into b.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	225
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	226 Each tuple is of the form (tag, i1, i2, j1, j2). The first tuple has
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	227 i1 == j1 == 0, and remaining tuples have i1 == the i2 from the tuple
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	228 preceding it, and likewise for j1 == the previous j2.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	229
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	230 The tags are strings, with these meanings:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	231
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	232 'replace': a[i1:i2] should be replaced by b[j1:j2]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	233 'delete': a[i1:i2] should be deleted.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	234 Note that j1==j2 in this case.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	235 'insert': b[j1:j2] should be inserted at a[i1:i1].
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	236 Note that i1==i2 in this case.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	237 'equal': a[i1:i2] == b[j1:j2]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	238
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	239 >>> a = "qabxcd"
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	240 >>> b = "abycdf"
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	241 >>> s = SequenceMatcher(None, a, b)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	242 >>> for tag, i1, i2, j1, j2 in s.get_opcodes():
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	243 ... print ("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	244 ... (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	245 delete a[0:1] (q) b[0:0] ()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	246 equal a[1:3] (ab) b[0:2] (ab)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	247 replace a[3:4] (x) b[2:3] (y)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	248 equal a[4:6] (cd) b[3:5] (cd)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	249 insert a[6:6] () b[5:6] (f)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	250
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	251 ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	252 Return a measure of the sequences' similarity (float in [0,1]).
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	253
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	254 Where T is the total number of elements in both sequences, and M is the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	255 number of matches, this is 2,0*M / T. Note that this is 1 if the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	256 sequences are identical, and 0 if they have nothing in common.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	257
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	258 .ratio() is expensive to compute if you haven't already computed
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	259 .get_matching_blocks() or .get_opcodes(), in which case you may want to
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	260 try .quick_ratio() or .real_quick_ratio() first to get an upper bound.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	261
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	262 >>> s = SequenceMatcher(None, "abcd", "bcde")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	263 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	264 0.75
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	265 >>> s.quick_ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	266 0.75
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	267 >>> s.real_quick_ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	268 1.0
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	269
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	270 quick_ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	271 Return an upper bound on .ratio() relatively quickly.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	272
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	273 This isn't defined beyond that it is an upper bound on .ratio(), and
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	274 is faster to compute.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	275
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	276 real_quick_ratio():
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	277 Return an upper bound on ratio() very quickly.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	278
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	279 This isn't defined beyond that it is an upper bound on .ratio(), and
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	280 is faster to compute than either .ratio() or .quick_ratio().
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	281 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	282
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	283 TRACE = 0
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	284
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	285 class SequenceMatcher:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	286 def __init__(self, isjunk=None, a='', b=''):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	287 """Construct a SequenceMatcher.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	288
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	289 Optional arg isjunk is None (the default), or a one-argument
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	290 function that takes a sequence element and returns true iff the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	291 element is junk. None is equivalent to passing "lambda x: 0", i.e.
16695 e14c5f34fa05 Fix a few small typos in the docstrings. Fred Drake <fdrake@acm.org> parents: 16551 diff changeset	292 no elements are considered to be junk. For example, pass
16551 7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	293 lambda x: x in " \\t"
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	294 if you're comparing lines as sequences of characters, and don't
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	295 want to synch up on blanks or hard tabs.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	296
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	297 Optional arg a is the first of two sequences to be compared. By
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	298 default, an empty string. The elements of a must be hashable. See
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	299 also .set_seqs() and .set_seq1().
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	300
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	301 Optional arg b is the second of two sequences to be compared. By
16695 e14c5f34fa05 Fix a few small typos in the docstrings. Fred Drake <fdrake@acm.org> parents: 16551 diff changeset	302 default, an empty string. The elements of b must be hashable. See
16551 7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	303 also .set_seqs() and .set_seq2().
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	304 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	305
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	306 # Members:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	307 # a
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	308 # first sequence
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	309 # b
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	310 # second sequence; differences are computed as "what do
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	311 # we need to do to 'a' to change it into 'b'?"
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	312 # b2j
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	313 # for x in b, b2j[x] is a list of the indices (into b)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	314 # at which x appears; junk elements do not appear
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	315 # b2jhas
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	316 # b2j.has_key
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	317 # fullbcount
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	318 # for x in b, fullbcount[x] == the number of times x
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	319 # appears in b; only materialized if really needed (used
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	320 # only for computing quick_ratio())
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	321 # matching_blocks
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	322 # a list of (i, j, k) triples, where a[i:i+k] == b[j:j+k];
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	323 # ascending & non-overlapping in i and in j; terminated by
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	324 # a dummy (len(a), len(b), 0) sentinel
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	325 # opcodes
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	326 # a list of (tag, i1, i2, j1, j2) tuples, where tag is
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	327 # one of
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	328 # 'replace' a[i1:i2] should be replaced by b[j1:j2]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	329 # 'delete' a[i1:i2] should be deleted
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	330 # 'insert' b[j1:j2] should be inserted
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	331 # 'equal' a[i1:i2] == b[j1:j2]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	332 # isjunk
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	333 # a user-supplied function taking a sequence element and
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	334 # returning true iff the element is "junk" -- this has
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	335 # subtle but helpful effects on the algorithm, which I'll
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	336 # get around to writing up someday <0.9 wink>.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	337 # DON'T USE! Only __chain_b uses this. Use isbjunk.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	338 # isbjunk
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	339 # for x in b, isbjunk(x) == isjunk(x) but much faster;
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	340 # it's really the has_key method of a hidden dict.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	341 # DOES NOT WORK for x in a!
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	342
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	343 self.isjunk = isjunk
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	344 self.a = self.b = None
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	345 self.set_seqs(a, b)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	346
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	347 def set_seqs(self, a, b):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	348 """Set the two sequences to be compared.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	349
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	350 >>> s = SequenceMatcher()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	351 >>> s.set_seqs("abcd", "bcde")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	352 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	353 0.75
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	354 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	355
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	356 self.set_seq1(a)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	357 self.set_seq2(b)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	358
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	359 def set_seq1(self, a):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	360 """Set the first sequence to be compared.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	361
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	362 The second sequence to be compared is not changed.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	363
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	364 >>> s = SequenceMatcher(None, "abcd", "bcde")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	365 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	366 0.75
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	367 >>> s.set_seq1("bcde")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	368 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	369 1.0
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	370 >>>
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	371
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	372 SequenceMatcher computes and caches detailed information about the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	373 second sequence, so if you want to compare one sequence S against
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	374 many sequences, use .set_seq2(S) once and call .set_seq1(x)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	375 repeatedly for each of the other sequences.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	376
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	377 See also set_seqs() and set_seq2().
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	378 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	379
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	380 if a is self.a:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	381 return
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	382 self.a = a
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	383 self.matching_blocks = self.opcodes = None
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	384
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	385 def set_seq2(self, b):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	386 """Set the second sequence to be compared.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	387
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	388 The first sequence to be compared is not changed.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	389
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	390 >>> s = SequenceMatcher(None, "abcd", "bcde")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	391 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	392 0.75
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	393 >>> s.set_seq2("abcd")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	394 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	395 1.0
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	396 >>>
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	397
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	398 SequenceMatcher computes and caches detailed information about the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	399 second sequence, so if you want to compare one sequence S against
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	400 many sequences, use .set_seq2(S) once and call .set_seq1(x)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	401 repeatedly for each of the other sequences.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	402
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	403 See also set_seqs() and set_seq1().
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	404 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	405
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	406 if b is self.b:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	407 return
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	408 self.b = b
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	409 self.matching_blocks = self.opcodes = None
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	410 self.fullbcount = None
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	411 self.__chain_b()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	412
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	413 # For each element x in b, set b2j[x] to a list of the indices in
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	414 # b where x appears; the indices are in increasing order; note that
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	415 # the number of times x appears in b is len(b2j[x]) ...
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	416 # when self.isjunk is defined, junk elements don't show up in this
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	417 # map at all, which stops the central find_longest_match method
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	418 # from starting any matching block at a junk element ...
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	419 # also creates the fast isbjunk function ...
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	420 # note that this is only called when b changes; so for cross-product
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	421 # kinds of matches, it's best to call set_seq2 once, then set_seq1
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	422 # repeatedly
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	423
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	424 def __chain_b(self):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	425 # Because isjunk is a user-defined (not C) function, and we test
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	426 # for junk a LOT, it's important to minimize the number of calls.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	427 # Before the tricks described here, __chain_b was by far the most
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	428 # time-consuming routine in the whole module! If anyone sees
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	429 # Jim Roskind, thank him again for profile.py -- I never would
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	430 # have guessed that.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	431 # The first trick is to build b2j ignoring the possibility
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	432 # of junk. I.e., we don't call isjunk at all yet. Throwing
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	433 # out the junk later is much cheaper than building b2j "right"
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	434 # from the start.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	435 b = self.b
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	436 self.b2j = b2j = {}
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	437 self.b2jhas = b2jhas = b2j.has_key
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	438 for i in xrange(len(b)):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	439 elt = b[i]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	440 if b2jhas(elt):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	441 b2j[elt].append(i)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	442 else:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	443 b2j[elt] = [i]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	444
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	445 # Now b2j.keys() contains elements uniquely, and especially when
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	446 # the sequence is a string, that's usually a good deal smaller
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	447 # than len(string). The difference is the number of isjunk calls
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	448 # saved.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	449 isjunk, junkdict = self.isjunk, {}
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	450 if isjunk:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	451 for elt in b2j.keys():
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	452 if isjunk(elt):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	453 junkdict[elt] = 1 # value irrelevant; it's a set
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	454 del b2j[elt]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	455
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	456 # Now for x in b, isjunk(x) == junkdict.has_key(x), but the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	457 # latter is much faster. Note too that while there may be a
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	458 # lot of junk in the sequence, the number of unique junk
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	459 # elements is probably small. So the memory burden of keeping
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	460 # this dict alive is likely trivial compared to the size of b2j.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	461 self.isbjunk = junkdict.has_key
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	462
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	463 def find_longest_match(self, alo, ahi, blo, bhi):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	464 """Find longest matching block in a[alo:ahi] and b[blo:bhi].
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	465
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	466 If isjunk is not defined:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	467
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	468 Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	469 alo <= i <= i+k <= ahi
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	470 blo <= j <= j+k <= bhi
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	471 and for all (i',j',k') meeting those conditions,
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	472 k >= k'
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	473 i <= i'
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	474 and if i == i', j <= j'
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	475
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	476 In other words, of all maximal matching blocks, return one that
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	477 starts earliest in a, and of all those maximal matching blocks that
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	478 start earliest in a, return the one that starts earliest in b.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	479
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	480 >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	481 >>> s.find_longest_match(0, 5, 0, 9)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	482 (0, 4, 5)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	483
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	484 If isjunk is defined, first the longest matching block is
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	485 determined as above, but with the additional restriction that no
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	486 junk element appears in the block. Then that block is extended as
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	487 far as possible by matching (only) junk elements on both sides. So
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	488 the resulting block never matches on junk except as identical junk
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	489 happens to be adjacent to an "interesting" match.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	490
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	491 Here's the same example as before, but considering blanks to be
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	492 junk. That prevents " abcd" from matching the " abcd" at the tail
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	493 end of the second sequence directly. Instead only the "abcd" can
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	494 match, and matches the leftmost "abcd" in the second sequence:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	495
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	496 >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	497 >>> s.find_longest_match(0, 5, 0, 9)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	498 (1, 0, 4)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	499
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	500 If no blocks match, return (alo, blo, 0).
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	501
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	502 >>> s = SequenceMatcher(None, "ab", "c")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	503 >>> s.find_longest_match(0, 2, 0, 1)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	504 (0, 0, 0)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	505 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	506
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	507 # CAUTION: stripping common prefix or suffix would be incorrect.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	508 # E.g.,
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	509 # ab
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	510 # acab
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	511 # Longest matching block is "ab", but if common prefix is
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	512 # stripped, it's "a" (tied with "b"). UNIX(tm) diff does so
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	513 # strip, so ends up claiming that ab is changed to acab by
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	514 # inserting "ca" in the middle. That's minimal but unintuitive:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	515 # "it's obvious" that someone inserted "ac" at the front.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	516 # Windiff ends up at the same place as diff, but by pairing up
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	517 # the unique 'b's and then matching the first two 'a's.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	518
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	519 a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.isbjunk
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	520 besti, bestj, bestsize = alo, blo, 0
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	521 # find longest junk-free match
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	522 # during an iteration of the loop, j2len[j] = length of longest
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	523 # junk-free match ending with a[i-1] and b[j]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	524 j2len = {}
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	525 nothing = []
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	526 for i in xrange(alo, ahi):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	527 # look at all instances of a[i] in b; note that because
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	528 # b2j has no junk keys, the loop is skipped if a[i] is junk
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	529 j2lenget = j2len.get
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	530 newj2len = {}
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	531 for j in b2j.get(a[i], nothing):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	532 # a[i] matches b[j]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	533 if j < blo:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	534 continue
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	535 if j >= bhi:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	536 break
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	537 k = newj2len[j] = j2lenget(j-1, 0) + 1
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	538 if k > bestsize:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	539 besti, bestj, bestsize = i-k+1, j-k+1, k
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	540 j2len = newj2len
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	541
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	542 # Now that we have a wholly interesting match (albeit possibly
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	543 # empty!), we may as well suck up the matching junk on each
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	544 # side of it too. Can't think of a good reason not to, and it
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	545 # saves post-processing the (possibly considerable) expense of
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	546 # figuring out what to do with it. In the case of an empty
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	547 # interesting match, this is clearly the right thing to do,
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	548 # because no other kind of match is possible in the regions.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	549 while besti > alo and bestj > blo and \
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	550 isbjunk(b[bestj-1]) and \
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	551 a[besti-1] == b[bestj-1]:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	552 besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	553 while besti+bestsize < ahi and bestj+bestsize < bhi and \
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	554 isbjunk(b[bestj+bestsize]) and \
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	555 a[besti+bestsize] == b[bestj+bestsize]:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	556 bestsize = bestsize + 1
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	557
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	558 if TRACE:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	559 print "get_matching_blocks", alo, ahi, blo, bhi
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	560 print " returns", besti, bestj, bestsize
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	561 return besti, bestj, bestsize
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	562
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	563 def get_matching_blocks(self):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	564 """Return list of triples describing matching subsequences.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	565
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	566 Each triple is of the form (i, j, n), and means that
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	567 a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	568 i and in j.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	569
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	570 The last triple is a dummy, (len(a), len(b), 0), and is the only
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	571 triple with n==0.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	572
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	573 >>> s = SequenceMatcher(None, "abxcd", "abcd")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	574 >>> s.get_matching_blocks()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	575 [(0, 0, 2), (3, 2, 2), (5, 4, 0)]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	576 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	577
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	578 if self.matching_blocks is not None:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	579 return self.matching_blocks
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	580 self.matching_blocks = []
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	581 la, lb = len(self.a), len(self.b)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	582 self.__helper(0, la, 0, lb, self.matching_blocks)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	583 self.matching_blocks.append( (la, lb, 0) )
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	584 if TRACE:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	585 print '*** matching blocks', self.matching_blocks
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	586 return self.matching_blocks
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	587
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	588 # builds list of matching blocks covering a[alo:ahi] and
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	589 # b[blo:bhi], appending them in increasing order to answer
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	590
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	591 def __helper(self, alo, ahi, blo, bhi, answer):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	592 i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	593 # a[alo:i] vs b[blo:j] unknown
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	594 # a[i:i+k] same as b[j:j+k]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	595 # a[i+k:ahi] vs b[j+k:bhi] unknown
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	596 if k:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	597 if alo < i and blo < j:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	598 self.__helper(alo, i, blo, j, answer)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	599 answer.append(x)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	600 if i+k < ahi and j+k < bhi:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	601 self.__helper(i+k, ahi, j+k, bhi, answer)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	602
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	603 def get_opcodes(self):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	604 """Return list of 5-tuples describing how to turn a into b.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	605
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	606 Each tuple is of the form (tag, i1, i2, j1, j2). The first tuple
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	607 has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	608 tuple preceding it, and likewise for j1 == the previous j2.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	609
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	610 The tags are strings, with these meanings:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	611
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	612 'replace': a[i1:i2] should be replaced by b[j1:j2]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	613 'delete': a[i1:i2] should be deleted.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	614 Note that j1==j2 in this case.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	615 'insert': b[j1:j2] should be inserted at a[i1:i1].
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	616 Note that i1==i2 in this case.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	617 'equal': a[i1:i2] == b[j1:j2]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	618
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	619 >>> a = "qabxcd"
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	620 >>> b = "abycdf"
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	621 >>> s = SequenceMatcher(None, a, b)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	622 >>> for tag, i1, i2, j1, j2 in s.get_opcodes():
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	623 ... print ("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	624 ... (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	625 delete a[0:1] (q) b[0:0] ()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	626 equal a[1:3] (ab) b[0:2] (ab)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	627 replace a[3:4] (x) b[2:3] (y)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	628 equal a[4:6] (cd) b[3:5] (cd)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	629 insert a[6:6] () b[5:6] (f)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	630 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	631
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	632 if self.opcodes is not None:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	633 return self.opcodes
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	634 i = j = 0
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	635 self.opcodes = answer = []
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	636 for ai, bj, size in self.get_matching_blocks():
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	637 # invariant: we've pumped out correct diffs to change
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	638 # a[:i] into b[:j], and the next matching block is
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	639 # a[ai:ai+size] == b[bj:bj+size]. So we need to pump
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	640 # out a diff to change a[i:ai] into b[j:bj], pump out
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	641 # the matching block, and move (i,j) beyond the match
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	642 tag = ''
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	643 if i < ai and j < bj:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	644 tag = 'replace'
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	645 elif i < ai:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	646 tag = 'delete'
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	647 elif j < bj:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	648 tag = 'insert'
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	649 if tag:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	650 answer.append( (tag, i, ai, j, bj) )
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	651 i, j = ai+size, bj+size
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	652 # the list of matching blocks is terminated by a
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	653 # sentinel with size 0
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	654 if size:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	655 answer.append( ('equal', ai, i, bj, j) )
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	656 return answer
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	657
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	658 def ratio(self):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	659 """Return a measure of the sequences' similarity (float in [0,1]).
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	660
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	661 Where T is the total number of elements in both sequences, and
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	662 M is the number of matches, this is 2,0*M / T.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	663 Note that this is 1 if the sequences are identical, and 0 if
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	664 they have nothing in common.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	665
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	666 .ratio() is expensive to compute if you haven't already computed
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	667 .get_matching_blocks() or .get_opcodes(), in which case you may
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	668 want to try .quick_ratio() or .real_quick_ratio() first to get an
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	669 upper bound.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	670
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	671 >>> s = SequenceMatcher(None, "abcd", "bcde")
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	672 >>> s.ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	673 0.75
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	674 >>> s.quick_ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	675 0.75
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	676 >>> s.real_quick_ratio()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	677 1.0
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	678 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	679
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	680 matches = reduce(lambda sum, triple: sum + triple[-1],
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	681 self.get_matching_blocks(), 0)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	682 return 2.0 * matches / (len(self.a) + len(self.b))
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	683
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	684 def quick_ratio(self):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	685 """Return an upper bound on ratio() relatively quickly.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	686
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	687 This isn't defined beyond that it is an upper bound on .ratio(), and
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	688 is faster to compute.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	689 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	690
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	691 # viewing a and b as multisets, set matches to the cardinality
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	692 # of their intersection; this counts the number of matches
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	693 # without regard to order, so is clearly an upper bound
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	694 if self.fullbcount is None:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	695 self.fullbcount = fullbcount = {}
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	696 for elt in self.b:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	697 fullbcount[elt] = fullbcount.get(elt, 0) + 1
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	698 fullbcount = self.fullbcount
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	699 # avail[x] is the number of times x appears in 'b' less the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	700 # number of times we've seen it in 'a' so far ... kinda
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	701 avail = {}
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	702 availhas, matches = avail.has_key, 0
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	703 for elt in self.a:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	704 if availhas(elt):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	705 numb = avail[elt]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	706 else:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	707 numb = fullbcount.get(elt, 0)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	708 avail[elt] = numb - 1
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	709 if numb > 0:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	710 matches = matches + 1
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	711 return 2.0 * matches / (len(self.a) + len(self.b))
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	712
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	713 def real_quick_ratio(self):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	714 """Return an upper bound on ratio() very quickly.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	715
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	716 This isn't defined beyond that it is an upper bound on .ratio(), and
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	717 is faster to compute than either .ratio() or .quick_ratio().
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	718 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	719
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	720 la, lb = len(self.a), len(self.b)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	721 # can't have more matches than the number of elements in the
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	722 # shorter sequence
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	723 return 2.0 * min(la, lb) / (la + lb)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	724
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	725 def get_close_matches(word, possibilities, n=3, cutoff=0.6):
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	726 """Use SequenceMatcher to return list of the best "good enough" matches.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	727
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	728 word is a sequence for which close matches are desired (typically a
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	729 string).
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	730
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	731 possibilities is a list of sequences against which to match word
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	732 (typically a list of strings).
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	733
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	734 Optional arg n (default 3) is the maximum number of close matches to
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	735 return. n must be > 0.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	736
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	737 Optional arg cutoff (default 0.6) is a float in [0, 1]. Possibilities
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	738 that don't score at least that similar to word are ignored.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	739
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	740 The best (no more than n) matches among the possibilities are returned
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	741 in a list, sorted by similarity score, most similar first.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	742
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	743 >>> get_close_matches("appel", ["ape", "apple", "peach", "puppy"])
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	744 ['apple', 'ape']
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	745 >>> import keyword
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	746 >>> get_close_matches("wheel", keyword.kwlist)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	747 ['while']
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	748 >>> get_close_matches("apple", keyword.kwlist)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	749 []
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	750 >>> get_close_matches("accept", keyword.kwlist)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	751 ['except']
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	752 """
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	753
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	754 if not n > 0:
16695 e14c5f34fa05 Fix a few small typos in the docstrings. Fred Drake <fdrake@acm.org> parents: 16551 diff changeset	755 raise ValueError("n must be > 0: " + `n`)
16551 7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	756 if not 0.0 <= cutoff <= 1.0:
16695 e14c5f34fa05 Fix a few small typos in the docstrings. Fred Drake <fdrake@acm.org> parents: 16551 diff changeset	757 raise ValueError("cutoff must be in [0.0, 1.0]: " + `cutoff`)
16551 7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	758 result = []
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	759 s = SequenceMatcher()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	760 s.set_seq2(word)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	761 for x in possibilities:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	762 s.set_seq1(x)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	763 if s.real_quick_ratio() >= cutoff and \
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	764 s.quick_ratio() >= cutoff and \
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	765 s.ratio() >= cutoff:
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	766 result.append((s.ratio(), x))
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	767 # Sort by score.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	768 result.sort()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	769 # Retain only the best n.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	770 result = result[-n:]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	771 # Move best-scorer to head of list.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	772 result.reverse()
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	773 # Strip scores.
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	774 return [x for score, x in result]
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	775
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	776 def _test():
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	777 import doctest, difflib
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	778 return doctest.testmod(difflib)
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	779
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	780 if __name__ == "__main__":
7de5043827f7 Moved SequenceMatcher from ndiff into new std library module difflib.py. Tim Peters <tim.peters@gmail.com> parents: diff changeset	781 _test()

Mercurial > cpython-lru_cache-weakref

annotate Lib/difflib.py @ 17581:c1937faabb23 2.1