Python'da Bulanık Dize Eşleştirme Eğitimi

Düzenlemeler ve düzenleme mesafesi

Bulanık dize eşleştirme algoritması, iki farklı dizenin birbirine ne kadar yakın olduğunu belirlemeye çalışır. Bu da “düzenleme mesafesi” olarak bilinen bir uzaklık metriği kullanılarak bulunur. Düzenleme mesafesi, bir dizenin diğerine dönüştürülmesi için gereken en az sayıda “düzenleme”yi bularak iki dizenin ne kadar yakın olduğunu belirler. 

Eğer düzenleme mesafesi bize bir dizenin diğerinden kaç işlem uzakta olduğunu söylemek için düzenleme işlemlerinin sayısını sayıyorsa, bir düzenleme, bir dizenin başka bir dizeye dönüştürülmesi için o dize üzerinde gerçekleştirilen bir işlemdir.  

Dört temel düzenleme türü vardır:

Bu dört düzenleme işlemi, herhangi bir dizenin değiştirilmesini mümkün kılar. 

Düzenleme işlemlerini birleştirmek, N düzenleme uzakta olan olası dizelerin listesini keşfetmenizi sağlar; burada N, düzenleme işlemlerinin sayısıdır. Örneğin “London” ile “Londin” arasındaki düzenleme mesafesi birdir; çünkü “i”nin “o” ile değiştirilmesi tam eşleşmeye götürür. 

Peki düzenleme mesafesi tam olarak nasıl hesaplanır?

Düzenleme mesafesini hesaplamanın farklı varyasyonları vardır. Örneğin Levenshtein mesafesi, Hamming mesafesi, Jaro mesafesi ve daha fazlası.

Levenshtein Mesafesi nasıl hesaplanır?

Bu eğitimde yalnızca Levenshtein mesafesi ile ilgileniyoruz. 

Bu metrik, iki kelime dizisi arasındaki farkı ölçmek için 1965'te ilk olarak bunu ele alan Vladimir Levenshtein'in adını taşır. Tek bir kelime dizisini diğerine dönüştürmek için yapmanız gereken en az sayıda düzenlemeyi bulmak için kullanabiliriz. 

Resmî hesaplama şöyledir: 

Burada a=b iken 0'ı, aksi halde 1'i ifade eder. 

Yukarıdaki minimumdaki satırların sırasıyla silme, ekleme ve yerine koymaya (ikameye) karşılık geldiğini not etmek önemlidir.

Levenshtein mesafesine dayanarak Levenshtein benzerlik oranını hesaplamak da mümkündür. Bu, aşağıdaki formülle yapılabilir:

burada |a| ve |b| sırasıyla a ve b dizilerinin uzunluklarıdır.

Basit Bulanık Dize Eşleştirme

Python'da bulanık dize eşleştirme için en popüler paketlerden biri tarihsel olarak FuzzyWuzzy idi. Ancak lisans sorunlarını çözmek ve kod tabanını güncellemek için proje 2021'de TheFuzz olarak yeniden adlandırıldı. Sadelik nedeniyle yeni başlayanlar için hâlâ başvurulan bir kütüphanedir ve bu eğitimde kullanacağımız kütüphanedir.

İlk olarak SeatGeek tarafından, benzer isimlere sahip iki bilet ilanının aynı etkinlik için olup olmadığını ayırt etmek amacıyla geliştirildi. Selekörü gibi TheFuzz, iki dize arasındaki yakınlığı hesaplamak için Levenshtein düzenleme mesafesini kullanır.

İpucu: Üretimde RapidFuzz kullanın. TheFuzz öğrenme ve küçük veri kümeleri için mükemmel olsa da, büyük ölçekli veri işleme için yavaş kalabilir. Sektör büyük ölçüde RapidFuzz adlı daha yeni bir kütüphaneye yönelmiştir.

• Hız: RapidFuzz C++ ile yazılmıştır, bu da onu belirgin biçimde daha hızlı kılar.
• Lisans: TheFuzz’ın GPL lisansına kıyasla kurumsal kullanım için daha esnek olan MIT lisansını kullanır.
• Uyumluluk: Neredeyse aynı söz dizimini kullanır (ör. fuzz.ratio), dolayısıyla daha sonra kolayca geçiş yapabilirsiniz.

Bu rehberde, birçok ortamda önceden yüklü geldiği ve temel kavramları anlamak için ideal olduğu için TheFuzz ile devam edeceğiz.

Önce TheFuzz paketini kurmalıyız. Bunu aşağıdaki komutla pip kullanarak yapabilirsiniz: 

!pip install thefuzz

Not: Bu kütüphane DataLab çalışma kitabında önceden yüklüdür. 

Şimdi, thefuzz ile neler yapabileceğimize bir göz atalım. 

Bu DataLab çalışma kitabındaki kodla birlikte ilerleyin. 

Basit oran

İki dize arasındaki basit oranı, fuzz nesnesi üzerindeki ratio() yöntemiyle belirleyebiliriz. Bu, her iki giriş dizisinin sıralamasına dayanarak düzenleme mesafesini hesaplar difflib.ratio() – daha fazla bilgi için difflib belgelerine bakın. 

# Check the similarity score
name = "Kurtis Pykes"
full_name = "Kurtis K D Pykes"

print(f"Similarity score: {fuzz.ratio(name, full_name)}")

"""
Similarity Score: 86
"""

Kodda, adımın iki varyasyonunu benzerlik puanını karşılaştırmak için kullandık ve sonuç 86 olarak verildi. 

Bunu kısmi oranla karşılaştıralım. 

Kısmi oran 

Kısmi oranı kontrol etmek için yukarıdaki kodda yapmamız gereken tek şey ratio() yerine fuzz nesnemizde partial_ratio() çağırmaktır. 

# Check the similarity score
name = "Kurtis Pykes"
full_name = "Kurtis K D Pykes"

print(f"Similarity score: {fuzz.partial_ratio(name, full_name)}")

"""
Similarity Score: 67
"""

Bir düşüş görüyoruz. Ne oluyor? 

partial_ratio(), iki dizenin kısmen ne kadar benzer olduğunu bulmaya çalışır. İki dize, ortak bir sırada bazı kelimelere sahipse kısmen benzerdir. 

partial_ratio(), daha kısa olan diziyi alarak (bu senaryoda name değişkeninde saklanmıştır) daha uzun dizide (full_name) aynı uzunluktaki alt dizelerle karşılaştırıp benzerliği hesaplar. 

Kısmi oranda sıralama önemli olduğundan, bu örnekte puanımız düştü. Dolayısıyla %100 benzerlik eşleşmesi için, "K D" kısmını (ikinci adımı ifade ediyor) dizenin sonuna taşımanız gerekir. Örneğin: 

# Order matters with partial ratio
# Check the similarity score
name = "Kurtis Pykes"
full_name = "Kurtis Pykes K D"
​
print(f"Partial ratio similarity score: {fuzz.partial_ratio(name, full_name)}")
​
# But order will not effect simple ratio if strings do not match
print(f"Simple ratio similarity score: {fuzz.ratio(name, full_name)}")

"""
Partial ratio similarity score: 100
Simple ratio similarity score: 86
"""

Peki bulanık dize eşleştiricimizin sıralamayı görmezden gelmesini istersek? 

O zaman “token sort ratio”yu kullanmak isteyebilirsiniz. 

Token sort ratio

Tamam, dizelerdeki kelimelerin sıralamasını yok saymak ama yine de ne kadar benzer olduklarını belirlemek istiyoruz – token sort tam olarak bunu yapmanıza yardımcı olur. Token sort, kelimelerin hangi sırayla geçtiğiyle ilgilenmez. Yukarıda açıklandığı gibi, sırada olmayan benzer dizeleri hesaba katar. 

Dolayısıyla, en son örnekte token sort ratio kullanarak %100 puan almalıyız: 

# Check the similarity score
full_name = "Kurtis K D Pykes"
full_name_reordered = "Kurtis Pykes K D"
​
# Order does not matter for token sort ratio
print(f"Token sort ratio similarity score: {fuzz.token_sort_ratio(full_name_reordered, full_name)}")
​
# Order matters for partial ratio
print(f"Partial ratio similarity score: {fuzz.partial_ratio(full_name, full_name_reordered)}")
​
# Order will not effect simple ratio if strings do not match
print(f"Simple ratio similarity score: {fuzz.ratio(name, full_name)}")

"""
Token sort ratio similarity score: 100
Partial ratio similarity score: 75
Simple ratio similarity score: 86
"""

… ve beklendiği gibi aldık. 

Orijinal name ve full_name değişkenlerine geri dönelim. Şimdi token sort kullanırsak ne olacağını düşünüyorsunuz? 

# Check the similarity score
name = "Kurtis Pykes"
full_name = "Kurtis K D Pykes"

print(f"Token sort ratio similarity score: {fuzz.token_sort_ratio(name, full_name)}")

"""
Token sort ratio similarity score: 86
"""

Puan düşüyor. 

Bunun nedeni token sort'un yalnızca sıralamayı görmezden gelmesidir. Dizelerde benzer olmayan kelimeler varsa, yukarıda gördüğümüz gibi bu durum benzerlik oranını olumsuz etkiler.

Ancak bir çözüm yolu var. 

Token set ratio

token_set_ratio() yöntemi token_sort_ratio()ya oldukça benzer, ancak benzerliği hesaplamadan önce ortak tokenları çıkarır: bu, dizelerin uzunlukları önemli ölçüde farklı olduğunda son derece yararlıdır. 

Hem name hem de full_name değişkenleri “Kurtis Pykes”ı içerdiğinden, token set ratio benzerliğinin %100 olmasını bekleyebiliriz. 

# Check the similarity score
name = "Kurtis Pykes"
full_name = "Kurtis K D Pykes"
​
print(f"Token sort ratio similarity score: {fuzz.token_set_ratio(name, full_name)}")

"""
Token sort ratio similarity score: 100
"""

Process 

Process modülü, kullanıcıların bir koleksiyondan bulanık dize eşleştirme kullanarak metin çıkarmasını sağlar. Process modülünde extract() yöntemini çağırmak, benzerlik puanlarıyla birlikte dizeleri bir vektörde döndürür. Örneğin: 

from thefuzz import process
​
collection = ["AFC Barcelona", "Barcelona AFC", "barcelona fc", "afc barcalona"]
print(process.extract("barcelona", collection, scorer=fuzz.ratio))

"""
[('barcelona fc', 86), ('AFC Barcelona', 82), ('Barcelona AFC', 82), ('afc barcalona', 73)]
"""

extract() yönteminin döndürdüğü vektörün uzunluğunu, limit parametresini istenen uzunluğa ayarlayarak kontrol edebiliriz.

print(process.extract("barcelona", collection, scorer=fuzz.ratio))

"""
[('barcelona fc', 86), ('AFC Barcelona', 82), ('Barcelona AFC', 82)]
"""

Bu örnekte, extract() tanımladığımız skorlayıcıya göre en yakın üç eşleşen diziyi döndürür. 

TheFuzz ile bulanık dize eşleştirme tekniklerinin karşılaştırması

Aşağıdaki tabloda, TheFuzz içinde bulunan farklı tekniklerin hızlı bir karşılaştırmasını görebilirsiniz: 

pandas ile Bulanık Dize Eşleştirme

Bu bölümde, bir pandas veri çerçevesinde bulanık dize eşleştirme yapmayı göreceğiz. 

Diyelim ki bir veriyi pandas veri çerçevesine aktardınız ve bunu elinizdeki mevcut verilerle birleştirmek istiyorsunuz. 

import pandas as pd
​
# Creating a dataframe
dict_one = {
  "country": ["England", "Scotland", "Wales", "United Kingdom", "Northern Ireland"],
  "population_in_millions": [55.98, 5.45, 3.14, 67.33, 1.89]
}
​
dict_two = {
  "country": ["Northern Iland", "Wles", "Scotlnd", "Englnd", "United K."],
  "GDP_per_capita": [24900, 23882, 37460, 45101, 46510.28]
}
​
existing_data = pd.DataFrame(dict_one)
exported_data = pd.DataFrame(dict_two)
​
print(existing_data, exported_data, sep="\n\n")

"""
          country  population_in_millions
0           England                   55.98
1          Scotland                    5.45
2             Wales                    3.14
3    United Kingdom                   67.33
4  Northern Ireland                    1.89

          country  GDP_per_capita
0  Northern Iland        24900.00
1            Wles        23882.00
2         Scotlnd        37460.00
3          Englnd        45101.00
4       United K.        46510.28
"""

Önemli bir sorun var. 

Mevcut verilerde ülkelerin doğru yazımları varken, dışa aktarılan verilerde yok. İki veri çerçevesini country sütununda birleştirmeye çalışırsak, pandas yanlış yazılmış kelimeleri doğru yazılmış kelimelerle eşit olarak tanımaz. Dolayısıyla merge işlevinden dönen sonuç beklendiği gibi olmayacaktır. 

Deneseydik ne olacağı aşağıda: 

# Attempt to join the two dataframe
data = pd.merge(existing_data, exported_data, on="country", how="left")
print(data.head())

"""
          country  population_in_millions  GDP_per_capita
0           England                   55.98             NaN
1          Scotland                    5.45             NaN
2             Wales                    3.14             NaN
3    United Kingdom                   67.33             NaN
4  Northern Ireland                    1.89             NaN
"""

Bu, bu veri çerçevelerini birleştirme girişiminin tüm amacını boşa çıkarır. 

Ancak, bu sorunu bulanık dize eşleştirme ile aşabiliriz.

Kodda nasıl göründüğüne bakalım: 

# Rename the misspelled columns
exported_data["country"] = exported_data["country"].apply(
  lambda x: process.extractOne(x, existing_data["country"], scorer=fuzz.partial_ratio)[0]
)
​
# Attempt to join the two dataframe
data = pd.merge(existing_data, exported_data, on="country", how="left")
print(data.head())

"""
          country  population_in_millions  GDP_per_capita
0           England                   55.98        45101.00
1          Scotland                    5.45        37460.00
2             Wales                    3.14        23882.00
3    United Kingdom                   67.33        46510.28
4  Northern Ireland                    1.89        24900.00
"""

Bu kodda, dışa aktarılan verilerin country sütunundaki yanlış yazılmış değerleri, process.extractOne() yöntemiyle birlikte kullandığımız şık bir lambda işleviyle yeniden adlandırdık. Dikkat edin, yalnızca benzer dizeyi döndürmek için extractOne() sonucunda 0 indeksini kullandık; böylece dize ve benzerlik değerini içeren bir liste yerine doğrudan dizeyi aldık. 

Ardından, veri çerçevelerini country sütununda sol birleştirme ile birleştirdik. Sonuç, doğru yazılmış ülkeleri (Birleşik Krallık'ın siyasi birliği dahil) içeren tek bir veri çerçevesidir.

Yukarıdaki çözüm bu eğitim ve küçük veri kümeleri için mükemmel olsa da, bunu "Büyük Veri"ye uygularken dikkatli olun.

Bulanık eşleştirme ile .apply() kullandığınızda, bilgisayar A veri çerçevesindeki her bir satırı B veri çerçevesindeki her bir satırla karşılaştırmak zorundadır (Kartezyen Çarpım).

• Küçük Veri: 100 satır x 100 satır = 10.000 karşılaştırma (Anında).
• Büyük Veri: 50.000 satır x 50.000 satır = 2,5 milyar karşılaştırma (Bettiğinizi çökertir).

Birkaç bin satırı aşan veri kümeleri için, hız için C++ kullanan RapidFuzzu veya karşılaştırmaları azaltmak için "bloklama" kullanan Splinki düşünün.

pandas DataFrame'leri ile bulanık dize eşleştirme

Yukarıda bahsedilen tekniklere hızlı bir özet gerekiyorsa, bunları aşağıdaki tabloda bulabilirsiniz: 

Son düşünceler

Bu eğitimde şunları öğrendiniz: 

• Düzenlemeler ve düzenleme mesafesi
• Levenshtein düzenleme mesafesi ve nasıl çalıştığı
• Python'da thefuzz kütüphanesiyle bulanık dize eşleştirme nasıl yapılır
• Pandas veri çerçeveleriyle bulanık dize eşleştirme nasıl yapılır. 

Buradaki örnekler basit olabilir, ancak bir bilgisayarın eşleşmiyor olarak düşündüğü çeşitli dize durumlarının nasıl ele alınacağını göstermek için yeterlidir. Yazım denetimi ve biyoinformatik gibi alanlarda, DNA dizilerini eşleştirmek için bulanık mantığın kullanıldığı birçok bulanık eşleştirme uygulaması vardır.

Ek Kaynaklar

• Python Dize Eğitimi
• Python Dize İçerir Eğitimi
• Python'da Düzenli İfadeler kursu
• Python Düzenli İfadeler Eğitimi