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 va Nondeterministic Finite Automaton
Regular Expression algoritmiga o’tishdan avval NFA – Nondeterministic Finite Automaton abstrakt hisoblash mashinasi haqida tanishib chiqish kerak bo’ladi.
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. Rabin-Karp algoritmi
Matn ichida qidiruv uchun yana bir diqqatga molik algoritmlardan biri – Rabin-Karp algoritmi hashing usuliga asoslanadi. Uning ishlash tartibini batafsil tushuntirishga harakat qilaman.
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. Knuth-Morris-Pratt algoritmi
Matn ichida qidiruv uchun brute-force yondashuvining kamchiligi – pattern’dagi belgilardan biri qidiruvda mos kelmay qolganda, qidiruvni boshqatdan boshlashi kerak. Shuning uchun worst case O(N*M) bo’lib ketadi.
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.
Trie ma’lumot tuzilmasida string amallari
Ushbu maqolada biz ba’zi string amallarini R-way trie ma’lumot tuzilmasida ko’rib o’tamiz.
Ternary search tries
Ternary search tries (TST, uchlamchi qidiruv trie) R-way tries’dagi kamchilikka yechim o’laroq tavsiya etiladi. TSTda belgilar indeks ko’rinishida emas, node ichida saqlanadi (R-way tries’da belgilar indeks nomer sifatida saqlanardi). Shuningdek har bir node uch child’ga ega: kichikroq (chap), teng (o’rtada), kattaroq (o’ngda).