Gestalt Desen Eşleştirme - Gestalt Pattern Matching - Wikipedia

Gestalt Desen Eşleştirme,[1] Ayrıca Ratcliff / Obershelp Örüntü Tanıma,[2] bir dize eşleştirme algoritması belirlemek için benzerlik iki Teller. 1983 yılında John W. Ratcliff ve John A. Obershelp ve yayınlandı Dr. Dobb's Journal Temmuz 1988'de.[2]

Algoritma

İki dizenin benzerliği ve formül tarafından belirlenir, eşleşme sayısının iki katı hesaplanır karakterler her iki dizenin toplam karakter sayısına bölünür. Eşleşen karakterler şu şekilde tanımlanır: en uzun ortak alt dize (LCS) artı tekrarlı LCS'nin her iki tarafındaki eşleşmeyen bölgelerdeki eşleşen karakterlerin sayısı:[2]

[3]

benzerlik metriği sıfır ile bir arasında bir değer alabilir:

1 değeri, iki dizenin tam eşleşmesini ifade ederken, 0 değeri eşleşme olmadığı ve tek bir ortak harf bile olmadığı anlamına gelir.

Örneklem

S1WbenKbenMEDbenBir
S2WbenKbenMBirNbenBir

En uzun ortak alt dize WIKIM (gri) 5 karakterli. Solda başka alt dize yok. Sağ taraftaki eşleşmeyen alt dizeler EDIA ve ANIA. Yine en uzun ortak alt dizeye sahipler IA (koyu gri) uzunluk 2. Benzerlik ölçüsü şu şekilde belirlenir:

Özellikleri

Karmaşıklık

Algoritmanın yürütme zamanı en kötü durumda ve ortalama bir durumda. Hesaplama yöntemini değiştirerek, yürütme süresi önemli ölçüde iyileştirilebilir.[1]

Değişmeli özellik

Gösterilebilir ki Gestalt Desen Eşleştirme Algoritması değişmeli: [4]

Örneklem

İki tel için

ve

için metrik sonucu

dır-dir alt dizelerle GESTALT P, Bir, T, E ve için
metrik alt dizelerle GESTALT P, R, Bir, C, ben.

Başvurular

Algoritma, Python difflib 2.1 sürümünde sunulan kitaplık.[1] Bu benzerlik ölçüsünün olumsuz çalışma zamanı davranışı nedeniyle, üç yöntem uygulanmıştır. İkisi bir üst sınır daha hızlı bir yürütme süresinde.[1] En hızlı varyant yalnızca iki alt dizenin uzunluğunu karşılaştırır:[5]

,
# Python'da Drqr Uygulamasıdef real_quick_ratio(s1: str, s2: str) -> yüzer:    "" "Orana () çok hızlı bir şekilde bir üst sınır dönün." ""    l1, l2 = len(s1), len(s2)    uzunluk = l1 + l2    Eğer değil uzunluk:        dönüş 1.0    dönüş 2.0 * min(l1, l2) / uzunluk

İkinci üst sınır, kullanılan tüm karakterlerin toplamının iki katını hesaplar hangi meydana gelir her iki dizenin uzunluğuna bölünür, ancak sıra dikkate alınmaz.

,
# Python'da Dqr Uygulamasıdef Hızlı oran(s1: str, s2: str) -> yüzer:    "" "Oranın () üst sınırına nispeten hızlı bir şekilde dönün." ""    uzunluk = len(s1) + len(s2)    Eğer değil uzunluk:        dönüş 1.0    kesişmek = koleksiyonlar.Sayaç(s1) & koleksiyonlar.Sayaç(s2)    maçlar = toplam(kesişmek.değerler())    dönüş 2.0 * maçlar / uzunluk

Özellikle aşağıdakiler geçerlidir:

ve
.

Referanslar

  1. ^ a b c d difflib - deltaları hesaplamak için yardımcılar Python belgelerinin içinde
  2. ^ a b c Ulusal Standartlar ve Teknoloji Enstitüsü Ratcliff / Obershelp örüntü tanıma
  3. ^ Ilya Ilyankou: Yazım denetiminde Jaro-Winkler ve Ratcliff / Obershelp algoritmalarının karşılaştırılması, Mayıs 2014 (PDF)
  4. ^ Pythons SequenceMatcher nasıl çalışır? stackoverflow.com adresinde
  5. ^ Python 3.7.0, difflib.py Satır 38–41 ve 676–686'dan ödünç alınmıştır.

daha fazla okuma

  • John W. Ratcliff ve David Metzener: Örüntü Eşleştirme: Gestalt Yaklaşımı, Dr. Dobb's Journal, Sayı 46, Temmuz 1988

Ayrıca bakınız