در این مطلب، روش تطبیق رشته تقریبی و تشخیص رشته‌های مشابه با بهره‌گیری از مثال‌های گوناگون، آموزش داده خواهد شد. تمرکز این نوشته بر روش «تطبیق رشته فازی» (Fuzzy String Matching) در پایتون است.

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

تاکنون، برای افراد زیادی پیش آمده که نیاز به مقایسه کردن رشته‌هایی پیدا می‌کنند که به چیز مشابهی ارجاع دارند، ولی به شیوه‌ای تقریبا متفاوت نوشته شده‌اند. این تفاوت، ممکن است ناشی از اشکال تایپی یا نگارشی باشد. مساله بیان شده، چالشی است که افراد ممکن است در شرایط گوناگون، از نرم‌افزارهای بررسی نگارش گرفته تا نگاشت «پایگاه‌داده‌ها» (Databases) که فاقد یک کلید مشترک هستند (مثلا در شرایطی که فرد سعی دارد دو جدول را بر اساس نام شرکت به یکدیگر متصل کند، اما به نظر می‌رسد این مورد در دو جدول متفاوت است)، با آن مواجه شوند.

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

خروجی

True

قطعه کد بالا به این صورت عمل می‌کند که اگر دو رشته مقایسه شده با یکدیگر تطابق داشته باشند (شباهت صد در صدی) پیغام True (به معنای درست) را نمایش می‌دهد. در ادامه، کد بالا روی دو رشته دیگر اعمال شده، تا مشخص شود که در صورت عدم مطابقت دو رشته، قطعه کد چه خروجی را نمایش می‌دهد.

خروجی

False

همانطور که مشهود است، هنگامی که دو رشته با یکدیگر مشابه نباشند، پیام False (به معنای غلط) روی صفحه چاپ می‌شود. این در حالی است که امکان دارد رشته‌های داده شده به کد، با چشم انسانی مشابه به نظر برسند. در مثال ارائه شده در بالا، تفاوت دو رشته در استفاده از حروف بزرگ (A) و کوچک انگلیسی (a) در نوشتن کلمه apple است. البته، مساله موجود در رشته‌های مثال بالا به این شکل قابل حل است که هر دو رشته را ابتدا به حروف کوچک تبدیل و سپس آن‌ها را با یکدیگر مقایسه کرد.

خروجی

True

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

خروجی

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

فاصله لون‌اشتاین

فاصله لون‌اشتاین، سنجه‌ای است که برای اندازه‌گیری فاصله دو توالی از کلمات مورد استفاده قرار می‌گیرد. به بیان دیگر، فاصله لون‌اشتاین حداقل تعداد ویرایش‌هایی که برای تغییر توالی یک کلمه به دیگری مورد نیاز است را اندازه‌گیری می‌کند. این ویرایش‌ها، شامل «درج» (Insert)، «حذف» (Delete) یا «جایگزینی» (Substitute) می‌شوند. این سنجه، به افتخار «ولادیمیر لون‌اشتاین» (Vladimir Levenshtein) که برای اولین بار این فاصله را در سال 1۹۶۵ معرفی کرد، لون‌اشتاین نام‌گذاری شده است. تعریف رسمی فاصله لون‌اشتاین بین دو رشته a و b به صورت زیر است.

$$ {\displaystyle \qquad \operatorname {lev} _{a,b}(i,j)={\begin{cases}\max(i,j)&{\text{ if }}\min(i,j)=0,\\\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}\neq b_{j})}\end{cases}}&{\text{ otherwise.}}\end{cases}}} $$

در رابطه بالا، $$ \large 1_ { ( a _ i \ne b_ j ) } $$ هنگامی که a=b است، برابر با صفر و در غیر این صورت برابر با یک است. شایان توجه است که سطرها در حداقل (Min) بالا، متناظر با یک حذف، یک درج و یک جایگزینی در آن ترتیب هستند. همچنین، این امکان وجود دارد که نرخ مشابهت لون‌اشتاین بر پایه فاصله لون‌اشتاین محاسبه شود. این کار با استفاده از فرمول زیر، انجام پذیر است.

$$\frac{(|a| + |b|) – {lev}_{a,b}(i,j)}{|a| + |b|}$$

در رابطه بالا، |a| و |b| به ترتیب طول‌های توالی a و توالی b هستند. در قطعه کد زیر، پیاده‌سازی فرمول بالا با استفاده از تابع پایتون انجام شده است.

در صورت اعمال این تابع روی مثال‌های اولیه‌ای که در این مطلب ارائه شد، می‌توان مشاهده کرد که دو عبارت «Apple Inc» و «apple Inc» بسیار مشابه هستند. زیرا فاصله لون‌اشتاین آن‌ها بسیار ناچیز است.

خروجی

The strings are 2 edits away
0.8421052631578947

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

خروجی

The strings are 1 edits away
0.9473684210526315

همانطور که در خروجی قابل مشاهده است، با انجام یک پیش‌پردازش کوچک و تبدیل رشته‌ها به حروف کوچک (تنها یک کاراکتر تغییر کرد)، خروجی افزایش قابل توجهی پیدا کرد و تقریبا برابر با ۹۵٪ شد. این امر، تاکید بر اهمیت پیش‌پردازش رشته‌ها پیش از انجام پردازش تطبیق رشته دارد. در صورتی که آستانه تعیین مشابهت روی ۹۰٪ تنظیم شده باشد، «Apple Inc» و «apple Inc» بدون انجام پیش‌پردازش، غیر مشابه تشخیص داده می‌شوند. با وجود آنکه روش ارائه شده در بالا به منظور پیاده‌سازی فاصله لون‌اشتاین به درستی عمل می‌کند، اما راه ساده‌تری برای انجام این کار در پایتون وجود دارد. بسته لون‌اشتاین حاوی دو تابع است که کاری مشابه تابع بالا انجام می‌دهند.

خروجی

توجه: به این نکته لازم است که در پیاده‌سازی پایتون ارائه شده در بالا، توضیحاتی وجود دارد که بیان می‌کند، هنگامی که نرخ مشابهت محاسبه شد، هزینه جایگزینی به جای 1،‌ برابر با 2 خواهد بود. این امر بدین دلیل است که ()lev.ratio چنین هزینه‌ای را به یک جایگزینی تخصیص می‌دهد (شرایطی قابل تصور است که نیاز به حذف، درج و جایگزینی به طور هم‌زمان باشد). اگرچه، هزینه جایگزینی در ()lev.distance برابر با یک است. پس در صورت تمایل به اعتبارسنجی خروجی‌های تابع به صورت دستی، باید به این نکته توجه داشت.

بسته FuzzyWuzzy در پایتون

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

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

خروجی

95

این نسبت مشابه با آنچه است که در مثال بالا مشاهده شد. اگرچه، fuzzywuzzy دارای توابع قدرتمندتری است که امکان مدیریت شرایط‌های پیچیده‌تر مانند تطبیق «زیر رشته» را فراهم می‌کند. در ادامه، مثالی برای این مورد آورده شده است.

خروجی

50
100

()fuzz.partial_ratio قادر به شناسایی این مورد است که هر دو رشته به Lakers اشاره دارند. بدین ترتیب، مقدار مشابهت را ٪1۰۰ تعیین می‌کند. روش کار این تابع به این صورت است که از یک « منطق بهینه جزئی» (Optimal Partial Logic) استفاده می‌کند. به عبارت دیگر، اگر رشته کوتاه دارای طول k و رشته بلند دارای طول m باشد، الگوریتم به دنبال امتیاز بهترین زیررشته تطبیق یافته با طول k می‌گردد. با این اوصاف، روش مذکور بدون خطا نخواهد بود. اگر دو رشته مقایسه شده مشابه ولی ترتیب آن‌ها متفاوت باشد، چه می‌شود؟ خوشبختانه، fuzzywuzzy راهکاری برای حل این مشکل دارد. مثال زیر قابل توجه است.

خروجی

59
74
100

توابع fuzz.token، دارای یک مزیت مهم نسبت به تابع‌های ratio و partial_ratio هستند. آن‌ها، رشته‌ها را نشانه‌گذاری و با تبدیل به حروف کوچک‌تر و حذف نشانه‌های سجاوندی، «پیش‌پردازش» (Preprocessing) می‌کنند. با بهره‌گیری از ()fuzz.token_sort_ratio، توکن‌های رشته‌ها به صورت الفبایی مرتب و سپس به یکدیگر ملحق (Join) می‌شوند. پس از آن، یک ()fuzz.ratio ساده برای به دست آوردن درصد مشابهت اعمال می‌شود. انجام چنین کاری، این قابلیت را فراهم می‌کند تا در مثال‌هایی مانند court (مثال ارائه شده در کد زیر)، موارد به عنوان مشابه تعیین شوند. اما اگر دو رشته دارای طول متفاوتی باشند چه؟ در اینجا است که پای ()fuzz.token_set_ratio به میان می‌آید. مثال زیر در همین رابطه است.

57
77
58
95

مشابهت ٪۹۵ یک معجزه نیست، بلکه حاصل انجام پیش‌پردازش است. ()fuzz.token_set_ratio نسبت به ()fuzz.token_sort_ratio دارای رویکرد انعطاف‌پذیرتری است. به جای «نشانه‌گذاری» (Tokenization) رشته‌ها، مرتب‌سازی و مجددا چسباندن نشانه‌گذاری‌های کنار هم، token_set_ratio عملیاتی را انجام می‌دهد که نشانه‌گذاری‌های متداول را دریافت کرده (تقاطع) و سپس، ()fuzz.ratio مقایسه دو به دو را میان رشته‌های جدید زیر انجام می‌دهد.

  • s1 = Sorted_tokens_in_intersection
  • s2 = Sorted_tokens_in_intersection + sorted_rest_of_str1_tokens
  • s3 = Sorted_tokens_in_intersection + sorted_rest_of_str2_tokens

منطق نهفته در پس این مقایسه‌ها آن است که نظر به مشابهت همیشگی Sorted_tokens_in_intersection، امتیاز گرایش به بالاتر بودن دارد؛ زیرا این کلمات بخش بزرگتری از رشته اصلی را تشکیل می‌دهند و یا نشانه‌گذاری‌های باقی‌مانده به یکدیگر نزدیک‌تر هستند. در نهایت، بسته fuzzywuzzy دارای ماژولی با عنوان process است که امکان محاسبه رشته با بالاترین مشابهت را از یک بردار از رشته‌ها فراهم می‌کند. نحوه کار آنچه بیان شد، در مثال زیر قابل مشاهده است.

خروجی

[('Apple Inc.', 100), ('apple incorporated', 90), ('apple park', 67), ('iphone', 30)]
('Apple Inc.', 100)

در این راهنما، چگونگی تطبیق رشته تقریبی و تعیین میزان مشابهت دو رشته آموزش داده شد. مثال‌های ارائه شده در اینجا ممکن است ساده باشند، اما برای درک چگونگی انجام تطبیق رشته فازی در شرایط گوناگون کافی هستند. کاربردها و مزایای تطبیق رشته فازی، محدود به آنچه در اینجا بیان شد نیست. در مسائلی مانند غلط‌یابی (Spell Checking) و یا در بیوانفورماتیک برای تطبیق توالی DNA نیز از تطبیق رشته فازی استفاده می‌شود. کاربردهای متنوع دیگری نیز برای این کار وجود دارند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *