توسعه یک الگوریتم ساده و فوق سریع برای پردازش یک متن کوتاه به زبان پایتون

شرح پروژه

سلام

خسته نباشید

ما بر روی پروژه ای کار می کنیم که در بخشی از اون نیاز هست یک رشته ورودی را پردازش کنیم.

به دنبال فردی هستیم که اولا با پایتون براحتی کد نویسی کند و ثانیه بتواند یک الگوریتم و یا یک روش خوب (استفاده از ماژولهای پایتون مجاز است) این کار را انجام دهد. نیاز داریم که سرعت پردازش خیلی خیل بالا باشد چون بعدا روی سرور قرار می گیرد این سیستم.

معما چیست.

فرض کنیم یک دیتابیس حدود 100 هزار رکورد از اسامی افراد (شامل اسم و فامیل و نام پدر) که همگی در یک فیلد هست داریم...یعنی در چند فیلد نیست ... یعنی فیلد نام و نام خانوادگی و غیره از هم جدا نیست..

تصور کنید این دیتابیس 100 هزار رکوردی ما، عملا یک دیشکنری باشد..یعنی هر رکورد یکتاست و تکراری نداریم..لذا 100 هزار نام یکتا...

حالا نیاز چیست:

یک ورودی چند کلمه ای در سیستم وارد می شود..این ورودی باید پردازش شود و شکسته شود به بزرگترین چانک های ممکن ..یعنی بزرگترین اسامی مممکن که با ورودی می تواند نسبت داشته باشد را به ما بدهد...ضمنا بتواند غلط املایی را هم تا حدود مثلا فازی بودن 90% پوشش دهد و ضمنا در گام آخر قادر باشد که بتواند رشته ورودی اگر دارای SPACE نبود هم بتواند آن را بشکند و درست کند..در حوزه پردازش متن، این مقوله معروف به Segmentation و یا گاهی Tokenizing هست.

کتابخانه های مختلفی در پایتون مثل NLTK or SPACY هستند که کار برای پردازش متن را ساده می کنند...ولی هیچ کدام معمای ما را حل نمی کنند..زیرا عمده این کتابخانه ها برای پردازش زبان طبیعی طراحی و تیون شده اند و دیکشنری خودشان را دارند..البته می شود دیکشنری خودمان را بدهیم ..ولی باز ما موفق نشدیم نتیجه درست بگیریم.

برای فهم بهتر معما من یک دیتابیس 10 رکورد نمونه می دهم... و بعد رشته جستجو را هم می دهم..با مطالعه این دو متوجه می شوید که معما چیست.

کلمات ثبت شده در دیتابیس نمونه:

1. محمد علی کشاورز

2. محمد رضا آراسته بیدگلی

3. همایون شجریان اصل شیرازی

4. سهیلا فرامرزی 

5. سید حسن شهامت خواه کشاورزی

6. شایان رسولی فرامرزی

7. مریم السادات شجریان 

8. محمدامین احمدی آراسته

9. همایون

10. مریم

این داده ها هر سطر یک رکورد هست در دیتابیس ما...خیلی ساده...

حالا ورودی مثلا این رشته است:

مریم رسولی فرامرزی همایون شجریان شایان

سیستم باید هوشمندانه این رشته را بشکند به این صورت: مریم - رسولی فرامرزی - همایون شجریان - شایان

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

حالا این مثال ورودی:   محمد علی مریم شجریان سیدحسن اصل شیرازی

خروجی خوب:  محمد علی - مریم شجریان - سید حسن - اصل شیرازی

دقت کنید مثلا مریم شجریان  انتخاب شد چون دارای عناصر مشترک با مریم السادات شجریان بود.

حالا یک مثال سخت تر:

ورودی: محمد غلی کشاور سهیلا مریم شهامث خواه

ورودی دارای غلط های کوچک املایی هست

خروجی خوب: محمد علی کشاورز  - سهیلا - مریم - شهامت خواه

لذا سیستم اگر مثلا یک کلمه 5 حرفی، یک حرفش هم غلط باشد تا مرز 80% تغییر را مچ می کند و اگر تغییر مثلا 50% باشد، مورد قبول نیست..لذا مشابهت 80% به بالا قبول می کنیم و پایین تر کلا مچ نمی شود.

و سخت ترین و نهایی ترین بخش.

ورودی:  همایونمحمدامینسهیلاکشاورزی

خروجی: همایون - محمد امین - سهیلا - کشاورزی

عملا در این مثال کاربر رشته را بدون فاصله درج کرده لذا باید قادر باشیم بدون فاصله هم این تفکیک را انجام دهیم.

همانطور که مشاهده می کنید هدف اصلی سیستم شکستن جمله به نزدیکترین رشته موجود در دیتابیس هست و حتی رفع غلط املایی تا مرز 80% و همچنین پردازش متون به هم چسبیده.

ما فکر می کنیم یک برنامه نویس خبره باید بتواند این معما را در فاصله 5 تا 15 ساعت حل کند. یا از طریق نوشتن یک الگوریتم کاملا جدید یا کمک از ماژولهای دیگر که ممنوعیت ندارد

دقت کنید دیتابیس ما حدود 100 هزار رکورد دارد..می شود این را در حافظه آورد ..هدف ما شکشستن این جمله در حدود کمتر از 1 میلی ثانیه هست در سروری با 8 هسته پردازش کننده و 16 گیگ رم.

لطفا اگر سوالی دارید برای ما بفرستید

با تشکر

کاشیان

مهارت ها و تخصص های مورد نیاز

درباره کارفرما

kashian

عضویت پنج سال پیش

1 پروژه ثبت شده ،

0 پروژه در حال انجام ،

0 پروژه آماده دریافت پیشنهاد ،

نرخ پذیرش پیشنهاد 0%