ابزار آنالیز استاتیک کد در اندروید استودیو — راهنمای مقدماتی

آنالیز استاتیک یا آنالیز استاتیک کد نوعی از آنالیز است که بر مبنای برخی قواعد تعیین‌شده و پیش از اجرای برنامه و معمولاً حتی پیش از تست unit، روی کد منبع اعمال می‌شود. این نوعی از دیباگ کردن است که بدون اجرای برنامه انجام می‌یابد و معمولاً نخستین گام در جهت آنالیز کد محسوب می‌شود. از آنجا که این آنالیز بر مبنای برخی قواعد تعیین‌شده اجرا می‌شود به حفظ قراردادهای درون تیم توسعه برای نگهداری از کد کمک می‌کند.

اجرای این آنالیز به صورت دستی در طی فرایند مرور کد ممکن است، اما در این حالت احتمال بروز خطاهای انسانی بالا است و چندان کارآمد یا مؤثر نیست. برای حل این مشکل برخی ابزارهای خودکار سازی جالب مانند lint ابداع شده‌اند که اینک به صورت آماده در اندروید استودیو جای گرفته‌اند و می‌توانیم از آن‌ها استفاده کنیم. در این نوشته، قصد داریم از یک چنین ابزاری بهره جسته و به عنوان نمونه یک پروژه اندروید را مورد بررسی قرار دهیم.

Lint کردن به چه معنا است؟

Lint کردن با پیروی از قواعدی که در یک فایل پیکربندی مانند lint.xml تعریف‌ شده‌اند صورت می‌گیرد. سپس ابزار lint این قواعد را با فایل‌های کد منبع بررسی می‌کند. برای این که درک بهتری به دست آورید به تصویر زیر مراجعه کنید:

استفاده از Lint در پروژه

دو روش برای انجام این کار وجود دارد که یکی از آن‌ها بهره‌گیری از اندروید استودیو و دیگری استفاده از ترمینال و gradle است.

استفاده از اندروید استودیو

دو روش برای اجرای ابزار lint روی کد منبع وجود دارد. می‌توان این کار را از نوارابزار Analyze > Inspect Code اجرا کرد. سپس یک کادر گفتگو باز می‌کنیم که در آن می‌توان دامنه کد منبع را برای اجرای ابزار lint تعیین کرد. در تصویر زیر مثالی از آن را می‌بینید:

پس از مدتی اندروید استودیو نتایج را در پنجره Inspection results به صورت تصویر زیر نمایش می‌دهد:

استفاده از gradle

برای اجرای lint از gradle، می‌توانید از دستورهای زیر استفاده کنید.

• روی ویندوز: gradlew lint
• روی لینوکس یا مک: gradlew lint/.

دقت کنید که هنگام اجرای دستورهای فوق gradle به صورت پیش‌فرض lint را روی بیلد release اجرا می‌کند. جهت اجرای آن روی یک بیلد متفاوت مانند debug می‌توانید نام بیلد را به صورت gradlew lintDebug اضافه کنید. پس از این که کار lint کردن پایان یافت، نتایج در قالب html و xml ایجاد می‌شوند.

توجه کنید که اگر هر گونه خطای lint وجود داشته باشد، اندروید استودیو نمی‌تواند نتایج را تولید کند و از این رو باید خطوط زیر را در فایل سطح gradle اپلیکیشن خود اضافه کنید:

1 2	lintOptions {     abortOnError false

سفارشی‌سازی قواعد Lint کردن

شاید نیازهای شما یا قراردادهای کدنویسی تیم از پیکربندی پیش‌فرض متفاوت باشد. بنابراین می‌توانید تنظیمات را در فایل gradle به صورت زیر تغییر دهید:

1 2 3 4

lintOptions {     abortOnError false     disable 'ContentDescription' }

در مثال فوق، بررسی lint را برای هشدار ContentDescription در کل پروژه غیرفعال کرده‌ایم. اگر نمی‌خواهید این وضعیت را روی کل پروژه اعمال کنید و می‌خواهید آن را صرفاً روی چند فایل به کار بگیرید، می‌توانید روی فایل‌های جاوا یا کاتلین از یک annotation به صورت SupressLint@ استفاده کنید و روی فایل‌های xml نیز می‌توانید از tools:ignore استفاده کنید. مثال زیر را بررسی کنید:

1 2 3

@SuppressLint("NewApi") override fun onCreate(savedInstanceState: Bundle?) {              super.onCreate(savedInstanceState)       setContentView(R.layout.main)

در مورد فایل‌های xml از کد زیر استفاده کنید:

1	<ImageView tools:ignore="HardcodedText"

اگر به خاطر داشته باشید کمی پیش‌تر اشاره کردیم که ابزار lint از فایل پیکربندی lint.xml استفاده می‌کند. شما می‌توانید فایل lint.xml خاص خود را بسازید و قواعد مرتبط با نیازهای خود را تعیین کنید. در مثال زیر ما فایل lint.xml خود را ایجاد کرده‌ایم و یک قاعده برای نادیده گرفتن هشدار missing contentDescription تعیین کرده‌ایم.

1 2 3 4 5

<?xml version="1.0" encoding="UTF-8"?> <lint>     <!-- Disable the given check in this project -->     <issue id="ContentDescription" severity="ignore" /> </lint>

پس از آن باید ارجاعی به فایل gradle به صورت زیر ایجاد کنیم:

1 2 3

lintOptions {     lintConfig file("lint.xml") }

توجه داشته باشید که در حالت فوق، قواعد lint که در فایل lint.xml تعیین‌شده‌اند، روی کل ماژول اعمال می‌شوند. اگر می‌خواهید آن را روی مسیر خاصی به کار بگیرید، می‌توانید به صورت زیر عمل کنید:

1 2 3

<issue id="ContentDescription" severity="ignore">      <ignore path="src/main/res/values/list_item.xml" /> </issue>

سخن پایانی

بدین ترتیب به پایان این مقاله می‌رسیم. تلاش کنید در پروژه بعدی خود از این ابزار جذاب استفاده کرده و کدهای با کیفیت بالاتری تولید کنید. امیدواریم از خواندن این مقاله لذت برده باشید. هر گونه دیدگاه یا پیشنهاد خود را می‌توانید در بخش نظرات این نوشته با ما و دیگر خوانندگان فرادرس در میان بگذارید.

منبع: فرادرس

طراحی اسکریپت ژنتیک در پایتون — به زبان ساده

در این مقاله در خصوص برخی آرگومان‌های خط فرمان و ورودی کاربر صحبت می‌کنیم که طراحی اسکریپت ژنتیک را در پایتون میسر ساخته‌اند.

ساخت رابط‌های کاربری

در این بخش مراحل ابتدایی برای ساخت یک رابط کاربری با استفاده از ورودی تعاملی کاربر و آرگومان‌های خط فرمان را مورد بررسی قرار می‌دهیم. کدی که در این مقاله ارائه شده است، در طی بخش‌های بعدی این سری مقالات بهبود خواهد یافت.

در هنگام طراحی یک اسکریپت، همواره باید کاربر را در نظر داشت. در اغلب موارد، زمانی که یک اسکریپت را برای حل یک مشکل می‌نویسیم، این احتمال وجود دارد که مشکل افراد دیگری را نیز حل کنیم. با در نظر داشتن این ذهنیت همواره باید میزان سهولت استفاده از برنامه خودتان از سوی افراد دیگر را نیز مورد توجه قرار دهید. ما در این مقاله با پیروی از یک سری قواعد کلی مثال‌هایی از اسکریپت‌های ژنتیک ارائه می‌کنیم، اما ایده‌های مطرح شده در آن می‌توانند به صورت گسترده‌ای برای طراحی هر برنامه دیگری نیز استفاده شوند.

سناریوی زیر را در نظر بگیرید. ما می‌خواهیم یک توالی DNA را مورد جستجو قرار دهیم و تعیین کنیم که آیا دو جایگاه آنزیم محدودکننده در بالاتر از یک آستانه تعیین‌شده وجود دارند یا نه. برای نمونه آیا توالی آنزیم‌های محدودکننده برای EcoRI و HindIII در یک توالی DNA بیش از 5، 10 یا 15 بار حضور دارند؟

بدین ترتیب برنامه پایتون ما باید شرایط زیر را داشته باشد:

1. انعطاف‌پذیر باشد: یعنی کاربر امکان جستجوی جایگاه‌های محدودکننده یا در واقع هر موتیف DNA در یک توالی DAN را دارد و تعداد تکرار آن را بالاتر از یک حد آستانه مشخص می‌سازد.
2. امکان کنترل داشته باشد: هر توالی DNA که کاربر انتخاب می‌کند را جستجو کند.
3. بخشنده باشد: برنامه می‌بایست اشتباه‌های معمول کاربران را در نظر بگیرد. برای مثال تایپ کردن نام بازهای DNA بدون استفاده از کاراکترهای ambiguity در یک توالی DNA یا استفاده از حروف کوچک برای بازهای DNA.
4. «بسیار» بخشنده باشد: برنامه باید همه تلاش خود را در راستای کمک به کاربر در جهت وارد کردن یک توالی معتبر DNA ارائه کند.

ورودی تعاملی کاربر

برای دریافت ورودی کاربر در یک برنامه باید از تابع ()input استفاده کنیم. تابع ()input یک آرگومان منفرد رشته‌ای می‌گیرد که از طریق اعلان نمایش یافته برای کاربر دریافت می‌شود و مقدار وارد شده را به صورت یک رشته بازمی‌گرداند. در این حالت بهتر است پیامی به کاربر نمایش داده شود که به صورت روشنی از وی بخواهد مقدار مورد نظر خود را وارد نماید. در مثال زیر از کاربر می‌خواهیم که یک توالی DNA را وارد کند:

1	DNA = input('Please enter your DNA sequence...')

با این وجود، بروز خطا ناگزیر است و یک ضربه نادرست روی کیبورد و یا غلط املایی هر زمان محتمل است. در چنین وضعیتی دو گزینه در اختیار داریم؛ می‌توانیم به سادگی از برنامه خارج شویم و همه کارها را از نو آغاز کنیم. برای خروج بی‌درنگ می‌توانیم کد زیر را اجرا کنیم:

1 2 3 4

import re DNA = input('Please enter your DNA sequence...').upper() while re.search('[^AGCT]', DNA):      exit("DNA sequence entered is not valid")

با این حال، این کار به صورت شهودی نادرست به نظر می‌رسد. به طور جایگزین می‌توانیم امکان وارد کردن مقدار دیگری را در اختیار کاربر قرار دهیم و یا این کار را تا هر تعداد دفعاتی که کاربر یک توالی DNA قابل قبول وارد نکرده است، تکرار کنیم. این کار به نام اعتبارسنجی ورودی کاربر شناخته می‌شود و اساساً به معنی بررسی معنی‌دار بودن ورودی ارائه شده از سوی کاربر است. در این مثال، ما می‌خواهیم که کاربر یک توالی را بدون بازهای مبهم وارد کند. ما می‌توانیم از یک گروه کاراکتر منفی شده و تابع ()re.search برای اطمینان یافتن از این که کاربر یک توالی معتبر DNA وارد کرده است استفاده کنیم. همچنین از متد ()upper. استفاده می‌کنیم تا مطمئن شویم که همه حروف توالی به صورت حروف بزرگ لاتین هستند. این مباحث همگی در حوزه «عبارت‌های منظم» (Regular Expressions) قرار می‌گیرند.

1 2 3 4

import re DNA = input('Please enter your DNA sequence...').upper() while re.search('[^AGCT]', DNA):     DNA = input('Please enter a valid DNA sequence...').upper()

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

گرچه ورودی کاربر می‌تواند موجب تعاملی و انعطاف‌پذیر شدن برنامه بشود؛ اما اجرای برنامه‌هایی که بخشی از گردش کار آن به صورت نظارت‌نشده است کار دشوارتری محسوب می‌شود. به طور ایده‌آل بهتر است موقعیت‌هایی را طراحی کنیم که برنامه ما همه آرگومان‌های تعیین‌شده را در آغاز از کاربر دریافت کند. برای نیل به این مقصود؛ آرگومان‌های خط فرمان یک راه‌حل ایده‌آل محسوب می‌شوند.

آرگومان‌های خط فرمان

آرگومان‌های خط فرمان رشته‌هایی هستند که پس از نام برنامه‌ای که می‌خواهیم اجرا شود، در خط فرمان تایپ می‌کنیم. برای استفاده از آرگومان‌های خط فرمان در اسکریپت‌های پایتون لازم است که ماژول sys ایمپورت شود. سپس می‌توانیم با استفاده از لیست خاص بازگشتی از سوی sys.argv به آرگومان‌های خط فرمان دسترسی داشته باشیم. عنصر نخست sys.argv، نام برنامه است که در این مورد به صورت Command_line_arguments.py و در اندیس 0 لیست قرار دارد. مثال زیر، اندیس‌ها آرگومان‌های متناظر خط فرمان آن را نمایش می‌دهد.

ما می‌توانیم با ایجاد امکان وارد کردن توالی به صورت حروف کوچک یا بزرگ در خط فرمان، کد خود را بیش از این پایدار بسازیم. همچنین می‌توان از متد رشته ()upper. به منظور مدیریت این وضعیت بهره جست. با این وجود، یک نکته مهم که باید توجه داشت این است که گزینه‌های خط فرمان همواره به صورت رشته بازگشت می‌یابند و از این رو باید count_no را به شکل زیر صریحاً به صورت عدد صحیح تبدیل کنیم:

1 2 3 4

import sys pattern = sys.argv[1].upper() pattern2 = sys.argv[2].upper() count_no = int(sys.argv[3])

در خط فرمان زیر، به نکاتی که در ادامه آمده است می‌توان اشاره کرد:

• GA نخستین آرگومان خط فرمان در اندیس 1 است که به الگو اشاره می‌کند.
• TC دومین آرگومان خط فرمان در اندیس 2 است که به الگوی 2 اشاره می‌کند.
• 2 سومین آرگومان خط فرمان است که در اندیس 3 قرار دارد و به count_no اشاره می‌کند.

اسکریپت پایتون ما یک تابع برای جستجوی دو آنزیم محدودکننده درون توالی DNA تعیین‌ شده تعریف می‌کند. سپس یک دیکشنری می‌سازیم و در آن به ذخیره‌سازی توالی آنزیم محدودکننده به صورت کلید می‌پردازیم و مقادیر آن نیز شمار آن‌ها خواهد بود. در ادامه روی این دیکشنری یک حلقه تعریف و بررسی می‌کنیم که آیا توالی بزرگ‌تر از تعداد تعیین‌شده از سوی کاربر است یا نه. کد کامل اسکریپت به صورت زیر است:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

import re import sys # DNA = input('Please enter your DNA sequence...').upper() # while re.search('[^AGCT]', DNA): #     DNA = input('Please enter a valid DNA sequence...').upper()   DNA = open('E.coli_genome.fasta').read()   pattern = sys.argv[1].upper() pattern2 = sys.argv[2].upper() count_no = int(sys.argv[3])   def restriction_enzyme_func(pattern, pattern2):     result = []     for m in re.finditer(pattern, DNA):         result.append(m.group())       for x in re.finditer(pattern2, DNA):         result.append(x.group())       return result   restriction_site_count = {} for pat in restriction_enzyme_func(pattern, pattern2):     current_count = restriction_site_count.get(pat, 0)     new_count = current_count + 1     restriction_site_count[pat] = new_count     for pattern, count in restriction_site_count.items():     if count > count_no:         print('The restriction enzyme site ' + pattern + ' is present : ' + str(count) + ' times')

اکنون می‌توانیم اسکریپت را با استفاده از آرگومان‌های خط فرمان اجرا کنیم. در این مرحله برای تست کارکرد برنامه از یک توالی کوچک تعیین‌شده از سوی کاربر استفاده کرده و تلاش می‌کنیم تعیین کنیم آیا tri-nucleotide-های TGC و ATG بیش از 3 بار وجود دارند یا نه.

در این مثال، می‌توانیم به وضوح مشاهده کنیم که کاربر یک نوکلئوتید DNA نامعتبر به صورت F (با رنگ زرد مشخص شده) وارد کرده است. برنامه ما در ادامه از کاربر می‌خواهد که یک توالی معتبر DNA وارد کند و زمانی که این کار صورت گرفت، نتیجه را بازگشت می‌دهد.

با این حال در اغلب موارد می‌خواهیم کل ژنوم را مورد جستجو قرار دهیم و از این رو تقاضا برای وارد کردن مقدار از سوی کاربر به‌سادگی میسر نیست. برای نمایش بهتر این که این برنامه تا چه حد می‌تواند مفید باشد ما کل ژنوم E.coli را از NCBI با شماره دسترسی Genbank CU928161.2 دانلود کردیم. این ژنوم نسبتاً بزرگ است و دقیقاً شامل 5،032،268 جفت باز است. با این وجود، اسکریپت ما به طرز کارآمدی آن را مدیریت می‌کند و نتیجه را تقریباً به صورت آنی بازگشت می‌دهد. در مثال زیر جستجو کرده‌ایم که جایگاه‌های آنزیم‌های محدودکننده EcoR1 GTTACC, و HindIII AAGCCT در ژنوم بالاتر از 50 بار حضور دارند یا نه. اگر چنین باشد برنامه اعلام می‌کند که چندین بار این جایگاه‌ها وجود داشته‌اند.

علاوه بر این می‌توانیم خروجی بسیار واضح‌تری از ترمینال بگیریم و بدین ترتیب همه افرادی که نتایج را روی ترمینال می‌خوانند، می‌توانند داده‌ها را تفسیر کنند.

نتیجه‌گیری

آرگومان‌های خط فرمان روشی مناسب برای دریافت ورودی در برنامه‌های پایتون محسوب می‌شود. در این روش همه داده‌های متناظر که برنامه نیاز دارد در آغاز ارائه می‌شوند. در این راهنما مقدمه کوتاهی در مورد روش طراحی اسکریپت‌های پایتون با ذهنیت کاربر محور ارائه کردیم. اگر می‌خواهید کاربر بتواند با برنامه شما تعامل داشته باشد، باید انتظار بروز خطا را نیز داشته باشید و بر همین اساس باید رویه‌های اصلاح خطا را در اسکریپت خود در نظر بگیرید.

منبع: فرادرس

ساخت ربات تلگرام برای دریافت اعلان های سفارشی — به زبان ساده

در این مقاله روش استفاده از ربات تلگرام برای دریافت اعلان های سفارشی در موضوعات خاص را بررسی می‌کنیم. فرض کنید یک اپلیکیشن را روی یک سرور توزیع کرده‌اید. همواره برخی کارها وجود دارند که لازم است در پس‌زمینه اجرا شوند. اما برای این که متوجه شویم این کارها پایان یافته‌اند یا نه، باید به صورت دستی آن‌ها را بررسی کنیم.

این همان نقطه‌ای است که ربات‌های تلگرام به کار می‌آیند. البته روش‌های مختلفی برای ارسال چنین اعلان‌هایی از طریق ابزارهای شخص ثالث وجود دارند. برای مثال می‌توان یک ایمیل، پیامک و یا حتی پیام slack ارسال کرد.

اما استفاده از پیام‌رسان تلگرام به این منظور بسیار کارآمد است، زیرا پلتفرم ربات آن امکانات بسیار زیادی دارد و خود این سرویس نیز به عنوان یک سرویس پایدار و رایگان برای این منظور کاملاً مناسب است.

ایجاد یک ربات تلگرام

برای ایجاد یک ربات تلگرام ابتدا باید به ربات botfather (+) مراجعه کنید و یک پیام به صورت newbot/ به آن ارسال کنید. ارسال این پیام به‌سادگی به صورت زیر ممکن است:

1 2 3 4

curl -X POST \        -H 'Content-Type: application/json' \        -d '{"chat_id": "123456789", "text": "This is a test from curl"}' \        https://api.telegram.org/bot$TELEGRAM_TOKEN/sendMessage

مطمئن باشید که توکن API خود را به جای TELEGRAM_TOKEN$ جایگزین کرده‌اید.

برای به دست آوردن chat_id می‌توانید ربات خود را به یک گروه یا گفتگویی که می‌خواهید اعلان‌ها به آن ارسال شوند اضافه کنید. سپس یک پیام ارسال کرده و آن را اجرا کنید:

1 2	curl -X GET \        https://api.telegram.org/bot$TELEGRAM_TOKEN/getUpdates

در این مرحله یک پاسخ JSON دریافت می‌کنید و درون این پیام می‌توانید chat_id خود را به دست آورید.

استفاده از کلاینت Bash تلگرام

مرحله بعدی این است که این کلاینت Bash تلگرام (+) را فورک کنید تا از طریق دستور زیر یک پیام را ارسال کنید:

1	telegram -t $TELEGRAM_TOKEN -c $TELEGRAM_CHAT "Hello World!"

همچنین می‌توانید متغیرهای محیطی را طوری تنظیم کنید که دیگر نیازی به وارد کردن مکرر TELEGRAM_TOKEN و TELEGRAM_CHAT نباشد. بدین ترتیب دستور موردنیاز برای ارسال پیام Hello World! به صورت زیر درمی‌آید:

1	telegram "Hello World!"

همان طور که می‌بینید، قابلیت بسیار جالبی است. بدین ترتیب به محض این که کار مورد نظر شما به پایان برسد، می‌توانید از دستورهای فوق برای ارسال یک پیام و همچنین خلاصه‌ای از نتیجه اجرای آن کار برای خودتان استفاده کنید.

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش ساخت ربات تلگرام (Telegram)

منبع:  فرادرس

جستجوی الگو (Pattern Searching) — به زبان ساده

در این مطلب، جستجوی الگو (Pattern Searching) مورد بررسی قرار می‌گیرد و یک الگوریتم ساده برای این کار ارائه می‌شود. متن  [txt[0..n-1 و الگوی [pat[0..m-1 موجود است؛ هدف نوشتن تابع جستجویی ([]char pat[], char txt) است که همه وقوع‌های []pat در []txt را چاپ کند. می‌توان فرض کرد که n > m است. مثال‌های زیر در این راستا قابل توجه هستند.

Input:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
Output: Pattern found at index 10

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

جستجوی الگو، یک مسأله مهم در علوم کامپیوتر است. هنگامی که یک رشته در فایل «نوت‌پد» (Notepad)، «ورد» (Word)، مرورگر و یا «پایگاه‌داده» (Database) جستجو می‌شود از جستجوی الگو برای نمایش نتایج جستجو استفاده می‌شود.

الگوریتم ساده برای جستجوی الگو

الگو در متن به این صورت بررسی می‌شود که از آغاز متن به صورت اسلایدی (کشویی) با متن مطابقت داده می‌شود. اگر الگویی مطابق با الگوی جستجو شده در متن پیدا شد، فعالیت مجددا ادامه پیدا می‌کند تا سایر الگوها نیز یافت شوند.

الگوریتم ساده جستجوی الگو در ++C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// C++ program for Naive Pattern   // Searching algorithm #include<bits/stdc++.h> using namespace std;    void search(char* pat, char* txt) {     int M = strlen(pat);     int N = strlen(txt);        /* A loop to slide pat[] one by one */     for (int i = 0; i <= N - M; i++) {         int j;            /* For current index i, check for pattern match */         for (j = 0; j < M; j++)             if (txt[i + j] != pat[j])                 break;            if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]             cout << "Pattern found at index "                  << i << endl;     } }    // Driver Code int main() {     char txt[] = "AABAACAADAABAAABAA";     char pat[] = "AABA";     search(pat, txt);     return 0; }    // This code is contributed   // by Akanksha Rai

الگوریتم ساده جستجوی الگو در C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

// C program for Naive Pattern Searching algorithm #include <stdio.h> #include <string.h>    void search(char* pat, char* txt) {     int M = strlen(pat);     int N = strlen(txt);        /* A loop to slide pat[] one by one */     for (int i = 0; i <= N - M; i++) {         int j;            /* For current index i, check for pattern match */         for (j = 0; j < M; j++)             if (txt[i + j] != pat[j])                 break;            if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]             printf("Pattern found at index %d \n", i);     } }    /* Driver program to test above function */ int main() {     char txt[] = "AABAACAADAABAAABAA";     char pat[] = "AABA";     search(pat, txt);     return 0; }

الگوریتم ساده جستجوی الگو در جاوا

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

// Java program for Naive Pattern Searching public class NaiveSearch {        public static void search(String txt, String pat)     {         int M = pat.length();         int N = txt.length();            /* A loop to slide pat one by one */         for (int i = 0; i <= N - M; i++) {                int j;                /* For current index i, check for pattern                 match */             for (j = 0; j < M; j++)                 if (txt.charAt(i + j) != pat.charAt(j))                     break;                if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]                 System.out.println("Pattern found at index " + i);         }     }        public static void main(String[] args)     {         String txt = "AABAACAADAABAAABAA";         String pat = "AABA";         search(txt, pat);     } } // This code is contributed by Harikishore

الگوریتم ساده جستجوی الگو در #C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

// C# program for Naive Pattern Searching using System;    class GFG {            public static void search(String txt, String pat)     {         int M = pat.Length;         int N = txt.Length;            /* A loop to slide pat one by one */         for (int i = 0; i <= N - M; i++)         {             int j;                /* For current index i, check for pattern               match */             for (j = 0; j < M; j++)                 if (txt[i + j] != pat[j])                     break;                // if pat[0...M-1] = txt[i, i+1, ...i+M-1]             if (j == M)                   Console.WriteLine("Pattern found at index " + i);         }     }        // Driver code     public static void Main()     {         String txt = "AABAACAADAABAAABAA";         String pat = "AABA";         search(txt, pat);     } } // This code is Contributed by Sam007

الگوریتم ساده جستجوی الگو در PHP

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

<?php // PHP program for Naive Pattern // Searching algorithm    function search($pat, $txt) {     $M = strlen($pat);     $N = strlen($txt);        // A loop to slide pat[]       // one by one       for ($i = 0; $i <= $N - $M; $i++)     {            // For current index i,           // check for pattern match           for ($j = 0; $j < $M; $j++)             if ($txt[$i + $j] != $pat[$j])                 break;            // if pat[0...M-1] =           // txt[i, i+1, ...i+M-1]         if ($j == $M)               echo "Pattern found at index ", $i."\n";     } }        // Driver Code     $txt = "AABAACAADAABAAABAA";     $pat = "AABA";     search($pat, $txt);        // This code is contributed by Sam007 ?>

الگوریتم ساده جستجوی الگو در پایتون ۳

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

# Python3 program for Naive Pattern # Searching algorithm def search(pat, txt):     M = len(pat)     N = len(txt)        # A loop to slide pat[] one by one */     for i in range(N - M + 1):         j = 0                    # For current index i, check           # for pattern match */         for j in range(0, M):             if (txt[i + j] != pat[j]):                 break            if (j == M - 1):               print("Pattern found at index ", i)    # Driver Code if __name__ == '__main__':     txt = "AABAACAADAABAAABAA"     pat = "AABA"     search(pat, txt)    # This code is contributed   # by PrinciRaj1992

خروجی و پیچیدگی زمانی

خروجی قطعه کدهای بالا، به صورت زیر است.

Pattern found at index 0 
Pattern found at index 9 
Pattern found at index 13

بهترین حالت

بهترین حالت هنگامی به وقوع می‌پیوندد که اولین کاراکتر از الگو هرگز در متن ظاهر نشود.

txt[] = “AABCCAADDEE”;
pat[] = “FAA”;

تعداد مقایسه ها در بهترین حالت (O(n است.

بدترین حالت

بدترین حالت الگوریتم جستجوی الگوی ساده در شرایط زیر به وقوع می‌پیوندد.

۱. هنگامی که همه کاراکترهای متن و الگو مشابه باشد:

txt[] = "AAAAAAAAAAAAAAAAAA"; 
pat[] = "AAAAA";

۲. همچنین، بدترین حالت هنگامی به وقوع می‌پیوندد که آخرین کاراکتر متفاوت باشد.

txt[] = "AAAAAAAAAAAAAAAAAB"; 
pat[] = "AAAAB";

تعداد مقایسه‌ها در بدترین حالت برابر با ((O(m*(n-m+1 است. با وجود اینکه برخی از رشته‌ها دارای کاراکترهایی هستند که در زبان انگلیسی ظاهر نمی‌شود، اما این رشته‌ها ممکن است در دیگر کاربردها به وقوع بپیوندند (برای مثال، در متن‌های دودویی). الگوریتم تطبیق KMP، بدترین حالت را به (O(n بهبود می‌بخشد.

منبع: فرادرس

جستجوی الگو (Pattern Searching) — به زبان ساده

در این مطلب، جستجوی الگو (Pattern Searching) مورد بررسی قرار می‌گیرد و یک الگوریتم ساده برای این کار ارائه می‌شود. متن  [txt[0..n-1 و الگوی [pat[0..m-1 موجود است؛ هدف نوشتن تابع جستجویی ([]char pat[], char txt) است که همه وقوع‌های []pat در []txt را چاپ کند. می‌توان فرض کرد که n > m است. مثال‌های زیر در این راستا قابل توجه هستند.

Input:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
Output: Pattern found at index 10

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

جستجوی الگو، یک مسأله مهم در علوم کامپیوتر است. هنگامی که یک رشته در فایل «نوت‌پد» (Notepad)، «ورد» (Word)، مرورگر و یا «پایگاه‌داده» (Database) جستجو می‌شود از جستجوی الگو برای نمایش نتایج جستجو استفاده می‌شود.

الگوریتم ساده برای جستجوی الگو

الگو در متن به این صورت بررسی می‌شود که از آغاز متن به صورت اسلایدی (کشویی) با متن مطابقت داده می‌شود. اگر الگویی مطابق با الگوی جستجو شده در متن پیدا شد، فعالیت مجددا ادامه پیدا می‌کند تا سایر الگوها نیز یافت شوند.

الگوریتم ساده جستجوی الگو در ++C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// C++ program for Naive Pattern   // Searching algorithm #include<bits/stdc++.h> using namespace std;    void search(char* pat, char* txt) {     int M = strlen(pat);     int N = strlen(txt);        /* A loop to slide pat[] one by one */     for (int i = 0; i <= N - M; i++) {         int j;            /* For current index i, check for pattern match */         for (j = 0; j < M; j++)             if (txt[i + j] != pat[j])                 break;            if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]             cout << "Pattern found at index "                  << i << endl;     } }    // Driver Code int main() {     char txt[] = "AABAACAADAABAAABAA";     char pat[] = "AABA";     search(pat, txt);     return 0; }    // This code is contributed   // by Akanksha Rai

الگوریتم ساده جستجوی الگو در C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

// C program for Naive Pattern Searching algorithm #include <stdio.h> #include <string.h>    void search(char* pat, char* txt) {     int M = strlen(pat);     int N = strlen(txt);        /* A loop to slide pat[] one by one */     for (int i = 0; i <= N - M; i++) {         int j;            /* For current index i, check for pattern match */         for (j = 0; j < M; j++)             if (txt[i + j] != pat[j])                 break;            if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]             printf("Pattern found at index %d \n", i);     } }    /* Driver program to test above function */ int main() {     char txt[] = "AABAACAADAABAAABAA";     char pat[] = "AABA";     search(pat, txt);     return 0; }

الگوریتم ساده جستجوی الگو در جاوا

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

// Java program for Naive Pattern Searching public class NaiveSearch {        public static void search(String txt, String pat)     {         int M = pat.length();         int N = txt.length();            /* A loop to slide pat one by one */         for (int i = 0; i <= N - M; i++) {                int j;                /* For current index i, check for pattern                 match */             for (j = 0; j < M; j++)                 if (txt.charAt(i + j) != pat.charAt(j))                     break;                if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]                 System.out.println("Pattern found at index " + i);         }     }        public static void main(String[] args)     {         String txt = "AABAACAADAABAAABAA";         String pat = "AABA";         search(txt, pat);     } } // This code is contributed by Harikishore

الگوریتم ساده جستجوی الگو در #C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

// C# program for Naive Pattern Searching using System;    class GFG {            public static void search(String txt, String pat)     {         int M = pat.Length;         int N = txt.Length;            /* A loop to slide pat one by one */         for (int i = 0; i <= N - M; i++)         {             int j;                /* For current index i, check for pattern               match */             for (j = 0; j < M; j++)                 if (txt[i + j] != pat[j])                     break;                // if pat[0...M-1] = txt[i, i+1, ...i+M-1]             if (j == M)                   Console.WriteLine("Pattern found at index " + i);         }     }        // Driver code     public static void Main()     {         String txt = "AABAACAADAABAAABAA";         String pat = "AABA";         search(txt, pat);     } } // This code is Contributed by Sam007

الگوریتم ساده جستجوی الگو در PHP

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

<?php // PHP program for Naive Pattern // Searching algorithm    function search($pat, $txt) {     $M = strlen($pat);     $N = strlen($txt);        // A loop to slide pat[]       // one by one       for ($i = 0; $i <= $N - $M; $i++)     {            // For current index i,           // check for pattern match           for ($j = 0; $j < $M; $j++)             if ($txt[$i + $j] != $pat[$j])                 break;            // if pat[0...M-1] =           // txt[i, i+1, ...i+M-1]         if ($j == $M)               echo "Pattern found at index ", $i."\n";     } }        // Driver Code     $txt = "AABAACAADAABAAABAA";     $pat = "AABA";     search($pat, $txt);        // This code is contributed by Sam007 ?>

الگوریتم ساده جستجوی الگو در پایتون ۳

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

# Python3 program for Naive Pattern # Searching algorithm def search(pat, txt):     M = len(pat)     N = len(txt)        # A loop to slide pat[] one by one */     for i in range(N - M + 1):         j = 0                    # For current index i, check           # for pattern match */         for j in range(0, M):             if (txt[i + j] != pat[j]):                 break            if (j == M - 1):               print("Pattern found at index ", i)    # Driver Code if __name__ == '__main__':     txt = "AABAACAADAABAAABAA"     pat = "AABA"     search(pat, txt)    # This code is contributed   # by PrinciRaj1992

خروجی و پیچیدگی زمانی

خروجی قطعه کدهای بالا، به صورت زیر است.

Pattern found at index 0 
Pattern found at index 9 
Pattern found at index 13

بهترین حالت

بهترین حالت هنگامی به وقوع می‌پیوندد که اولین کاراکتر از الگو هرگز در متن ظاهر نشود.

txt[] = “AABCCAADDEE”;
pat[] = “FAA”;

تعداد مقایسه ها در بهترین حالت (O(n است.

بدترین حالت

بدترین حالت الگوریتم جستجوی الگوی ساده در شرایط زیر به وقوع می‌پیوندد.

۱. هنگامی که همه کاراکترهای متن و الگو مشابه باشد:

txt[] = "AAAAAAAAAAAAAAAAAA"; 
pat[] = "AAAAA";

۲. همچنین، بدترین حالت هنگامی به وقوع می‌پیوندد که آخرین کاراکتر متفاوت باشد.

txt[] = "AAAAAAAAAAAAAAAAAB"; 
pat[] = "AAAAB";

تعداد مقایسه‌ها در بدترین حالت برابر با ((O(m*(n-m+1 است. با وجود اینکه برخی از رشته‌ها دارای کاراکترهایی هستند که در زبان انگلیسی ظاهر نمی‌شود، اما این رشته‌ها ممکن است در دیگر کاربردها به وقوع بپیوندند (برای مثال، در متن‌های دودویی). الگوریتم تطبیق KMP، بدترین حالت را به (O(n بهبود می‌بخشد.

منبع: فرادرس