بهبود ورودی (علم رایانه)
 | این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
 | این مقاله نیازمند تمیزکاری است. لطفاً تا جای امکان آنرا از نظر املا، انشا، چیدمان و درستی بهتر کنید، سپس این برچسب را بردارید. محتویات این مقاله ممکن است غیر قابل اعتماد و نادرست یا جانبدارانه باشد یا قوانین حقوق پدیدآورندگان را نقض کرده باشد. |
در علم کامپیوتر، بهبود ورودی بدین معنی است که پردازش یک ورودی داده شده برای یک مشکل و تغییر آن به روشی خاص، کارایی زمان اجرا یا کارایی فضا یا هر دو را افزایش می‌دهد. ورودی تغییر یافته معمولاً برای ساده کردن مشکل ذخیره شده و قابل دسترسی است. با بهره‌برداری از ساختار و ویژگی‌های ورودی‌ها، بهبود ورودی، سرعت‌های مختلفی را در کارایی الگوریتم ایجاد می‌کند.
جستجوکردن[ویرایش]
بهبود ورودی هنگام جستجو مدتی هست مولفه اصلی دنیای الگوریتم در علم کامپیوتر می‌باشد. ایده اصلی پشت این اصل این است که کارایی جستجو زمانی بسیار سریعتر است که قبل از تلاش برای جستجوی عنصر در ساختار داده، زمان برای ایجاد یا مرتب‌سازی یک ساختار داده از ورودی داده شده صرف شود.
پیش مرتب‌سازی[ویرایش]
پیش مرتب‌سازی یا Presorting تکنیک مرتب‌سازی یک ورودی قبل از جستجوی آن می‌باشد. از آنجایی که افزودن یک جزء مرتب‌سازی به یک الگوریتم به زمان اجرای الگوریتم جستجو افزوده می‌کند و ضرب نمی‌شود، بنابر این تنها برای کندترین بخش الگوریتم رقابت می‌کند. از آنجایی که کارایی الگوریتم‌ها با کندترین مؤلفه اندازه‌گیری می‌شود، اگر جستجو کارآمدتر باشد، افزودن مؤلفه مرتب‌سازی ناچیز است. متأسفانه، پیش مرتب‌سازی معمولاً کندترین مؤلفه الگوریتم است. متضاد، الگوریتم جستجوی بدون پیش‌تنظیم تقریباً همیشه کندتر از الگوریتم پیش‌تنظیم است.
بخش مرتب‌سازی الگوریتم، ورودی مسئله را قبل از رسیدن به بخش جستجوی الگوریتم پردازش می‌کند. مرتب کردن عناصر ورودی به نوعی باعث می‌شود که جستجو در عمل بی‌اهمیت باشد. ساده‌ترین الگوریتم‌های مرتب‌سازی - مرتب‌سازی درج، مرتب‌سازی انتخابی، و مرتب‌سازی حبابی - همگی دارای بدترین زمان اجرا O(n2) هستند، در حالی که الگوریتم‌های مرتب‌سازی پیشرفته‌تر - دسته‌بندی، مرتب‌سازی ادغام - که بدترین زمان اجرا O(n) را دارند . log n) – و Quicksort – که بدترین حالت O(n 2) را دارد اما تقریباً همیشه O(n log n) است. با استفاده از این الگوریتم‌های مرتب‌سازی، یک الگوریتم جستجو که دارای پیش مرتب‌سازی باشد، این کارایی‌های big-O را به همراه خواهد داشت.
یک مثال ساده از مزایای پیش مرتب‌سازی را می‌توان با الگوریتمی مشاهده کرد که یک آرایه را برای عناصر منحصربه‌فرد بررسی می‌کند: اگر آرایه‌ای از n عنصر داده شود، اگر هر عنصر در آرایه منحصربه‌فرد است، true را برگردانید، در غیر این صورت false را برگردانید. کد شبه در زیر ارائه شده‌است :
algorithm uniqueElementSearch (A[0...n]) is for i := 0 to n – 1 do for j := i + 1 to n do if A[i] = A[j] then return false return true
بدون پیش مرتب‌سازی، در بدترین حالت، این الگوریتم مستلزم این است که هر عنصر با هر عنصر دیگر با دو نتیجه ممکن بررسی شود: یا هیچ عنصر تکراری در آرایه وجود ندارد، یا دو عنصر آخر در آرایه تکراری هستند. این منجر به بازده
O (n2) می‌شود.
اکنون این را با الگوریتم مشابهی مقایسه کنید که از پیش مرتب‌سازی استفاده می‌کند. این الگوریتم آرایه ورودی را مرتب می‌کند و سپس هر جفت عنصر را برای یک تکرار بررسی می‌کند. کد شبه در زیر ارائه شده‌است :
algorithm presortUniqueElementSearch(A[0...n]) is sort(A[0...n]) for i := 0 to n – 1 do if A[i] = A[i + 1] then return false return true
همان‌طور که قبلاً گفته شد، کم کارآمدترین بخش این الگوریتم مرتب‌سازی آرایه است که اگر مرتب‌سازی کارآمد انتخاب شود، در O(n log n) اجرا می‌شود. اما پس از مرتب‌سازی آرایه، آرایه فقط باید یک بار پیمایش شود که در O(n) اجرا می‌شود. این منجر به بازده O (n log n) می‌شود.
این مثال ساده نشان می‌دهد که چه چیزی با یک تکنیک بهبود ورودی مانند پیش مرتب‌سازی قابل انجام است. الگوریتم از زمان اجرا درجه دوم به زمان اجرای خطی تبدیل شد که منجر به افزایش سرعت برای ورودی‌های بزرگ می‌شود.
در درختان[ویرایش]
ایجاد ساختارهای داده برای جستجوی کارآمدتر در میان داده‌ها نیز نوعی افزایش ورودی است. قرار دادن داده‌ها در یک درخت برای ذخیره و جستجو از طریق ورودی‌ها یکی دیگر از روش‌های محبوب است. درختان در سراسر علوم کامپیوتر مورد استفاده قرار می‌گیرند و بسیاری از انواع درختان - درختان جستجوی دودویی، درختان AVL، درختان قرمز-مشکی، و ۲–۳ درخت برای نام بردن چند درخت کوچک - برای ذخیره، دسترسی و دستکاری صحیح داده‌ها توسعه داده شده‌اند. ساختار خود را حفظ کنند. درختان یک ساختار داده اصلی برای پیاده‌سازی فرهنگ لغت هستند.
مزایای قرار دادن داده‌ها در یک درخت بسیار زیاد است، به خصوص اگر داده‌ها دستکاری یا به‌طور مکرر جستجو شوند. درخت‌های جستجوی باینری ساده‌ترین و در عین حال رایج‌ترین نوع درخت برای این پیاده‌سازی هستند. درج، حذف و جستجوی اقلام در یک درخت همه در بدترین حالت O(n) هستند، اما اغلب در O(log n) اجرا می‌شوند. این باعث می‌شود جستجوی مکرر عناصر برای ورودی‌های بزرگ سریعتر شود. انواع مختلفی از درخت‌های جستجوی دودویی وجود دارد که با اضافه کردن و حذف آیتم‌ها کارآمدتر عمل می‌کنند و حتی به تعادل می‌رسند، مانند درخت AVL که بدترین حالت O(log n) را برای همه جستجوها، درج‌ها و حذف‌ها دارد.
صرف زمان برای قرار دادن داده‌های ورودی در چنین ساختاری، سرعت بالایی برای جستجوی مکرر عناصر خواهد داشت، برخلاف جستجوی داده‌هایی که بهبود نیافته‌اند.
تطبیق رشته[ویرایش]
در حال حاضر که موتورهای جستجو پیشتاز اینترنت و دنیای آنلاین هستند، تطبیق رشته‌ها یک موضوع پیچیده در دنیای برنامه‌نویسی است. وقتی به یک کلمه کلیدی یا رشته‌ای داده می‌شود که باید در بین میلیون‌ها میلیون کلمه جستجو شود، زمان باورنکردنی برای مطابقت با این کاراکتر رشته در هر کاراکتر طول می‌کشد. بهبود ورودی اجازه می‌دهد تا یک ورودی را تغییر دهید تا این فرایند بسیار سریعتر شود.
الگوریتم brute-force برای این مشکل به صورت زیر عمل می‌کند: وقتی با رشته‌ای از n کاراکتر ارائه می‌شود که اغلب کلید یا الگو نامیده می‌شود، رشته با هر کاراکتر یک رشته طولانی‌تر m که اغلب متن نامیده می‌شود مقایسه می‌شود. اگر یک کاراکتر منطبق رخ دهد، کاراکتر دوم کلید را بررسی می‌کند تا ببیند آیا مطابقت دارد یا خیر. اگر اینطور باشد، کاراکتر بعدی بررسی می‌شود و به همین ترتیب تا زمانی که رشته مطابقت داشته باشد یا کاراکتر بعدی مطابقت نداشته باشد و کل کلید یک کاراکتر را جابجا کند. این کار تا زمانی که کلید پیدا شود یا متن تمام شود ادامه می‌یابد.
این الگوریتم بسیار ناکارآمد است. حداکثر تعداد آزمایش‌های چک m - n +1 آزمایش خواهد بود که بازده big-O را در بدترین حالت O(mn) می‌سازد. در حالت متوسط، حداکثر تعداد آزمایش‌های چک هرگز به دست نمی‌آید و تنها تعداد کمی از آنها اجرا می‌شوند، که منجر به بازده زمانی میانگین O(m + n) می‌شود.
به دلیل لزوم کارآمدتر الگوریتم‌های تطبیق رشته‌ها، چندین الگوریتم سریعتر ایجاد شده‌اند که اکثر آنها از ایده افزایش ورودی استفاده می‌کنند. کلید برای جمع‌آوری اطلاعات در مورد آنچه که باید در متن جستجو شود از قبل پردازش شده‌است و این اطلاعات ذخیره می‌شود تا در صورت لزوم به آنها مراجعه شود. دسترسی به این اطلاعات زمان ثابتی است و کارایی زمان اجرا الگوریتم‌هایی را که از آن استفاده می‌کنند، که معروف‌ترین آنها الگوریتم Knuth-Morris-Pratt و الگوریتم Boyer-Moore است، به شدت افزایش می‌دهد. این الگوریتم‌ها در بیشتر موارد از روش‌های مشابهی برای به دست آوردن کارایی آن استفاده می‌کنند که تفاوت اصلی آن در نحوه ترکیب کلید است.
الگوریتم هورسپول[ویرایش]
به عنوان نمایشی از افزایش ورودی در تطبیق رشته‌ها، باید یک نسخه ساده شده از الگوریتم بویر مور، الگوریتم هورسپول Horspool را بررسی کرد. الگوریتم از نویسه n ام متن m شروع می‌شود و کاراکترها را با هم مقایسه می‌کند. بیایید این کاراکتر را x بنامیم. ۴ مورد احتمالی وجود دارد که در آینده چه اتفاقی می‌افتد.
مورد ۱: اولین مورد ممکن این است که کاراکتر x در کلید نباشد. اگر این اتفاق بیفتد، کل کلید را می‌توان به طول کلید تغییر داد.
مورد ۲: دومین مورد ممکن این است که کاراکتر x کاراکتر فعلی نیست، اما x در کلید است. اگر این اتفاق بیفتد، کلید برای تراز کردن سمت راست‌ترین نویسه x جابجا می‌شود.
مورد ۳: حالت سوم ممکن است این باشد که کاراکتر x با آخرین کاراکتر کلید مطابقت داشته باشد اما سایر کاراکترها کاملاً با کلید مطابقت نداشته باشند و x دوباره در کلید رخ ندهد. اگر این اتفاق بیفتد، کل کلید را می‌توان به طول کلید تغییر داد.
مورد ۴: چهارمین و آخرین مورد ممکن این است که کاراکتر x با کلید مطابقت دارد اما سایر کاراکترها به‌طور کامل با کلید مطابقت ندارند و x دوباره در کلید رخ می‌دهد. اگر این اتفاق بیفتد، کلید برای تراز کردن سمت راست‌ترین رخداد در صورت نویسه x جابجا می‌شود.
این ممکن است به نظر کارآمدتر از الگوریتم brute-force نباشد زیرا باید همه کاراکترها را در هر چک بررسی کند. به هر حال، این چنین نیست. الگوریتم Horspool از یک جدول تغییر برای ذخیره تعداد کاراکترهایی استفاده می‌کند که الگوریتم در صورت اجرا با یک کاراکتر خاص باید تغییر دهد. ورودی در یک جدول با هر کاراکتر ممکنی که می‌توان در متن با آن روبرو شد از قبل محاسبه می‌شود. اندازه شیفت با دو گزینه محاسبه می‌شود: یکی، اگر کاراکتر در کلید نیست، اندازه شیفت n است، طول کلید. یا دو، اگر کاراکتر در کلید ظاهر می‌شود، مقدار تغییر آن فاصله از سمت راست‌ترین نویسه در اولین n -1 کاراکتر در کلید است. به الگوریتم مولد جدول shift کلید و الفبای کاراکترهای احتمالی داده می‌شود که می‌توانند در رشته (K[0... n -1]) به عنوان ورودی ظاهر شوند و جدول shift (T[0... s ) را برمی‌گرداند. -۱]). کد شبه برای تولیدکننده جدول شیفت و نمونه ای از جدول شیفت برای رشته "POTATO" در زیر نمایش داده شده‌است :
algorithm shiftTableGenerator(K[0...n-1]) is for i = 0 to s – 1 do T[i] := m for j := 0 to n – 2 do T[P[j]] := n – 1 – j return T
| character x | A | B | C | ... | O | P | ... | T | ... | Z | _ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| shift value | ۲ | ۶ | ۶ | ۶ | ۴ | ۵ | ۶ | ۱ | ۶ | ۶ | ۶ |
پس از اینکه جدول شیفت در مرحله ارتقای ورودی ساخته شد، الگوریتم کلید را ردیف کرده و اجرا را شروع می‌کند. الگوریتم تا زمانی اجرا می‌شود که زیررشته‌ای منطبق از متن m پیدا شود یا کلید با آخرین کاراکترهای متن m همپوشانی داشته باشد. اگر الگوریتم با یک جفت کاراکتر مواجه شود که مطابقت ندارند، به جدول برای مقدار تغییر کاراکتر دسترسی پیدا می‌کند و بر این اساس جابجا می‌شود. الگوریتم هورسپول کلید (K[0... n -1]) و متن (M[0... m -1]) را می‌گیرد و بسته به این که ایندکس زیررشته منطبق یا رشته «کلید یافت نشد» را خروجی می‌دهد. در نتیجه کد شبه برای الگوریتم Horspool در زیر ارائه شده‌است :
algorithm HorspoolsAlgorithm(K[0...n-1]), M [0...m-1]) is shiftTableGenerator(K[0...n-1]) i:= n – 1 while i ≤ m – 1 do k:= ۰ while k ≤ m – 1 and K[n – 1 – k] = M[i – k] do k:= k + 1 if k = m then return i – n + 1 else i = i + T[M[i]] return “Key not found”
اگرچه ممکن است مشهود نباشد، بدترین کارایی زمان اجرا این الگوریتم O(mn) است. خوشبختانه، در متن‌هایی که تصادفی هستند، بازده زمان اجرا خطی است، O(n/m). این امر الگوریتم Horspool را که از بهبود ورودی استفاده می‌کند، در کلاس بسیار سریع‌تری نسبت به الگوریتم brute-force برای این مشکل قرار می‌دهد.
مفاهیم مرتبط[ویرایش]
افزایش ورودی اغلب به جای یکدیگر استفاده می‌شود پیش محاسباتی و پیش پردازش. اگرچه به هم مرتبط هستند اما چندین تفاوت مهم وجود دارد که باید مورد توجه قرار گیرد.
- پیش محاسباتی و افزایش ورودی گاهی اوقات می‌توانند مترادف استفاده شوند. به‌طور خاص تر، پیش محاسبه، محاسبه یک ورودی داده شده قبل از انجام هر کار دیگری برای ورودی است. اغلب اوقات یک جدول برای بررسی مجدد در طول اجرای واقعی الگوریتم ایجاد می‌شود. افزایش ورودی که مقادیر را محاسبه می‌کند و آنها را به عناصر ورودی اختصاص می‌دهد، می‌تواند به عنوان پیش محاسبه طبقه‌بندی شود، اما شباهت‌ها در اینجا متوقف می‌شوند. بخش‌هایی از بهبود ورودی وجود دارد که از پیش محاسبه استفاده نمی‌کنند و اصطلاحات نباید به‌طور متقابل استفاده شوند.
- وقتی صحبت از تغییر ورودی‌ها می‌شود، اغلب از پیش پردازش سوء استفاده می‌شود. در علوم کامپیوتر، پیش پردازشگر و پیش پردازش کاملاً متفاوت هستند. هنگامی که پیش پردازش در زمینه استفاده می‌شود، هدف معمول به تصویر کشیدن مفهوم افزایش ورودی است، نه استفاده از یک پیش پردازنده. پیاده‌سازی یک پیش پردازنده مفهومی است که در آن یک برنامه یک ورودی را می‌گیرد و آن را به یک خروجی پردازش می‌کند تا به‌طور کامل توسط برنامه دیگری استفاده شود. این به نظر بهبود ورودی است، اما استفاده از پیش پردازنده برای برنامه عمومی اعمال می‌شود که ورودی منبع را پردازش می‌کند تا در قالبی که کامپایلر بتواند بخواند و سپس کامپایل شود، خروجی شود.
منابع[ویرایش]
- لویتین، آنی (۲۰۱۲). مقدمه ای بر طراحی و تحلیل الگوریتم‌ها (ویرایش سوم). پیرسون.شابک ۹۷۸-۰-۱۳-۲۳۱۶۸۱-۱
- سبستا، رابرت دبلیو (۲۰۱۲). مفاهیم زبان‌های برنامه‌نویسی (ویرایش دهم). پیرسون.شابک ۹۷۸−۰−۱۳−۱۳۹۵۳۱−۲شابک 978-0-13-139531-2