Minimum edit distance

Minimum tahrirlash masofasi deb be’mani tarjima qilinadigan minimum edit distance (yoki ixtirochisi sharafiga Levenshtein distance) algoritmi ikki so’z o’rtasidagi farqlar sonini aniqlashga yordam beradi.

Ryukzak masalasi (Knapsack problem)

Bizda har biri vaznga va qiymatga ega bo’lgan turli buyumlar bor. Ryukzakga (yoki biror idishga) solish uchun ularni shunday tanlash kerakki, buyumlar ryukzakning maksimum og’irlik limitidan kichkina yoki teng bo’lsin va solingan buyumlarning umumiy qiymati iloji boricha eng kattasi bo’lsin. Ushbu masala ryukzak masalasi, inglizchada knapsack problem deb ataladi.

Dynamic programming

Dynamic programming (DP, dinamik dasturlash) deb muammoni kichik masalalarga ajratib, ularni faqat bir marta yechish va natijani keyingi bir xil tipdagi masalada ishlatish uchun saqlab turish texnikasiga aytiladi.

NFA simulyatsiyasi va API

NFA simulyatsiyasini ko’rib chiqishdan avval NFAning o’zini kodda qanday ifodalashni ko’rib chiqamiz. Avvalgi maqolada aytib o’tilganidek, NFAda 0 dan M gacha state’lar + accept state mavjud. M – bu yerda qavs ichiga olingan regular expression’dagi belgilar soni. Masalan ((A*B|AC)D) regexp uchun NFA state’lari 11 ta (10ta regexp belgi-state + 1 accept state).

Regular expressions

Regular expression (yana regex, regexp) – qidirish patternini belgilab beruvchi belgilar ketma-ketligi. Odatda regex’lar matn ichida qidiruv algoritmlarida so’zlarni topish (find), topish va almashtirish (find & replace), hamda kiritilgan ma’lumotni tekshirish uchun ishlatiladi.

Matn ichida qidiruv. Boyer-Moore algoritmi

Avvalgi mavzuda o’tganimiz – Knuth-Morris-Pratt algoritmi yordamida biz matn ichida qidiruvni O(N + M) vaqt ichida bajara olamiz. Navbatdagi algoritm – Boyer-Moore algoritmi bizga O(N) ni kafolatlay olmasada, amaliyotda KMPdan samaraliroq ishlaydi. O’rganishga ham osonroq ๐Ÿ˜‰

Matn ichida qidiruv. Brute-force yondashuvi

Matn ichida so’z/ibora qidiruv (substring search) algoritmlari bilan tanishib chiqishni boshlaymiz. Qo’yiladigan masala juda oddiy. N uzunlikdagi matn ichidan M uzunlikdagi iborani (pattern) topish kerak bo’lsin. Bunda matn juda katta hajmda, pattern esa juda kichik – bir-ikki so’zdan iborat.