موضوع مقاله: بهبود ورودی (علم رایانه) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بهبود ورودی (علم رایانه) | مقدمه: در علوم رایانه، بهبود ورودی یا «تقویت ورودی» به معنای پردازش و تغییر ورودی‌های یک مسئله به‌گونه‌ای است که کارایی الگوریتم‌ها از نظر زمان اجرا یا مصرف حافظه بهبود یابد. | ## بخش 1: بهبود ورودی (علم رایانه) | برای مثال، مرتب‌سازی داده‌ها پیش از جست‌وجو یا ساختاردهی آن‌ها در درخت‌های جست‌وجو می‌تواند سرعت پردازش را افزایش دهد. این روش با بهره‌گیری از ویژگی‌ها و ساختارهای خاص ورودی، عملکرد الگوریتم‌ها را بهینه می‌کند. به عبارتی دیگر، بهبود ورودی بدین معنی است که پردازش یک ورودی داده شده برای یک مشکل و تغییر آن به روشی خاص، کارایی زمان اجرا یا کارایی فضا یا هر دو را افزایش می‌دهد. با بهره‌برداری از ساختار و ویژگی‌های ورودی‌ها، بهبود ورودی، سرعت‌های مختلفی را در کارایی الگوریتم ایجاد می‌کند. جستجوکردن بهبود ورودی هنگام جستجو مدتی هست مولفه اصلی دنیای الگوریتم در علم کامپیوتر می‌باشد. ایده اصلی پشت این اصل این است که کارایی جستجو زمانی بسیار سریعتر است که قبل از تلاش برای جستجوی عنصر در ساختار داده، زمان برای ایجاد یا مرتب‌سازی یک ساختار داده از ورودی داده شده صرف شود. از آنجایی که افزودن یک جزء مرتب‌سازی به یک الگوریتم به زمان اجرای الگوریتم جستجو افزوده می‌کند و ضرب نمی‌شود، بنابر این تنها برای کندترین بخش الگوریتم رقابت می‌کند. از آنجایی که کارایی الگوریتم‌ها با کندترین مؤلفه اندازه‌گیری می‌شود، اگر جستجو کارآمدتر باشد، افزودن مؤلفه مرتب‌سازی ناچیز است. متضاد، الگوریتم جستجوی بدون پیش‌تنظیم تقریباً همیشه کندتر از الگوریتم پیش‌تنظیم است. بخش مرتب‌سازی الگوریتم، ورودی مسئله را قبل از رسیدن به بخش جستجوی الگوریتم پردازش می‌کند. ساده‌ترین الگوریتم‌های مرتب‌سازی - مرتب‌سازی درج، مرتب‌سازی انتخابی، و مرتب‌سازی حبابی - همگی دارای بدترین زمان اجرا O(n2) هستند، در حالی که الگوریتم‌های مرتب‌سازی پیشرفته‌تر - دسته‌بندی، مرتب‌سازی ادغام - که بدترین زمان اجرا O(n) را دارند . با استفاده از این الگوریتم‌های مرتب‌سازی، یک الگوریتم جستجو که دارای پیش مرتب‌سازی باشد، این کارایی‌های big-O را به همراه خواهد داشت. یک مثال ساده از مزایای پیش مرتب‌سازی را می‌توان با الگوریتمی مشاهده کرد که یک آرایه را برای عناصر منحصربه‌فرد بررسی می‌کند: اگر آرایه‌ای از n عنصر داده شود، اگر هر عنصر در آرایه منحصربه‌فرد است، true را برگردانید، در غیر این صورت false را برگردانید. این الگوریتم آرایه ورودی را مرتب می‌کند و سپس هر جفت عنصر را برای یک تکرار بررسی می‌کند. اما پس از مرتب‌سازی آرایه، آرایه فقط باید یک بار پیمایش شود که در O(n) اجرا می‌شود. این مثال ساده نشان می‌دهد که چه چیزی با یک تکنیک بهبود ورودی مانند پیش مرتب‌سازی قابل انجام است. الگوریتم از زمان اجرا درجه دوم به زمان اجرای خطی تبدیل شد که منجر به افزایش سرعت برای ورودی‌های بزرگ می‌شود. در درختان ایجاد ساختارهای داده برای جستجوی کارآمدتر در میان داده‌ها نیز نوعی افزایش ورودی است. قرار دادن داده‌ها در یک درخت برای ذخیره و جستجو از طریق ورودی‌ها یکی دیگر از روش‌های محبوب است. | ## بخش 2: بهبود ورودی (علم رایانه) | درختان در سراسر علوم کامپیوتر مورد استفاده قرار می‌گیرند و بسیاری از انواع درختان - درختان جستجوی دودویی، درختان AVL، درختان قرمز-مشکی، و ۲–۳ درخت برای نام بردن چند درخت کوچک - برای ذخیره، دسترسی و دستکاری صحیح داده‌ها توسعه داده شده‌اند. مزایای قرار دادن داده‌ها در یک درخت بسیار زیاد است، به خصوص اگر داده‌ها دستکاری یا به‌طور مکرر جستجو شوند. درخت‌های جستجوی باینری ساده‌ترین و در عین حال رایج‌ترین نوع درخت برای این پیاده‌سازی هستند. درج، حذف و جستجوی اقلام در یک درخت همه در بدترین حالت O(n) هستند، اما اغلب در O(log n) اجرا می‌شوند. انواع مختلفی از درخت‌های جستجوی دودویی وجود دارد که با اضافه کردن و حذف آیتم‌ها کارآمدتر عمل می‌کنند و حتی به تعادل می‌رسند، مانند درخت AVL که بدترین حالت O(log n) را برای همه جستجوها، درج‌ها و حذف‌ها دارد. صرف زمان برای قرار دادن داده‌های ورودی در چنین ساختاری، سرعت بالایی برای جستجوی مکرر عناصر خواهد داشت، برخلاف جستجوی داده‌هایی که بهبود نیافته‌اند. تطبیق رشته در حال حاضر که موتورهای جستجو پیشتاز اینترنت و دنیای آنلاین هستند، تطبیق رشته‌ها یک موضوع پیچیده در دنیای برنامه‌نویسی است. وقتی به یک کلمه کلیدی یا رشته‌ای داده می‌شود که باید در بین میلیون‌ها میلیون کلمه جستجو شود، زمان باورنکردنی برای مطابقت با این کاراکتر رشته در هر کاراکتر طول می‌کشد. بهبود ورودی اجازه می‌دهد تا یک ورودی را تغییر دهید تا این فرایند بسیار سریعتر شود. الگوریتم brute-force برای این مشکل به صورت زیر عمل می‌کند: وقتی با رشته‌ای از n کاراکتر ارائه می‌شود که اغلب کلید یا الگو نامیده می‌شود، رشته با هر کاراکتر یک رشته طولانی‌تر m که اغلب متن نامیده می‌شود مقایسه می‌شود. اگر یک کاراکتر منطبق رخ دهد، کاراکتر دوم کلید را بررسی می‌کند تا ببیند آیا مطابقت دارد یا خیر. اگر اینطور باشد، کاراکتر بعدی بررسی می‌شود و به همین ترتیب تا زمانی که رشته مطابقت داشته باشد یا کاراکتر بعدی مطابقت نداشته باشد و کل کلید یک کاراکتر را جابجا کند. در حالت متوسط، حداکثر تعداد آزمایش‌های چک هرگز به دست نمی‌آید و تنها تعداد کمی از آنها اجرا می‌شوند، که منجر به بازده زمانی میانگین O(m + n) می‌شود. به دلیل لزوم کارآمدتر الگوریتم‌های تطبیق رشته‌ها، چندین الگوریتم سریع‌تر ایجاد شده‌اند که اکثر آنها از ایده افزایش ورودی استفاده می‌کنند. کلید برای جمع‌آوری اطلاعات در مورد آنچه که باید در متن جستجو شود از قبل پردازش شده‌است و این اطلاعات ذخیره می‌شود تا در صورت لزوم به آنها مراجعه شود. این الگوریتم‌ها در بیشتر موارد از روش‌های مشابهی برای به دست آوردن کارایی آن استفاده می‌کنند که تفاوت اصلی آن در نحوه ترکیب کلید است. الگوریتم هورسپول به عنوان نمایشی از افزایش ورودی در تطبیق رشته‌ها، باید یک نسخه ساده شده از الگوریتم بویر مور، الگوریتم هورسپول Horspool را بررسی کرد. مورد ۲: دومین مورد ممکن این است که کاراکتر x کاراکتر فعلی نیست، اما x در کلید است. مورد ۳: حالت سوم ممکن است این باشد که کاراکتر x با آخرین کاراکتر کلید مطابقت داشته باشد اما سایر کاراکترها کاملاً با کلید مطابقت نداشته باشند و x دوباره در کلید رخ ندهد. | ## بخش 3: بهبود ورودی (علم رایانه) | مورد ۴: چهارمین و آخرین مورد ممکن این است که کاراکتر x با کلید مطابقت دارد اما سایر کاراکترها به‌طور کامل با کلید مطابقت ندارند و x دوباره در کلید رخ می‌دهد. اگر این اتفاق بیفتد، کلید برای تراز کردن سمت راست‌ترین رخداد در صورت نویسه x جابجا می‌شود. الگوریتم Horspool از یک جدول تغییر برای ذخیره تعداد کاراکترهایی استفاده می‌کند که الگوریتم در صورت اجرا با یک کاراکتر خاص باید تغییر دهد. ورودی در یک جدول با هر کاراکتر ممکنی که می‌توان در متن با آن روبرو شد از قبل محاسبه می‌شود. اندازه شیفت با دو گزینه محاسبه می‌شود: یکی، اگر کاراکتر در کلید نیست، اندازه شیفت n است، طول کلید. یا دو، اگر کاراکتر در کلید ظاهر می‌شود، مقدار تغییر آن فاصله از سمت راست‌ترین نویسه در اولین n -1 کاراکتر در کلید است. به الگوریتم مولد جدول shift کلید و الفبای کاراکترهای احتمالی داده می‌شود که می‌توانند در رشته (K[0... الگوریتم تا زمانی اجرا می‌شود که زیررشته‌ای منطبق از متن m پیدا شود یا کلید با آخرین کاراکترهای متن m همپوشانی داشته باشد. اگر الگوریتم با یک جفت کاراکتر مواجه شود که مطابقت ندارند، به جدول برای مقدار تغییر کاراکتر دسترسی پیدا می‌کند و بر این اساس جابجا می‌شود. m -1 را می‌گیرد و بسته به این که ایندکس زیررشته منطبق یا رشته «کلید یافت نشد» را خروجی می‌دهد. مفاهیم مرتبط افزایش ورودی اغلب به جای یکدیگر استفاده می‌شود پیش محاسباتی و پیش پردازش. اگرچه به هم مرتبط هستند اما چندین تفاوت مهم وجود دارد که باید مورد توجه قرار گیرد. به‌طور خاص تر، پیش محاسبه، محاسبه یک ورودی داده شده قبل از انجام هر کار دیگری برای ورودی است. افزایش ورودی که مقادیر را محاسبه می‌کند و آنها را به عناصر ورودی اختصاص می‌دهد، می‌تواند به عنوان پیش محاسبه طبقه‌بندی شود، اما شباهت‌ها در اینجا متوقف می‌شوند. بخش‌هایی از بهبود ورودی وجود دارد که از پیش محاسبه استفاده نمی‌کنند و اصطلاحات نباید به‌طور متقابل استفاده شوند. هنگامی که پیش پردازش در زمینه استفاده می‌شود، هدف معمول به تصویر کشیدن مفهوم افزایش ورودی است، نه استفاده از یک پیش پردازنده. پیاده‌سازی یک پیش پردازنده مفهومی است که در آن یک برنامه یک ورودی را می‌گیرد و آن را به یک خروجی پردازش می‌کند تا به‌طور کامل توسط برنامه دیگری استفاده شود. | ## جمع‌بندی | این به نظر بهبود ورودی است، اما استفاده از پیش پردازنده برای برنامه عمومی اعمال می‌شود که ورودی منبع را پردازش می‌کند تا در قالبی که کامپایلر بتواند بخواند و سپس کامپایل شود، خروجی شود.