Stalkerio algoritmas

Stalkerio algoritmas – paieškos eilutėje algoritmas, kai tekstiniame dokumente ieškomi tam tikri fragmentai, apsupti nežinomo ilgio , 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 . Nauji markeriai kuriami paimant ilgio ieškomo teksto fragmentui gretimą seką ir dalį atsitiktinai parinktų simbolių joje pakeičiant sutartiniais : „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.

Šaltiniai

1. Muslea,I., Minton,S. and Knoblock,C.A. (2001) Hierarchical wrapper induction for semistructured information sources. J. Aut. Agents Multi-Agent Syst., 4, 93–114
2. Meškauskas A, Lehmann-Horn F, Jurkat-Rott K. (2004). Sight: automating genomic data-mining without programming skills, Bioinformatics. 2004 Jul 22;20(11):1718-20. Epub 2004 Feb 26. [1][2]