Movatterモバイル変換
[0]ホーム
difflib
Mikkel Rasmussenfootech at get2net.dk
Sun Apr 22 06:54:30 EDT 2001
Has anybody got any references for the algorithm used in difflib. Thedocumentation says:"The basic algorithm predates, and is a little fancier than, an algorithmpublished in the late 1980's by Ratcliff and Obershelp under the hyperbolicname ``gestalt pattern matching.'' The idea is to find the longestcontiguous matching subsequence that contains no ``junk'' elements (theRatcliff and Obershelp algorithm doesn't address junk). The same idea isthen applied recursively to the pieces of the sequences to the left and tothe right of the matching subsequence. This does not yield minimal editsequences, but does tend to yield matches that ``look right'' to people."and there is a link to Dr. Dobbs journal, but the article is only availableon cd-rom.Are there any explanations available elsewhere?Mikkel Rasmussen
More information about the Python-listmailing list
[8]ページ先頭