[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/gestalt-pattern-matching-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki19\/gestalt-pattern-matching-wikipedia\/","headline":"Gestalt pattern matching – Wikipedia","name":"Gestalt pattern matching – Wikipedia","description":"From Wikipedia, the free encyclopedia Gestalt pattern matching,[1] also Ratcliff\/Obershelp pattern recognition,[2] is a string-matching algorithm for determining the similarity","datePublished":"2018-11-13","dateModified":"2018-11-13","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki19\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki19\/gestalt-pattern-matching-wikipedia\/","about":["Wiki"],"wordCount":4997,"articleBody":"From Wikipedia, the free encyclopediaGestalt pattern matching,[1] also Ratcliff\/Obershelp pattern recognition,[2] is a string-matching algorithm for determining the similarity of two strings. It was developed in 1983 by John W. Ratcliff and John A. Obershelp and published in the Dr. Dobb’s Journal in July 1988.[2]Algorithm[edit]The similarity of two strings S1{displaystyle S_{1}} and S2{displaystyle S_{2}} is determined by the formula, calculating twice the number of matching characters Km{displaystyle K_{m}} divided by the total number of characters of both strings. The matching characters are defined as the longest common substring plus recursively the number of matching characters in the non-matching regions on both sides of the longest common substring:[2]Dro=2Km|S1|+|S2|{displaystyle D_{ro}={frac {2K_{m}}{|S_{1}|+|S_{2}|}}}[3]where the similarity metric can take a value between zero and one:0\u2264Dro\u22641{displaystyle 0leq D_{ro}leq 1}The value of 1 stands for the complete match of the two strings, whereas the value of 0 means there is no match and not even one common letter.Sample[edit]S1WIKIMEDIAS2WIKIMANIAThe longest common substring is WIKIM (grey) with 5 characters. There is no further substring on the left. The non-matching substrings on the right side are EDIA and ANIA. They again have a longest common substring IA (dark gray) with length 2.The similarity metric is determined by:2Km|S1|+|S2|=2\u22c5(|”WIKIM”|+|”IA”|)|S1|+|S2|=2\u22c5(5+2)9+9=1418=0.7\u00af{displaystyle {frac {2K_{m}}{|S_{1}|+|S_{2}|}}={frac {2cdot (|{text{”WIKIM”}}|+|{text{”IA”}}|)}{|S_{1}|+|S_{2}|}}={frac {2cdot (5+2)}{9+9}}={frac {14}{18}}=0.{overline {7}}}Properties[edit]Complexity[edit]The execution time of the algorithm is O(n3){displaystyle O(n^{3})} in a worst case and O(n2){displaystyle O(n^{2})} in an average case. By changing the computing method, the execution time can be improved significantly.[1]Commutative property[edit]It can be shown, that the gestalt pattern matching algorithm is not commutative: [4]Dro(S1,S2)\u2260Dro(S2,S1).{displaystyle D_{ro}(S_{1},S_{2})neq D_{ro}(S_{2},S_{1}).}SampleFor the two stringsS1=GESTALT PATTERN MATCHING{displaystyle S_{1}={text{GESTALT PATTERN MATCHING}}}andS2=GESTALT PRACTICE{displaystyle S_{2}={text{GESTALT PRACTICE}}}the metric result forDro(S1,S2){displaystyle D_{ro}(S_{1},S_{2})} is 2440{displaystyle {frac {24}{40}}} with the substrings GESTALT P, A, T, E and forDro(S2,S1){displaystyle D_{ro}(S_{2},S_{1})} the metric is 2640{displaystyle {frac {26}{40}}} with the substrings GESTALT P, R, A, C, I.Applications[edit]The Python difflib library, which was introduced in version 2.1,[1] implements a similar algorithm that predates the Ratcliff-Obershelp algorithm. Due to the unfavourable runtime behaviour of this similarity metric, three methods have been implemented. Two of them return an upper bound in a faster execution time.[1] The fastest variant only compares the length of the two substrings:[5]Drqr=2\u22c5min(|S1|,|S2|)|S1|+|S2|{displaystyle D_{rqr}={frac {2cdot min(|S1|,|S2|)}{|S1|+|S2|}}},# Drqr Implementation in Pythondef real_quick_ratio(s1: str, s2: str) -> float:    \"\"\"Return an upper bound on ratio() very quickly.\"\"\"    l1, l2 = len(s1), len(s2)    length = l1 + l2    if not length:        return 1.0    return 2.0 * min(l1, l2) \/ lengthThe second upper bound calculates twice the sum of all used characters S1{displaystyle S_{1}} which occur in S2{displaystyle S_{2}} divided by the length of both strings but the sequence is ignored.Dqr=2\u22c5|{|S1|}\u2229{|S2|}||S1|+|S2|{displaystyle D_{qr}={frac {2cdot {big |}{!vert S1vert !}cap {!vert S2vert !}{big |}}{|S1|+|S2|}}},# Dqr Implementation in Pythondef quick_ratio(s1: str, s2: str) -> float:    \"\"\"Return an upper bound on ratio() relatively quickly.\"\"\"    length = len(s1) + len(s2)    if not length:        return 1.0    intersect = collections.Counter(s1) & collections.Counter(s2)    matches = sum(intersect.values())    return 2.0 * matches \/ lengthTrivially the following applies:0\u2264Dro\u2264Dqr\u2264Drqr\u22641{displaystyle 0leq D_{ro}leq D_{qr}leq D_{rqr}leq 1} and0\u2264Km\u2264|{|S1|}\u2229{|S2|}|\u2264min(|S1|,|S2|)\u2264|S1|+|S2|2{displaystyle 0leq K_{m}leq |{!vert S1vert !}cap {!vert S2vert !}{big |}leq min(|S1|,|S2|)leq {frac {|S1|+|S2|}{2}}}.References[edit]Further reading[edit]Ratcliff, John W.; Metzener, David (July 1988). “Pattern Matching: The Gestalt Approach”. Dr. Dobb’s Journal (46).See also[edit]  "},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/gestalt-pattern-matching-wikipedia\/#breadcrumbitem","name":"Gestalt pattern matching – Wikipedia"}}]}]