Gestaltmönstermatchning

Gestaltmönstermatchning , även Ratcliff/Obershelp-mönsterigenkänning, är en strängmatchningsalgoritm för att bestämma likheten mellan två strängar . Den utvecklades 1983 av John W. Ratcliff och John A. Obershelp och publicerades i Dr. Dobb's Journal i juli 1988.

Algoritm

Likheten mellan två strängar $S_{1}$ och $S_{2}$ bestäms av formeln, som beräknar två gånger antalet matchande tecken $K_{m}$ dividerat av det totala antalet tecken i båda strängarna. De matchande tecknen definieras som den längsta gemensamma delsträngen plus rekursivt antalet matchande tecken i de icke-matchande områdena på båda sidor om den längsta gemensamma delsträngen:

$D_{ro}={\frac {2K_{m}}{|S_{1}|+|S_{2}|}}$

där likhetsmåttet kan ha ett värde mellan noll och ett:

$0\leq D_{ro}\leq 1$

Värdet 1 står för den fullständiga matchningen av de två strängarna, medan värdet 0 betyder att det inte finns någon matchning och inte ens en vanlig bokstav.

Prov

S 1	W	jag	K	jag	M	E	D	jag	A
S 2	W	jag	K	jag	M	A	N	jag	A

Den längsta vanliga delsträngen är WIKIM (grå) med 5 tecken. Det finns ingen ytterligare delsträng till vänster. De icke-matchande delsträngarna på höger sida är EDIA och ANIA . De har återigen en längsta gemensamma delsträng IA (mörkgrå) med längden 2. Likhetsmåttet bestäms av:

${\frac {2K_{m}}{|S_{1}|+|S_{2}|}}={\ frac {2\cdot (|{\text{''WIKIM''}}|+|{\text{''IA''}}|)}{|S_{1}|+|S_{2}|} }={\frac {2\cdot (5+2)}{9+9}}={\frac {14}{18}}=0.{\overline {7}}$

Egenskaper

Komplexitet

Algoritmens exekveringstid är $O(n^{3})$ i värsta fall och $O(n^{2})$ i ett genomsnittligt fall . Genom att ändra beräkningsmetoden kan exekveringstiden förbättras avsevärt.

Kommutativ egenskap

Det kan visas att gestaltmönstermatchningsalgoritmen inte är kommutativ :

$D_{ro}(S_{1},S_{2})\neq D_{ro}(S_{2},S_{1}).$

Exempel

För de två strängarna

$S_{1}={\text{GESTALTMÖNSTER MATCHAR}}$

och

$S_{2}={\text{GESTALTÖVNING}}$

det metriska resultatet för

$D_{ro}(S_{1},S_{2})$ är ${\frac {24}{40}}$ med delsträngarna GESTALT P , A , T , E och för

$D_{ro}(S_{2},S_{1})$ är måttet ${\frac { 26}{40}}$ med delsträngarna GESTALT P , R , A , C , I .

Ansökningar

Python difflib - biblioteket, som introducerades i version 2.1, implementerar en liknande algoritm som föregår Ratcliff-Obershelp-algoritmen. På grund av det ogynnsamma körtidsbeteendet för detta likhetsmått har tre metoder implementerats. Två av dem returnerar en övre gräns på en snabbare körningstid. Den snabbaste varianten jämför bara längden på de två delsträngarna:

$D_{rqr}={\frac {2\cdot \min(|S1|,|S2|)}{|S1|+|S2|}}$ ,

      
    
        
        

      
         

           # Drqr-implementering i Python  def  real_quick_ratio  (  s1  :  str  ,  s2  :  str  )  ->  float  :  """Returnera en övre gräns på ratio() mycket snabbt."""  l1  ,  l2  =  len  (  s1  ),  len  (  s2  )  längd  =  l1  +  l2  om  inte  längd  :  retur  1,0  retur  2,0  *  min  (  l1  ,  l2  )  /  längd 

Den andra övre gränsen beräknar två gånger summan av alla använda tecken $S_{1}$ som förekommer i $S_{2}$ dividerat med längden på båda strängarna men sekvensen ignoreras.

$D_{qr}={\frac {2\cdot {\big |}\{\!\vert S1\vert \!\}\cap \{\!\vert S2\vert \!\}{\ stor |}}{|S1|+|S2|}}$ ,

      
    
        

      
         

        
      
          # Dqr-implementering i Python  def  quick_ratio  (  s1  :  str  ,  s2  :  str  )  ->  float  :  """Returnera en övre gräns på ratio() relativt snabbt."""  length  =  len  (  s1  )  +  len  (  s2  )  om  inte  längd  :  retur  1,0  skär  =  samlingar  .  Räknare  (  s1  )  &  samlingar  .  Räknare  (  s2  )  matchar  =  summa  (  skär  .  värden  ())  returnerar  2,0  *  matchningar  /  längd 

Trivialt gäller följande:

$0\leq D_{ro}\leq D_{qr}\leq D_{rqr}\leq 1$ och

$0\leq K_{m}\leq |\{\!\vert S1\vert \!\}\cap \{\!\vert S2\vert \!\}{\big |}\leq \ min(|S1|,|S2|)\leq {\frac {|S1|+|S2|}{2}}$ .

Vidare läsning

• Ratcliff, John W.; Metzener, David (juli 1988). "Pattern Matching: The Gestalt Approach". Dr. Dobb's Journal (46).

Se även

• Mönstermatchning