الگوریتم چینش حروف صفحه كلید موبایل ( مقاله )

[Admin]

جستجوي چينش بهينه حروف فارسي برروي صفحه كليد تلفن همراه با استفاده از الگوريتم ژنتيك


مقاله ای از : حمیده فعال

تهیه و تنظیم : سایت علمی نخبگان جوان

[Admin]

چکیده


* استفاده ازالگوريتمهاي پيش بيني براي حدس زدن حرف مورد نظر كاربر به هنگام فشردن هر كليد .
* نحوه پراکنده شدن حروف بر روی صفحه کلید
* بدليل اينكه يافتن چينش بهينه، يك مسأله بغرنج به شمار مي آيد معمولاً از روشهاي مكاشفه اي براي حل اين مسأله استفاده ميشود.
* استفاده ازالگوريتم ژنتيك براي جستجوي چينش بهينه حروف فارسي برروي صفحه كليد تلفن همراه .

[Admin]

مقدمه:

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

* روش های پیش بینی حرف موردنظر در صفحه کلید ترکیبی
* روش های مبتنی بر کلمه: پیش بینی پس از وارد کردن تمامی حروف یک کلمه انجام میشود.
مثال: اگر کاربر کلیدهای 2و3و5 را به ترتیب بفشارد توالی حروف « ب پ ت ث» ،« آ ا ء» ، « د ذ ر زژ» مشخص میشود. و الگوریتم پیش بینی باید تمام کلماتی که از ترکیب این حروف بدست می آید را پیدا کند.
* روشهای مبتنی بر حرف: پیش بینی بر اساس N حرف قبلی انجام میشود که معمولاً N<4 >2 می باشد.

http://www.esnips.com/nsdoc/856733a9-8617-4e05-91f3-38695532ddd2

• الگوریتم n-gram
– الگوريتم پيش بيني، آخرين N حرف قبلی را در نظر گرفته و احتمال هر یک از حروفی که روی کلید فشرده شده قرار دارند را از یک جدول احتمالات استخراج میکند. سپس حرف محتملتر به نمایش در می آید.
• به دلیل بغرنج بودن این مسأله از الگوریتم های مکاشفه ای برای حل آن استفاده میشود.
• با استفاده از الگوریتم ژنتیک استفاده از چینش های یافت شده باعث میشود خطای الگوریتم پیش بینی n-gram برای حروف فارسی بیش از 30 درصد کاهش یابد.
تعریف مسئله:
• تعریف مسأ له چینش حروف برای صفحه کلید ترکیبی
– مسأ له بهینه سازی چینش حروف برای صفحه کلیدهای ترکیبی که از الگوریتم پیش بینی مبتنی بر حرف استفاده می کنند به این صورت تعریف میشود:
چگونه می توان M حرف را بر روی N کلید طوری پراکنده کرد که وقتی از الگوریتم پیش بینی
P برای حدس زدن حرف مورد نظر کاربر استفاده می کنیم بتوانیم با کمترین میزان فشردن کلیدها
متن T را وارد نماییم.
– Pهمان الگوریتم n-gram است.
– جدول احتمال حروف یک ماتریس M^n×M است. تعداد سطرهای این ماتریس برابر است با تعداد رشته های مختلف به طول n که میتوان با M حرف ایجاد نمود.
– اين جدول را با پيمايش متن T مي توان بدست آورد . ميتوان از روشهاي نگهداري ماتريس هاي اسپارس براي ذخيره سازي آن استفاده نمود تا ازنظر حافظه با مشكل روبرو نشويم..
• برای محاسبۀ تعداد کل حالات می توان این مسأ له را به این صورت بیان کرد:
به چند طریق میتوان M شیء مجزا را به N گروه تقسیم نمود.بنابراین اندازۀ فضای جستجو برابر است با:
Search Space= N^M / N!
– اینکه هرگروه از حروف روی کدام کلید قرار دارد مهم نیست.
– مهم این است که هر حرف با چه حروف دیگری هم گروه شده است.
– در اینجا تعداد حروف فارسی را 34 تا درنظر گرفته ایم. 32حرف الفبای فارسی بعلاوۀ حروف آ و ء.
– در اکثر گوشی های موبایل تعداد کلیدها یی که حروف بر روی آن قرار می گیرند 8 تا است بنابراین تعداد کل حالات ممکن برای مسأ له ما برابر است با : 1.2 * 10^26

[Admin]

ارزیابی صفحه کلید:

– معیار keystroke efficiency :
– بازدمان بررسی هر کلید انتخاب شده برای اطمینان یافتن از اینکه برای عملی مناسب است. یا شمارش انتخابهای کلید انجام شده برای محاسبۀ هزینۀ تایپ.
– برابر است با طول متن ورودی بر حسب کاراکتر تقسیم بر تعداد دفعات فشردن کلیدهای صفحه کلید.
– معکوس این معیار بیانگر میانگین تعداد کلیدهایی است که برای تولید یک کاراکتر باید فشرده شود.
– برای اینکه نتایج شبیه سازی دقیق باشد باید از یک متن طولانی استفاده شود که با توجه به زمانگیر بودن الگوریتم های تکاملی زمان مورد نیاز برای محاسبۀ معیار ارزیابی افزایش می یابد.
– برای حل این مشکل با توجه به الگوریتم پیش بینی Pومتن T ماتریس بهم ریختگی ایجاد میشود.
ماتریس بهم ریختگی
• اگر حروف الفبا را با A1,A2,…,Am نشان دهیم این ماتریس یک ماتریس M*M است که خا نه ( i ,j) آن نشان می دهد که اگر از الگوريتم پيش بيني P براي وارد كردن متن T استفاده نماییم ، الگوریتم پیش بینی احتمال حرف Aj را بیش از Ai بدست آورده است.
• هرچه مقدار خانۀ (i,j) بیشتر باشد نشان دهندۀ این است که اگر دو حرف Ai وAj بر روی یک کلید قرار گیرند احتمال خطای پیش بینی بیشتر میشود.
• به ازای هردو حرف Ai وAj که بر روی یک کلید قرار دارند مقدار خانه های ( i , j ) و ( j,i )را از ماتریس بهم ریختگی استخراج و با هم جمع میکنیم.
الگوریتم ژنتیک برای جستجوی چینش بهینه
• یادآوری از مطالب الگوریتم ژنتیک:
– از روشهای متداول برای بهینه سازی مسائل بغرنج( NP-hard ) است.
– با تولید مجموعه ای از جوابها به صورت تصادفی آغاز میشود.
– باید تابع هدف و تابع تناسب مشخص شوند.
– تابع هدف تابعی است که قصد بهینه سازی آن را داریم. و برای مسأ له ما همان keystroke efficiency است.
– تابع تناسب تابعی است که میزان شایستگی هر یک از کروموزوم های موجود در یک نسل را مشخص میکند.
– محاسبۀ مقدار تابع تناسب با توجه به تابع هدف برای هر کروموزوم :
• روش اول : استفاده از خود تابع هدف یا حالت تغییر یافتۀ آن به عنوان تابع تناسب
• روش دوم : مرتب کردن کروموزوم های یک نسل بر اساس مقدار تابع هدف آنها و امتیاز دادن بر مبنای رتبه.
کد کردن پارامترهای فضای جستجو در قالب کروموزوم ها
• برای مسأ له چینش M حرف بر روی N کلید، هر کروموزوم را یک رشته به طول M در نظر میگیریم که مقدار هر مولفۀ آن میتواند بین 1 تا N باشد.
• هر مولفه از این رشته متعلق به یک حرف از حروف الفباست. حروفی که مقدار مولفۀ مربوط به آنها با هم برابر باشند در یک کلید قرار میگیرند.
• برای عملگر انتخاب از روش roulette wheel selection استفاده میشود.
• برای عمل ترکیب از عملگر ترکیب دودویی یکنواخت استفاده میشود.
• عملگر جهش:
• انتخاب تصادفی یک مولفه از یک کروموزوم و مقداردهی مجدد آن به طور تصادفی بین 1 تا N
• انتخاب تصادفی دو مولفه از یک کروموزوم و جابجا کردن مقادیر آنها با یکدیگر
• پارامترهای دیگر الگوریتم ژنتیک:
• تعداد جمعیت : 100
• تعداد نسل ها : 500
• نرخ جهش : 0.3
• نرخ نخبه گرایی : 0.01


نتایج آزمایشات


• الگوریتم n-gram به کمک یک ماتریس که در آن احتمال وقوع هر یک از حروف پس از هر رشته به طول n ثبت شده است ، حرف مورد نظر کاربر را پیش بینی میکند.
• برای ساخت این ماتریس از یک متن که از 1420000 حرف تشکیل شده استفاده میکنیم.
• چهار ماتریس احتمال وقوع حروف را به ازای n<=4 =>1 ایجاد میکنیم. پس 4 الگوریتم پیش بینی n-gram ایجاد میشود.
• استفاده از الگوریتم ژنتیک برای هر یک از این 4 الگوریتم پیش بینی.

• برای ارزیابی چینش های یافت شده توسط الگوریتم ژنتیک متن دیگری که از 160000 حرف تشکیل شده را تهیه میکنیم.
• در الگوریتم n-gram اگر از جداول احتمال وقوع حروف برای پیش بینی داده های تست استفاده شود وقتی n بزرگ باشد (n=4 ) خطای پیش بینی زیاد میشود.
• برای رفع این مشکل دو راه حل وجود دارد:
– استفاده از داده های آموزشی بسیار حجیم تر برای ساخت جدول احتمال وقوع حروف
– استفاده از جداول احتمال مربوط به n های کمتردر هنگام عدم وجود رشته موردنظر در جدول احتمال مربوط به n
• جدول زیر معیار keystroke efficiency را برای صفحه کلید فعلی تلفن همراه و صفحه کلیدهای بدست آمده از الگوریتم ژنتیک برای هر یک از 4 الگوریتم پیش بینی نشان میدهد.

http://www.esnips.com/imageable/medium/99f0a9ba-b1c1-4358-81d9-acd514cba656/?du=a5dfe3bd-3f0c-416f-9930-fce031780632&uu=3e3678a6-4179-4e77-8260-1862294adf5d&dt=1199305313000&fu=0ce6580b-0010-4f3c-9fac-e924bb86823f

• با افزایش مقدار n کارایی صفحه کلید برای داده های آموزشی و داده های تست افزایش می یابد.
• مقادیر داخل پرانتز، میزان کاهش خطای الگوریتم پیش بینی را برای صفحه کلیدهای بدست آمده از الگوریتم ژنتیک نسبت به صفحه کلید فعلی نشان میدهد.

• شکل زیرصفحه کلیدی که از الگوریتم ژنتیک برای الگوریتم پیش بینی 4-gram بدست آمده را نشان میدهد.

[Admin]

صفحه كليد يافت شده توسط الگوريتم ژنتيك

برای الگوریتم پیش بینی 4-gram

http://www.esnips.com/nsdoc/5bce3c4b-3064-4bfd-a11c-c8ab6c2f2483

جمع بندی و کارهای آتی

• معیار ارزیابی چینش های مختلف، دقت الگوریتم های پیش بینی حروف در هنگام فشردن کلیدها توسط کاربر می باشد.
• با تغییر چینش فعلی میتوان خطای الگوریتم های پیش بینی را بیش از 30 درصد کاهش داد.
• الگوریتم های پیش بینی برای حروف فارسی نسبت به حروف انگلیسی اندکی ضعیف عمل میکند.
• پیشنهاد میشود یک بستر داده ای استاندارد برای پیام های کوتاه تهیه شود تا محققان دیگر بتوانند با مشقات کمتر نتایج مطمئن تری را ارائه نمایند.
• برای کلمات انگلیسی پایگاه داده ای تشکیل شده که میزان تکرار هر یک از کلمات در متون انگلیسی در آن مشخص شده که از بررسی یکصد میلیون کلمه موجود در کتابهای مختلف بدست آمده است. بهتر است چنین پایگاه دادۀ مفیدی نیز برای کلمات فارسی تهیه شود.

[Admin]

فهرست منابع

• وفا غفاريان، معاون وزير ارتباطات، ۱۱ آذر ۱۳۸۵
http://www.favanews.com/default.aspx/news_18111.htm
• Lissa W. Light and Peter G. Anderson, “Typewriter keyboards via simulated annealing”, AI Expert, September 1993.
• M. O. Wagner, B Yannou, S. Kehl, D. Feillet, and J. Eggers, “Ergonomic Modeling and optimization of keyboard arrangement with an ant colony algorithm”, European Journal of Operation research, 2003.
• Rau, H., and Skiena, S.S., “Dialing for documents: An experiment in information theory”. Proc. UIST 1994, ACM Press, pp. 147-155, 1994