Stalkerio algoritmas

Stalkerio algoritmas – paieškos eilutėje algoritmas, kai tekstiniame dokumente ieškomi tam tikri fragmentai, apsupti nežinomo ilgio markeriais, kurių dalis yra konservatyvi ir gali padėti rasti reikiamą informaciją.

Algoritmo parašymas

Jei ieškoma skaičių tekste

    rqefscasdfawexhrtcvhhcx1uuuuucewrexcx2uuurrrxttttttabcx

kairysis markeris gali būti ex*cx o dešinysis u+, žvaigždute žymint bet kokią simbolių seką, o pliusu – kad raidė 'u' gali pasirodyti vieną ar daugiau kartų. Radus tinkamo ilgio markerius, jais galima išgauti reikiamą informaciją ir iš naujų, nesužymėtų dokumentų. Tarkim, naujame tekste

    cexarccxabcuxyzfff

algoritmas atkreips dėmesį į abc, kuris, nors ir nebūdamas joks skaičius, turi panašią aplinką.

Stalkerio algoritmas yra genetinis algoritmas, kuriama vyksta dirbtinė kairiojo ir dešiniojo markerių evoliucija. Nauji markeriai kuriami paimant atsitiktinio ilgio ieškomo teksto fragmentui gretimą seką ir dalį atsitiktinai parinktų simbolių joje pakeičiant sutartiniais kodais: „bet kokia simbolių seka“ (žvaigždutė), „bet koks simbolis“ (procento ženklas), gali būti taip pat „bet koks skaitmuo“ ar „šis simbolis vieną ar daugiau kartų“ bei panašiai (skirtingose programose sutartiniai kodai gali skirtis). Kai kada ieškomas teksto fragmentas laikomas trečiuoju markeriu ir taip pat aprašomas sutartiniais kodais (tarkim, *@* – elektroninio pašto adresas).

Atranką lemia tai, kiek žymėtų fragmentų markerių pora aptiko teisingai ir kiek kartų ji klaidingai nurodė nepažymėtas sekas.

Dirbtinei evoliucijai pasibaigus, bus rasta geriausiai tinkanti markerių pora, tačiau ji nebūtinai aptiks visus reikiamas rasti fragmentus. Jei kai kurių fragmentų rasta markerių pora „nemato“, dirbtinės evoliucijos procesas kartojamas kiek reikia kartų, kiekvienąsyk iš žymėtų fragmentų aibės pašalinant turimais markeriais jau randamas sekas. Taigi algoritmas pateikia markerių porų seką. Galutinė programa turi ieškoti fragmentų pagal visas markerių poras (pateikimo eilės tvarka) ir pateikti jungtinį rezultatą.

Sudėtingesnė (pilna) Stalkerio algoritmo realizacija ieškomus fragmentus hierarchiškai skaido į smulkesnius vienetus. Tarkim, iš pradžių algoritmas pritaikomas informacijai apie asmenį rasti, paskui tas pats algoritmas pritaikomas pavardei ir adresui rastame vienete aptikti.