Rabin-karp algoritmi

Рабин-Карп алгоритми

Рабин-Карп алгоритми сатрларни қидириш алгоритми бўлиб, у хешлаш ёрдамида матнда нақш, яъни пастки қаторни қидиради. У 1987 йилда Майкл Рабин ва Ричард Карп томонидан ишлаб чиқилган.

Алгоритм битта нақшни мослаштириш учун камдан-кам қўлланади, лекин муҳим назарий аҳамиятга эга ва бир хил узунликдаги бир нечта нақшларнинг мослигини топишда жуда самарали. н узунликдаги матн ва м узунликдаги нақш учун унинг ўртача ва энг яхши бажарилиш вақти тўғри танланган хеш функсияси билан О(н) дир (пастга қаранг), лекин энг ёмон ҳолатда у О(нм) самарадорлигига эга, бу жуда кенг қўлланилмаслигининг сабабларидан бири. Қидирувда нотўғри позитивларга чидаш мумкин бўлган иловалар учун, яъни нақшнинг топилган баъзи ҳолатлари аслида нақшга мос келмаслиги мумкин бўлган иловалар учун Рабин-Карп алгоритми кафолатланган О(н) вақтида ва тегишли тасодифий танлов билан ишлайди. хаш функцияси (пастга қаранг) хатолик эҳтимоли жуда кичик бўлиши мумкин. Алгоритм шунингдек, к нинг катталигидан қатъий назар, О(н) вақт ичида берилган бир хил узунликдаги к сатрлардан исталган бирини ўртача (хеш функсиясини тўғри танлаш билан) топишнинг ўзига хос хусусиятига эга.

Рабин-Карп алгоритмининг энг оддий амалий қўлланмаларидан бири плагиатни аниқлашдир. Айтайлик, бир талаба Моби Дик ҳақида мақола ёзяпти. Cрафтй Профессор Мобй Диcк-дан турли манба материалларини топади ва бу материаллардаги жумлалар рўйхатини автоматик равишда олади. Кейин Рабин-Карп алгоритми текширилаётган мақоладаги манба материалларидан маълум жумлаларнинг пайдо бўлишига мисолларни тезда топиши мумкин. Алгоритмни кичик фарқларга нисбатан камроқ сезгир қилиш учун уларни олиб ташлаш орқали катта ёки тиниш белгилари каби тафсилотларни эътиборсиз қолдиришингиз мумкин. Биз излаётган қаторлар сони, к, жуда катта бўлгани учун, анъанавий бир қаторли қидирув алгоритмлари самарасиз бўлиб қолади.

Алгоритм

Алгоритм қуйидагича кўрсатилади:

фунcтион РабинКарп(стринг с[1..н], стринг паттерн[1..м])
    ҳпаттерн := ҳаш(паттерн[1..м]);
    фор и фром 1 то н-м+1
        ҳс := ҳаш(с[и..и+м-1])
        иф ҳс = ҳпаттерн
            иф с[и..и+м-1] = паттерн[1..м]
                ретурн и
    ретурн нот фоунд

2, 4 ва 6-қаторларнинг ҳар бири О(м) вақтни талаб қилади. Бироқ, 2-қатор фақат бир марта бажарилади ва 6-қатор фақат хеш қийматлари мос келса, бажарилади, бу бир неча марта содир бўлиши даргумон. 5-қатор О (н) марта бажарилади, лекин ҳар бир таққослаш фақат доимий вақтни талаб қилади, шунинг учун унинг таъсири О (н) дир. Муаммо 4-қаторда.

с[и+1..и+м] пастки сатри учун хеш қийматини содда тарзда ҳисоблаш О(м) вақтни талаб қилади, чунки ҳар бир белги текширилади. Хешни ҳисоблаш ҳар бир циклда амалга оширилганлиги сабабли, содда хешни ҳисоблаш алгоритми О(мн) вақтни талаб қилади, бу оддий сатрларни мослаштириш алгоритми билан бир хил мураккаблик. Тезлик учун хешни доимий вақтда ҳисоблаш керак. Айёрлик шундаки, ҳс ўзгарувчиси аллақачон с[и..и+м-1] нинг олдинги хеш қийматини ўз ичига олади. Агар бу қиймат доимий вақтда кейинги хеш қийматини ҳисоблаш учун ишлатилиши мумкин бўлса, у ҳолда кетма-кет хеш қийматларини ҳисоблаш тез бўлади.

Ҳийла-найрангни ҳаддан ташқари хеш ёрдамида ишлатиш мумкин. Роллинг хеш – бу операцияни ёқиш учун махсус ишлаб чиқилган хеш функцияси. Арзимас (лекин унчалик яхши эмас) хеш функсияси шунчаки пастки қатордаги ҳар бир белгининг қийматларини қўшади. Ушбу ҳадделенмиş хеш формуласи доимий вақт ичида олдинги қийматдан кейинги ҳаш қийматини ҳисоблаши мумкин:

с[и+1..и+м] = с[и..и+м-1] – с[и] + с[и+м]

Бу оддий функция ишлайди, лекин 5-бўлим кейинги бўлимда муҳокама қилинган бошқа мураккаб хеш функсияларга қараганда тез-тез бажарилишига олиб келади.

Яхши ишлаш, дуч келган маълумотлар учун яхши хешлаш функциясини талаб қилади. Агар хешлаш ёмон бўлса (масалан, ҳар бир кириш учун бир хил хеш қийматини ишлаб чиқариш), у ҳолда 6-қатор О(н) марта (яъни, циклнинг ҳар бир итерациясида) бажарилади. Узунлиги м бўлган сатрларни белгима-белги билан таққослаш О(м) вақтни олади, шунинг учун бутун алгоритм энг ёмон ҳолатда О( мн) вақт олади.