الگوریتم  Weighted Edit Distance و نحوه پیاده سازی آن  در Python

در مورد الگوریتم edit distance می توانیم این را بیان کنیم که این الگوریتم برای محاسبه ی میزان تفاوت میان دو رشته است. این اختلاف را می توان با عملیاتی همانند حذف یک کاراکتر، اضافه کردن یک کاراکتر و یا تغییر دو کاراکتر با یکدیگر انجام داد. در واقع بین هر کدام از این عملیات ها باید زیر مجموعه ای را انتخاب کنیم که کمترین عضو را داشته باشد. بایک مثال ادامه میدهیم:form→ fromدر مثال فوق، می توانیم عملیات بسیار زیادی روی رشته ی مبدا یعنی "form" را انجام دهیم ولی مجموعه ای از عملیات بالا که کمترین عضو را داشته باشد مجموعه ی جابه جایی دو کاراکتر "o" و "r" خواهد بود که در این صورت با با هزینه ی فقط یک عملیات می توانیم به نتیجه مورد نظر برسیم و دیگر نیازی به جابه جایی کاراکترها نخواهد بود.عملکرد الگوریتم weighted edit distance همانند الگوریتم edit distance است با این تفاوت که در این الگوریتم، برنامه نویس با توجه به اهمیت و هزینه ی مورد نظر می تواند به هر کدام از عملیاتی که در بالا اشاره شد یک وزن مشخص دهد و هزینه هر کدام از عملیات را خود، مشخص کند.برای مثال، در مثالی که بالا زده شد، فرض کنیم هزینه ی جابه جایی عملیات جابه جایی کاراکترها "3" باشد و همچنین هزینه ی درج و حذف کاراکتر هر دو "1" باشد. در این صورت خواهیم داشت:form→ frm هزینه =1 → هزینه کل =2 form→ from هزینه =1با هزینه ی "2" توانستیم به کلمه ی مورد نظر برسیم اما اگر همانند الگوریتم edit distance عمل میکردیم، هزینه ی عملیاتی که باید انجام می دادیم تا به کلمه ی هدف برسیم، "3" می بود این در حالی است که ما هزینه ی بیشتری باید صرف می کردیم.حالا که در مورد این الگوریتم صحبت شد، قدم به قدم برای پیاده سازی این الگوریتم پیش خواهیم رفت:import sys import string import queue import collections input_file = open(&quotinput.txt&quot, &quotr&quot) first_line = [int(i) for i in input_file.readline().strip().split()] cost_count = len(first_line) add_cost, delete_cost, change_cost, anagram_cost = [int(i) for i in first_line] dict_file = open(&quotwords.txt&quot, &quotr&quot) word_list = dict_file.read().strip().split() dict_file.close() start_word = input_file.readline().strip().lower() end_word = input_file.readline().strip().lower() input_file.close()ورودی برنامه یک فایل تکست خواهد بود به نام "input.txt" در خط اول این تکست، 4 هزینه خواهد داشت:add_cost: هزینه ی اضافه کردن کاراکترdelete_cost: هزینه ی حذف کردن کاراکترchange_cost: هزینه ی جابه جایی دو کاراکترanagram_cost: هزینه ی ساخت یک کلمه با حروف کلمه ی قبلیهمچنین در این فایل دو خط دیگر وجود دارند که خط دوم این فایل متنی کلمه ی ابتدایی که کاربر وارد کرده است می باشد و در خط سوم نیز کلمه ای که هدف و مورد نظر بوده است وارد خواهد شد که این دو کلمه در برنامه در دو متغیر start_word و end_word مقداردهی شده اند.همچنین قطعه کد زیر به این دلیل تعریف شده اند که اگر کلمه مورد نظر در داکیومنت پیدا نشد، پیغام خطایی را به کاربر اعلام کند.if start_word not in word_list: sys.exit(&quotERROR: Starting word is not in the dictionary.&quot) if end_word not in word_list: sys.exit(&quotERROR: Ending word is not in the dictionary.&quot)در قطعه کد زیر نیز دو مقدار solution و min_cost را تعریف می کنیم و مقدار دهی می کنیم تا در مواقع نیاز عموما در توابعی که در ادامه تعریف خواهیم کرد، مقدار آنها را تغییر دهیم(متغیر Global).solution = False min_cost = -1در ادامه یک صف اولیت به نام word_queue و همچنین یک دیکشنری به نام word_costs که هزینه ی کلمه ها در آن ذخیره خواهد شد و یک متغیر به نام alphabet که حروف کوچک را به صورت کاراکترهای اسکی ذخیره میکند و یک مغیر به نام end_len که طول کلمه ی نهایی که قصد رسیدن به آن کلمه را داریم و یک متغیر به نام change_estimate که کمترین مقدار بین change_cost و add_cost + delete_cost را ذخیره می کند را تعریف میکنیم چرا که میخواهیم ببینیم اگر دو کاراکتر را با یکدیگر تغییر بدهیم کم هزینه تر است یا اگر یک کاراکتر را حذف و دیگری اضافه شود کم هزینه تر خواهد بود داریم:word_queue = queue.PriorityQueue() word_costs = {} alphabet = string.ascii_lowercase end_len = len(end_word) change_estimate = min(change_cost, add_cost + delete_cost) در مجموعه فایلی که برای دانلود قرار داده شده است مقدار change_estimate به صورت زیر خواهد بود:change_cost=1add_cost =1delete_cost=3change_estimate = min(change_cost, add_cost + delete_cost)change_estimate = min(1, 4)=1برای هر کدام از عملیاتی که در بالا به آن اشاره شد توابعی را تعریف می کنیم:def add_op(word, cost): #عملیات درج کاراکتر for i in range(len(word) + 1): #در طول کلمه باید جستجو را انجام دهیم for letter in alphabet: #به ازای تمام حروف کاراکتری که به صورت اسکی تعریف کردیم if check_word(word[:i] + letter + word[i:], cost): # check_word فراخوانی تابع # #h+'یکی از حروف اسکی'+lp help برای کلمه ی return def delete_op(word, cost): #عملیات حذف کاراکتر for i in range(len(word)): #در طول کلمه باید جستجو را انجام دهیم if check_word(word[:i] + word[i+1:], cost): #(i=1)کلمه به صورت زیر خواهد بود: #h+'e حذف حرف '+lp help برای کلمه ی return def change_op(word, cost): #عملیات تغییر دو کاراکتر for i in range(len(word)): #در طول کلمه باید جستجو را انجام دهیم for letter in alphabet: #به ازای تمام حروف کاراکتری که به صورت اسکی تعریف کردیم if check_word(word[:i] + letter + word[i+1:], cost): #(i=1)کلمه به صورت زیر خواهد بود: #h+'یکی از حروف اسکی '+p help برای کلمه ی return def anagram_op(word, cost): #عملیات پیدا کردن کلمه ی مشابه for real_word in word_list: #جستجو در تمامی کلمات موجود در داکیومنت کلمات if collections.Counter(real_word) == collections.Counter(word): check_word(real_word, cost, True)برای تابع add_op برای تابع anagram_op میخواهیم دو کلمه ای که تعداد حروف آن ها همانند هم هستند را پیدا کنیم برای این کار از کتابخانه یcollections ،collections.Counter را فراخوانی میکنیم. برای کلمه ی "help" خواهیم داشت:Counter({'h': 1, 'e': 1, 'l': 1, 'p': 1})کلماتی را پیدا خواهیم کرد که این حروف با این تعداد را داشته باشندو آن ها را به تابع check_word برای بررسی خواهیم فرستاد.در ادامه به بررسی تابع check_word می پردازیم:def check_word(word, cost, bypass=False): global solution, min_cost if (word == end_word) and ((not solution) or (cost < min_cost)): #کلمه ای مشابه با عملیات کم # هزینه پبدا کردیم solution = True min_cost = cost print(word) #چاپ کلمه مشابه پیدا شده با هزینه کمتر print(cost) #چاپ هزینه عملیات انجام شده روی کلمه return True elif bypass or (word in word_list): if (word not in word_costs) or \ # در صورتی که کلمه فعلی هزینه عملیاتی بیشتری داشته باشد (word_costs[word] > cost): new_cost = cost + heuristic(word) if (not solution) or (new_cost < min_cost):# در صورتی که هزینه ای که پیدا کرده ایم از کمترین #هزینه ی سابق کمتر باشد word_queue.put((new_cost, word)) #به صف کلمات کلمه ی با عملیات هزینه ی کم را به #همراه هزینه ی آن وارد می کنیم word_costs[word] = cost return Falseدر تابع بالا تابع هیرستیک برای پیدا کردن بهترین کلمه با کمترین هزینه در واقع پیدا کردن هزینه عملیات فراخوانی شده است.این تابع را در ادامه توضیح می دهیم:def heuristic(word): bias = 0 len_dif = len(word) - end_len if len_dif > 0: bias += len_dif * delete_cost else: bias -= len_dif * add_cost bias += max(0, max( len([x for x in word if x not in end_word]) - len_dif, len([x for x in end_word if x not in word]) + len_dif) ) * change_estimate return biasاین تابع کلمه مورد نظر را دریافت می کند سپس طول کلمه دریافت شده را با طول کلمه هدف پیدا می کند اگر بزرگتر از صفر بود(یعنی طول آن از کلمه ی هدف بزرگتر بود)، باید حداکثر یک واحد عملیاتی حذف کاراکتر روی آن اتفاق بیفتد ازین رو به ازای تعداد کاراکتر های اضافی(اختلاف موجود) باید هزینه را متقبل شویم که این هزینه در خط پنجم برنامه ی بالا در متغیر bias ریخته شده است.در غیر این صورت در صورتی که اختلاف کوچکتر از صفر شود، یعنی طول کلمه کمتر از طول کلمه هدف می باشد و باید به ازای هر کلمه ای که باید اضافه شود هزینه محاسباتی اضافه کردن کاراکتر را حساب کنیم که این مقدار مقداری منفی خواهد بود (به دلیل انجام محاسبات در خط سوم قطعه کد بالا) برای اینکه این مقدار را مثبت کنیم مقدار پایه bias را منهای این مقدار میکنیم و چون مقدار اولیه bias صفر می باشد تاثیری در مقدار هزینه نخواهد داشت.در آخر نیز بیشترین مقدار بین 0 (جهت اینکه عددی منفی انتخاب نشود)، تعداد حروفی که در کلمه ی هدف وجود ندارند ولی در کلمه ی فعلی وجود دارند منهای len_dif و طول تعداد حروفی که در کلمه ی هدف وجود دارند ولی در کلمه فعلی وجود ندارند به علاوه ی len_dif به دست خواهد آمد و این مقدار در change_estimate ضرب خواهد شد و متغیر bias برگردانده خواهد شد.در آخر نیز فراخوانی های نهایی برنامه را انجام می دهیم:word_queue.put((0, start_word)) #در خانه ی 0ام صف مقدار کلمه شروع را می گذاریم word_costs[start_word] = 0 #مقدار هزینه ی این کلمه را برابر صفر می گذاریم while not word_queue.empty(): #تا زمانی که صف خالی نشده است حلقه را ادامه می دهیم target = word_queue.get()[1]#هدف مان خانه ی 1ام صف خواهد بود print(target) #هدف مورد نظر را چاپ میکنیم old_cost = word_costs[target] #هزینه قدیمی در ابتدا برابر با هزینه ی هدف خواهد بود if (old_cost > min_cost) and solution: break if (not solution) or (old_cost + add_cost < min_cost): add_op(target, old_cost+add_cost) if ((not solution) or (old_cost + delete_cost < min_cost)) and \ (len(target) > 3): delete_op(target, old_cost+delete_cost) if (not solution) or (old_cost + change_cost < min_cost): change_op(target, old_cost+change_cost) if (not solution) or (old_cost + anagram_cost < min_cost): anagram_op(target, old_cost+anagram_cost) print(min_cost)در صورتی که هزینه ی قبلی به علاوه هزینه اضافه کردن کاراکتر کمتر از کمترین هزینه شد باید تابع اضافه کردن کاراکتر را صدا بزنیم تا چک کنیم آیا این عملیات به صرفه است یا خیر همین شرایط برای توابع دیگر نیز برقرار است.در اخر نیز کمترین هزینه را چاپ می کنیم.تست دیتا برای دو فایل input که لینک های آن ها در ادامه پیوست می شود به صورت زیر است:ورودی Input که شامل کلمه مبدا و کلمه ی هدف و وزن های عملیات ها می باشد:http://s7.picofile.com/d/8378271976/8d5d3896-1412-45e6-99b6-ed145f3f8fee/input.txtورودی فایل کلمات (داکیومنت کلمات):http://s7.picofile.com/d/8378272000/97119817-2619-4726-99b2-8dcb9e94dd85/words.txtنمایش خروجی:healthheathdeathdeashheatsheadsneathbeathhealsheapshearshentshantshands7leathmeathneatsbeachbeadsbeatsdeadsdealsdearsdentsdepthderthfeatshaarsheadyhealdheardhearthheedsheftsherdshestshintshoarshuntskeatsleadsleashmeadsmeatsneapsnearspeatsreadsseatsteatswealthbearsbeatabeatibeethbentsberthcantscentsfearsgearsgentshaetshaftshaltshartshathheapyheartheelsheilsheirshellshelpshempsherlsleapslearsmealsnantspantspealspearsrantsrealsreapsrearsrentssealssearssentstealstearstentsvealsventswantswealswearsyearszealsdash7 موفق باشید?