حل جدول كلمات متقاطع فارسي با تكنيك‌هاي پردازش زبان طبيعي

Solving Persian Crosswords with Natural Language Processing Techniques

در اين مقاله، به معرفي راهكارهايي براي حل جدول كلمات متقاطع توسط ماشين با استفاده از تكنيك‌هاي پردازش زبان طبيعي مي‌پردازيم. اين كار به دو زيروظيفه يافتن كلمات محتمل براي هر شرح جدول و سپس انتخاب كلمه هدف و جايگذاري در جدول تقسيم مي شود. زيروظيفه اول كه به يافتن كلمه از روي توصيف آن اختصاص دارد داراي كاربردهاي متعدد ديگر نيز هست. به اين منظور از تركيبي از روش‌هاي مختلف شامل جستجو و شباهت‌يابي معنايي روي دادگان جداول حل شده قبلي، جستجو در فرهنگ لغات و دانشنامه ويكي‌پديا، استفاده از مدل زباني ماسك شده و يافتن كلمات مرتبط در فارس‌نت و ابزار فارسي‌يار استفاده نموديم. نتايج نشان مي‌دهند تركيب اين روش‌ها نسبت به اجراي تك تك آن‌ها نتيجه بهتري (فراخواني 82%) در برداشته است. در زيروظيفه بعد ليست پاسخ‌هاي محتمل را به يك الگوريتم جستجو با ارضاء قيود مي‌دهيم تا با درنظر گرفتن قيود جدول از ميان پاسخ‌ها، پاسخ درستي كه مي‌تواند در جدول قرار گيرد را انتخاب كرده و خانه‌هاي خالي را به بهترين شكل پر كند و جدول را حل كند. ارزيابي كل نشانگر دقت ۸۰.۲۲٪ و فراخواني ۶۸.۸۶٪ در حل جدول كلمات متقاطع است.

In this article, we introduce solutions for solving crossword puzzles by machine using natural language processing techniques. This task is divided into two subtasks of finding possible answers for each table description and then selecting the target word and placing it in the table. The first subtask, which is dedicated to finding the word from its description, has many other uses as in text generation and paraphrasing. For this purpose, we used a combination of different methods, including searching and finding semantic similarities on the data of previously solved tables, searching in dictionary and Wikipedia articles, using a masked language model, and finding related words in Farsnet and the Farsiyar tool. The results show that the combination of these methods has a better result (82% recall) compared to their individual implementation. In the next subtask, we give the list of possible answers to a constraint-satisfaction search algorithm to choose the correct answer that can be placed in the table, taking into account the constraints of the table, and fill the empty cells in the best way and solve the crossword. The overall evaluation shows 80.22% precision and 68.86% recall in solving the crossword puzzle.