آموزش

آموزش تطبیق رشته فازی در پایتون

در این آموزش با بررسی مثال های مختلف یاد می‌گیری که چطور رشته‌ها رو به صورت تقریبی با هم تطبیق بدی و میزان شباهت اون‌ها رو تعیین کنی.

تاریخ انتشار:

17 شهریور 1405

پایتون

11 دقیقه

کاربرهای فینکا در چه شرکت‌هایی مشغول به کار هستند؟

تطبیق رشته فازی چیه؟

انسان ممکنه با یه نگاه سریع، منظور کلمه‌ای که غلط املایی داره رو به راحتی متوجه بشه. اما برای کامپیوتر، این تشخیص اصلاً به این سادگی‌ها نیست.

تطبیق رشته فازی در واقع اسم غیررسمی برای همون تطبیق تقریبی رشته‌هاست، ما هم در این آموزش از همون عبارت تطبیق رشته فازی استفاده می‌کنیم. این یه تکنیکه که برای پیدا کردن میزان شباهت بین دو تا رشته متنی که تا حدی به هم شبیه‌ان ولی دقیقاً یکی نیستن، استفاده می‌شه.

ما معمولاً این اتفاق رو در موتورهای جستجو می‌بینیم. مثلاً، اگه کاربر در گوگل به جای «London»، کلمه «Londin» رو تایپ کنه، تطبیق رشته فازی تشخیص می‌ده که منظور کاربر همون «London» بوده و نتایج رو برای کلمه درست میاره.

در این مقاله یاد می‌گیری:

الگوریتم تطبیق رشته فازی چطوری با کمک فاصله ویرایشی لونشتاین (Levenshtein)، میزان شباهت دو تا رشته رو حساب می‌کنه.
چطوری با استفاده از کتابخونه TheFuzz، یه تطبیق رشته فازی ساده رو در پایتون انجام بدی.
بعضی از تکنیک‌های پیشرفته تطبیق رشته فازی به کمک قابلیت‌های پیشرفته TheFuzz چطور کار می‌کنن.
چطوری کتابخونه TheFuzz رو با Pandas ترکیب کنی.

با استفاده از دوره پاک‌سازی داده‌ها در پایتون فینکا، می‌تونی مهارت‌های پایتونیت رو حسابی ارتقا بدی.

ویرایش‌ها و فاصله ویرایشی

الگوریتم تطبیق رشته فازی دنبال اینه که ببینه دو تا رشته مختلف چقدر به هم نزدیک هستن. این کار با بهره‌گیری از یه معیار فاصله به اسم «فاصله ویرایشی» انجام می‌شه. فاصله ویرایشی با پیدا کردن حداقل تعداد «ویرایش‌هایی» که لازمه تا یه رشته به رشته دیگه تبدیل بشه، بهمون نشون می‌ده این دو تا چقدر به هم شبیه‌ان.

اگه فاصله ویرایشی میاد تعداد عملیات‌ها رو می‌شماره تا بگه این دو تا رشته چند قدم با هم فاصله دارن، باید بدونی هر ویرایش در واقع همون عملیاتیه که روی یک رشته انجام می‌شه تا کاملاً شبیه اون یکی بشه.

کلاً چهار نوع اصلی ویرایش داریم:

عملیات ویرایش	توضیحات	مثال
درج	اضافه کردن یه حرف	"Londn" -> "London"
حذف	پاک کردن یه حرف	"Londoon" -> "London"
جابجایی	جابجا کردن دو تا حرف کنار هم	"Lnodon" -> "London"
جایگزینی	تغییر دادن یه حرف به حرف دیگه	"Londin" -> "London"

این چهار تا عملیات، دستِ ما رو باز می‌ذارن تا بتونیم هر رشته‌ای رو به شکل دلخواه تغییر بدیم.

ترکیب این عملیات‌ها با هم بهت اجازه می‌ده لیستی از رشته‌های ممکن رو پیدا کنی که فقط با N ویرایش فاصله دارن (N همون تعداد عملیات‌هاست). مثلاً فاصله ویرایشی بین «London» و «Londin» برابره با ۱، چون فقط با جایگزین کردن «i» با «o»، این دو تا کلمه دقیقاً مثل هم می‌شن.

اما شاید برات سؤال بشه که این فاصله ویرایشی دقیقاً چطوری حساب می‌شه؟

راه‌های مختلفی برای محاسبه‌ش وجود داره. از معروف‌ترین‌هاش می‌تونیم به فاصله لونشتاین، فاصله همینگ، فاصله جارو و موارد مشابه اشاره کنیم.

فاصله لونشتاین چطوری حساب می‌شه؟

در این آموزش، ما فقط روی فاصله لونشتاین تمرکز می‌کنیم.

این معیار به افتخار ولادیمیر لونشتاین اسم‌گذاری شده؛ کسی که اولین بار در سال ۱۹۶۵ ازش برای اندازه‌گیری تفاوت بین دو دنباله از کلمات استفاده کرد. ما هم می‌تونیم ازش استفاده کنیم تا بفهمیم حداقل چند تا ویرایش نیازه تا یه دنباله تک‌کلمه‌ای به یه دنباله دیگه تبدیل بشه.

فرمول رسمیش به این شکله:

$\operatorname{lev}_{a,b}(i,j)= \begin{cases} \max(i,j), & \text{if } \min(i,j)=0, \\[4pt] \min \begin{cases} \operatorname{lev}_{a,b}(i-1,j)+1 \\ \operatorname{lev}_{a,b}(i,j-1)+1 \\ \operatorname{lev}_{a,b}(i-1,j-1)+1_{(a_i \ne b_j)} \end{cases}, & \text{otherwise.} \end{cases}$

اینجا عبارت 1_(a≠b) اگه a=b باشه مقدارش ۰ می‌شه، و در غیر این صورت مقدار ۱ رو برمی‌گردونه.

نکته مهم اینه که توابع حداقلِ (min) سطرهای بالا، به ترتیب مربوط به یه عملیاتِ حذف، درج و جایگزینی هستن.

تازه می‌تونی نسبت شباهت لونشتاین رو هم روی همین فاصله لونشتاین حساب کنی. فرمولش اینه:

$\frac{(|a| + |b|) - lev_{a,b}(i, j)}{|a| + |b|}$

که در اون |a| و |b| نشون‌دهنده طول دنباله a و دنباله b هستن.

تطبیق رشته فازی ساده

یکی از معروف‌ترین پکیج‌ها برای تطبیق رشته فازی در پایتون، تا همین اواخر کتابخونه FuzzyWuzzy بود. ولی خب برای حل یه سری مشکلات لایسنس و آپدیت کردن کدهای قدیمی، این پروژه در سال ۲۰۲۱ اسمش به TheFuzz تغییر کرد. با این حال این کتابخونه به خاطر اینکه خیلی ساده‌ست، هنوزم انتخاب اول تازه‌کارهاست و ما هم در این آموزش با همون پیش می‌ریم.

این کتابخونه اولش توسط شرکت SeatGeek ساخته شد تا بتونن تشخیص بدن آیا دو تا بلیط که اسم‌های شبیهی دارن، برای یه رویداد مشترک هستن یا نه. TheFuzz هم درست مثل نسخه قبلیش، از فاصله ویرایشی لونشتاین برای اندازه‌گیری میزان نزدیکی دو تا رشته استفاده می‌کنه.

نکته حرفه‌ای: برای محیط واقعی (پروداکشن) حتماً از RapidFuzz استفاده کن. با اینکه TheFuzz برای یادگیری و کار روی دیتاست‌های کوچیک خیلی خوبه، ولی برای پردازش داده‌های بزرگ ممکنه لگ ایجاد کنه و کند بشه. الان دیگه صنعت به صورت جدی به سمت یه کتابخونه جدیدتر و بهینه‌تر به اسم RapidFuzz حرکت کرده.

سرعت: RapidFuzz با ++C نوشته شده و به همین دلیل به طرز چشمگیری سریع‌تره.
لایسنس: این کتابخونه از لایسنس MIT بهره می‌بره که برخلاف لایسنس GPL در TheFuzz، برای مصارف شرکتی و تجاری خیلی آزادتر و بی‌دغدغه‌تره.
سازگاری: تقریباً از همون سینتکس‌های رایج (مثلاً fuzz.ratio) استفاده می‌کنه، پس هر وقت رسیدی به پروژه‌های واقعی، می‌تونی خیلی راحت بهش سوییچ کنی.

با همه این حرف‌ها، برای این راهنما ما با همون TheFuzz کار رو جلو می‌بریم؛ چون در اکثر محیط‌ها از قبل نصب شده و برای درک مفاهیم پایه‌ای فوق‌العاده‌ست.

قبل از هر چیزی باید پکیج TheFuzz رو نصب کنیم. می‌تونی این کار رو با استفاده از pip و اجرای دستور زیر تو خط فرمان انجام بدی:

حالا بیا ببینیم با thefuzz چه کارهایی می‌شه کرد.

نسبت ساده

ما با اجرای متد ratio() روی آبجکت fuzz، می‌تونیم نسبت ساده بین دو تا رشته رو پیدا کنیم. این متد، فاصله ویرایشی رو با توجه به ترتیب قرارگیری کاراکترها در رشته‌های ورودی و با کمک difflib.ratio() حساب می‌کنه. اگه دوست داری دقیق‌تر بدونی چطور کار می‌کنه، می‌تونی به مستندات difflib یه سر بزنی.

Similarity Score: 86

در این کد، ما از دو تا حالت مختلفِ نوشتن اسم خودم برای بررسی نمره شباهت استفاده کردیم که نتیجه‌اش شد ۸۶.

حالا بیا اینو با نسبت جزئی (Partial Ratio) مقایسه کنیم.

نسبت جزئی

برای بررسی نسبت جزئی، کافیه به جای ratio() روی آبجکت fuzz، فقط متد partial_ratio() رو صدا بزنیم.

Similarity Score: 67

می‌بینیم که نمره افت کرد. حالا مشکل کجاست؟

خب، متد partial_ratio() سعی می‌کنه ببینه دو تا رشته از نظر جزئی چقدر به هم شبیه‌ان. دو رشته فقط وقتی شباهت جزئی دارن که کلمات مشترکشون دقیقاً با همون ترتیبِ مشابه، در هر دو وجود داشته باشن.

روش کار partial_ratio() این‌طوریه: اول میاد کوتاه‌ترین رشته (که در این مثال در متغیر name ذخیره شده) رو برمی‌داره و اون رو با زیررشته‌هایی که هم‌اندازه خودش هستن، در رشته طولانی‌تر (که در متغیر full_name قرار داره) مقایسه می‌کنه.

از اونجایی که در نسبت جزئی «ترتیب» خیلی مهمه، در این مثال امتیازمون پایین اومد. پس اگه می‌خوای یه تطابق ۱۰۰ درصدی بگیری، باید بخش «K D» (که همون اسم میانی من محسوب می‌شه) رو ببری آخر رشته. مثلاً این‌طوری:

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

خب، اگه بخوایم تطبیق‌دهنده رشته فازی‌مون بی‌خیالِ ترتیب کلمات بشه باید چیکار کنیم؟

در این حالت باید بری سراغ روش نسبت مرتب‌سازی توکن (Token Sort Ratio).

نسبت مرتب‌سازی توکن

خیلی خب، هدف ما اینه که به ترتیب کلمات در رشته‌ها کاری نداشته باشیم ولی همچنان بفهمیم اینا چقدر به هم شبیه‌ان. token_sort دقیقاً همین کار رو برات انجام می‌ده و اصلاً براش مهم نیست که کلمات با چه ترتیبی چیده شدن. با این روش، رشته‌هایی که مثل مثال قبلی فقط ترتیبشون به هم ریخته بود، به عنوان گزینه‌های مشابه در نظر گرفته می‌شن.

پس اگه توی همین مثال آخر بیایم از نسبت مرتب‌سازی توکن استفاده کنیم، قطعاً باید امتیازِ ۱۰۰ بگیریم:

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

… و می‌بینی که همون‌طور که انتظار می‌رفت، دقیقاً همین نتیجه رو گرفتیم.

حالا بیا برگردیم سراغ همون متغیرهای اولیه، یعنی name و full_name. فکر می‌کنی اگه الان از token_sort استفاده کنیم خروجی چی می‌شه؟

Token sort ratio similarity score: 86

همون‌طور که می‌بینی، اینجا امتیاز افت می‌کنه.

دلیلش اینه که token_sort فقط ترتیب رو نادیده می‌گیره. اگه کلماتِ متفاوت و اضافه‌ای در رشته‌ها باشن، همون‌طور که دیدیم، مستقیماً روی امتیاز شباهت تأثیر منفی می‌ذارن.

اما یه راهکار جایگزین هم برای این حالت داریم.

نسبت مجموعه توکن

متد token_set_ratio() واقعاً شبیه همون token_sort_ratio() کار می‌کنه، با این تفاوت مهم که قبل از اینکه شباهت‌ها رو بسنجه، توکن‌های مشترک رو کاملاً حذف می‌کنه. این قابلیت وقت‌هایی که تفاوت طول دو تا رشته زیاده، بدجور به کار میاد.

از اونجایی که هم متغیر name و هم full_name شامل عبارت «Kurtis Pykes» هستن، می‌تونیم انتظار داشته باشیم که نمره این شباهت وقتی از متد نسبت مجموعه توکن استفاده می‌کنیم، روی عدد ۱۰۰ متوقف بشه.

Token sort ratio similarity score: 100

متد process

ماژول process به برنامه‌نویس‌ها اجازه می‌ده تا بتونن با کمک قابلیت‌های تطبیق رشته فازی، یه متنی رو از داخل یه کالکشن یا دیتاست پیدا کنن و بکشن بیرون. اجرای متد extract() روی ماژول process، یه لیستی از رشته‌های مشابه رو به همراه امتیاز شباهتشون داخل یه وکتور (رشته‌ها به شکل لیست تاپل‌ها) برمی‌گردونه. به این مثال دقت کن:

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

با تنظیم پارامتر limit روی هر مقداری که دوست داریم، می‌تونیم تعیین کنیم که متد extract() دقیقاً چند تا نتیجه از اون وکتور برگردونه.

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

در این حالت، متد extract() سه تا از شبیه‌ترین رشته‌ها رو بر اساس همون scorer که بهش دادیم، برمی‌گردونه.

مقایسه تکنیک‌های تطبیق رشته فازی در TheFuzz

در جدول زیر می‌تونی یه مقایسه سریع و راحت بین تکنیک‌های مختلف TheFuzz داشته باشی:

تکنیک	توضیحات	مثال کد
نسبت ساده	میزان شباهت رو با در نظر گرفتن ترتیبِ رشته‌های ورودی حساب می‌کنه.	`fuzz.ratio(name, full_name)`
نسبت جزئی	با مقایسه کوتاه‌ترین رشته با زیررشته‌های معادلش در رشته دوم، شباهت جزئی رو می‌سنجه.	`fuzz.partial_ratio(name, full_name)`
نسبت مرتب‌سازی توکن	ترتیب قرارگیری کلمات در رشته‌ها رو کلاً نادیده می‌گیره.	`fuzz.token_sort_ratio(full_name_reordered, full_name)`
نسبت مجموعه توکن	قبل از اینکه بخواد نمره شباهت رو بده، اول توکن‌های مشترک و تکراری رو حذف می‌کنه.	`fuzz.token_set_ratio(name, full_name)`

تطبیق رشته فازی با Pandas

در این بخش می‌خوایم ببینیم چطوری می‌شه روی یه دیتافریم Pandas تطبیق رشته فازی انجام داد.

فرض کن کلی داده داری که در یه دیتافریم Pandas اکسپورت شدن و حالا می‌خوای اونا رو با یه سری داده موجود دیگه ادغام (join) کنی.

            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

ولی اینجا یه مشکل بزرگ هست.

در داده‌های موجودی که داشتیم، املای اسم کشورها کاملاً درسته، ولی در داده‌های اکسپورت‌شده این‌طوری نیست و غلط املایی دارن. اگه بلند شیم بیایم و این دو تا دیتافریم رو روی ستون کشور به هم متصل کنیم، pandas به خاطر این غلط‌های املایی، کلمات رو با هم برابر نمی‌دونه. نتیجه‌ش این می‌شه که خروجی تابع merge اصلاً اونی درنمیاد که ما انتظار داشتیم.

اگه تستش کنیم، نتیجه این‌طوری می‌شه:

          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

همون‌طور که می‌بینی، این مسئله کلاً هدف ادغام این دیتافریم‌ها رو زیر سؤال می‌بره.

اما جای نگرانی نیست؛ با کمک ابزار قدرتمندی به اسم تطبیق رشته فازی می‌شه راحت این مشکل رو دور زد.

بیا به کد نگاهی بندازیم تا ببینیم قضیه چطوریه:

          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

در این کد، ما با یه تابع جالب lambda که به متد process.extractOne() وصل شده بود، تمام غلط‌های املایی ستون کشور رو در داده‌های اکسپورت‌شده تغییر دادیم تا درست بشن. حواست باشه که ما موقع گرفتن خروجیِ extractOne()، از ایندکس 0 استفاده کردیم تا مستقیماً به خود رشته مشابه برسیم و دیگه کل لیست (که شامل رشته و نمره‌ش هست) رو بهمون پس نده.

در قدم بعدی، دیتافریم‌ها رو بر اساس ستون کشور و با روشِ left join با هم ترکیب کردیم. این‌طوری در نهایت یه دیتافریم کامل داریم که همه‌چیز در اون درسته و املای کشورها کاملاً بی‌نقصه (حتی اسمِ بریتانیا که چندکلمه‌ای بود).

با اینکه این ترفند برای این آموزش و روی دیتاست‌های کوچیک خیلی خوب جواب می‌ده، ولی وقتی پای کلان‌داده‌ها («Big Data») بیاد وسط باید حسابی مراقب باشی.

وقتی روی داده‌های حجیم از .apply() به همراه تطبیق فازی استفاده می‌کنی، کامپیوتر مجبوره تک‌تک سطرهای دیتافریم A رو دونه به دونه با سطرهای دیتافریم B چک کنه (که به این حالت می‌گن ضرب دکارتی).

داده‌های کوچیک: ۱۰۰ سطر ضرب‌در ۱۰۰ سطر می‌شه ۱۰,۰۰۰ مقایسه (که تو یه چشم به هم زدن انجام می‌شه).
داده‌های بزرگ: ۵۰,۰۰۰ سطر ضرب‌در ۵۰,۰۰۰ سطر می‌شه ۲.۵ میلیارد مقایسه (که این کار قطعاً باعث می‌شه سیستم کم بیاره و اسکریپتت کرش کنه).

واسه دیتاست‌هایی که بیشتر از چند هزار تا سطر دارن، بهت پیشنهاد می‌کنم بری سراغ RapidFuzz (که روی موتور ++C می‌چرخه و سرعتش محشره) یا اینکه از Splink استفاده کنی (که با کمک تکنیکی به اسم «بلاک‌بندی»، تعداد این مقایسه‌ها رو فوق‌العاده کم می‌کنه).

تطبیق رشته فازی با دیتافریم‌های Pandas

اگه می‌خوای یه مرور سریع روی چیزایی که تو این بخش یاد گرفتیم داشته باشی، جدول زیر کمکت می‌کنه:

مرحله	توضیحات	قطعه کد
ایجاد دیتافریم‌ها	تعریف داده‌ها و ساخت دیتافریم با در نظر گرفتن اشتباهات املایی احتمالی	`existing_data = pd.DataFrame(dict_one),` `exported_data = pd.DataFrame(dict_two)`
تلاش برای Merge و رسیدن به بن‌بست	متصل کردن اولیه به خاطر عدم تطابق رشته‌ها با شکست مواجه می‌شه	`data = pd.merge(existing_data, exported_data,` `on="country", how="left")`
اصلاح اشتباهات املایی	استفاده از تطبیق فازی برای پیدا کردن و جایگزینی اسم‌های اشتباه کشورها	`exported_data["country"] = exported_data["country"].apply(lambda x:` `process.extractOne(x, existing_data["country"], scorer=fuzz.partial_ratio)[0])`
Merge موفقیت‌آمیز	حالا که اشتباهات با استفاده از تطبیق رشته فازی اصلاح شدن، دیتافریم‌ها رو با خیال راحت به هم متصل می‌کنیم	`data = pd.merge(existing_data, exported_data,` `on="country", how="left")`

حرف آخر

در این آموزش به موضوعات زیر پرداختیم:

ویرایش‌ها و مفهوم فاصله ویرایشی چی هستن.
فاصله ویرایشی لونشتاین چیه و چطوری کار می‌کنه.
چطوری می‌شه با استفاده از کتابخونه thefuzz در پایتون، تطبیق رشته فازی انجام داد.
چطور روی دیتافریم‌های Pandas تطبیق رشته فازی پیاده‌سازی کنیم.

مثال‌هایی که اینجا با هم دیدیم شاید ساده به نظر برسن، اما برای اینکه درک کنی چطوری باید با کلماتی که کامپیوتر فکر می‌کرد با هم فرق دارن کنار بیای، کاملاً کافی بودن. تطبیق فازی کلاً در زمینه‌های مختلفی استفاده می‌شه؛ از غلط‌یاب‌های املایی بگیر تا بیوانفورماتیک که در اون با کمک منطق فازی، دنباله‌های DNA رو بررسی و تطبیق می‌دن.

منابع بیشتر

فهرست مطالب

تطبیق رشته فازی چیه؟
ویرایش‌ها و فاصله ویرایشی
تطبیق رشته فازی ساده
تطبیق رشته فازی با Pandas
حرف آخر

سوالات متداول در مورد تطبیق رشته‌ فازی

تطبیق رشته فازی معمولاً به حروف بزرگ و کوچک حساسه، مگه اینکه خلافش مشخص بشه. برای اینکه این حساسیت رو از بین ببری، می‌تونی قبل از تطبیق، تمام رشته‌ها رو به حروف کوچک تبدیل کنی.

کتابخونه TheFuzz اساساً برای مقایسه رشته‌ها ساخته شده. ولی خب می‌تونی قبل از استفاده از تکنیک‌های تطبیق فازی، بقیه انواع داده رو هم اول به رشته تبدیل و بعد مقایسه کنی.

در دیتاست‌های بزرگ، بهتره از تکنیک‌های اندیس‌گذاری یا فیلتر کردن استفاده کنی تا تعداد مقایسه‌ها کمتر بشه. استفاده از کتابخونه‌هایی مثل RapidFuzz هم که برای سرعت بالا بهینه‌سازی شدن، می‌تونه خیلی عالی باشه.

از تطبیق رشته فازی در کارهایی مثل غلط‌یاب‌های املایی، پاک‌سازی داده‌ها، بیوانفورماتیک (برای هم‌تراز کردن توالی‌های DNA) و پیوند رکوردها در دیتابیس‌ها استفاده می‌شه.

فاصله لونشتاین مواردی مثل درج، حذف و جایگزینی رو در نظر می‌گیره. ولی الگوریتم‌های دیگه‌ای مثل فاصله همینگ (Hamming) فقط جایگزینی رو حساب می‌کنن و برای استفاده ازشون، طول رشته‌ها حتماً باید برار باشه.