Duomenų bazėse saugomų tekstų identifikacija

VILNIAUS UNIVERSITETASMATEMATIKOS IR INFORMATIKOS FAKULTETASINFORMATIKOS KATEDRA

Kursinis darbas

Duomenų bazėse saugomų tekstų identifikacija

Atliko: 3 kurso, 6 grupės studentas Aurimas Pokvytis (parašas) Darbo vadovas: Doc. Rimantas Vaicekauskas (parašas)

Vilnius2004

TurinysĮvadas 31. Trigramų technologija 41.1. Trigramai 41.2. Trigramų panaudojimas dokumentų paieškoje ir palyginime 41.3 Trigramų panaudojimas specializuotiems tekstams 72. Duomenų bazių aspektas 7 2.1 Indeksai 7 2.2 Trigramai ir tekstinės duomenų bazės 9 2.3 Trigramų metodo tekstinėms duomenų bazėms optimizavimas 103. Dokumentų grupavimo pagal tarpusavio panašumo koeficientą metodas 12 3.1 Metodo esmė 12 3.2 Teorinis metodo realizavimas 13Išvados 15Literatūros sąrašas 16

ĮvadasŠiais informacinių technologijų laikais tekstų identifikacija užima ganėtinai svarbią poziciją. Tekstų identifikacija labai praverčia, kai naudojame ją plagijavimo atvejams atskleisti. Kaip žinome, tokių atvejų ypatingai daug informacinių technologijų srityje. Susipažinsime su trigramais, trigraminėmis technologijomis, jų panaudojimu tekstinių dokumentų panašumo nustatymui. Pabandysime aptarti įvairius jų metodus, tikimybinį panašumo nustatymą. Taip pat pažiūrėsime, kaip jie naudojami specializuotiems tekstams, konkrečiai struktūriniams tekstams (Java programos). Dar pakalbėsime apie duomenų bazių valdymo sistemas kaip duomenų kaupimo ir paieškos priemonę. Nagrinėdami jų veikimo principą apžvelgsime duomenų bazių indeksus, jų privalumus, panaudojimą. Pagrindinis šio darbo tikslas – surasti efektyvius paieškos ir palyginimo metodus duomenų bazių valdymo sistemoms, kuriose laikomi tekstiniai dokumentai. Šiame darbe panagrinėsime daugiau teorinį aspektą.

1. Trigraminės technologijos.1.1. Trigramai.Trigramų apibrėžimas: trigramas – tai trijų iš eilės einančių, iš žodžio paimtų, simbolių aibė. Yra laikoma, kad kiekvienas žodis prefikse turi du tarpo simbolius. Pavyzdžiui, žodis ,,prologas” turės šiuos trigramus(,, p”, ,, pr”,”pro”, ,,olo”, ,,log”, ,,oga”, ,,gas”).Mūsų problemos atveju geriau tinka trigramo, kaip trijų iš eilės einančių žodžių junginio, samprata. Ši eilutėplagijavimas yra labai opi problema gali būti išskaidytas į iš dalies sutampančių trigramų aibę:plagijavimas yra labai yra labai opi labai opi problema

Trigramai yra pakankamai plačiai naudojami ne tik tekstų palyginime ar paieškoje, bet ir rašybos klaidų tikrinimui ar panašių žodžių rašybos prasme pasiūlymui. Taipogi, su jais ganėtinai patogu dirbti nežinant kalbos, kuria parašytas tekstas, t.y. nebūtina žinoti žodžių reikšmių.

1.2. Trigramų panaudojimas tekstinių dokumentų paieškoje ir palyginime. Kai kurios paieškos sistemos naudoja trigramus vietoj žodžių. Pavyzdžiui, į paieškos lauką įrašius ,,search for”, sistema suskaido duotą frazę į atitinkančius trigramus: sea, ear, arc, rch, h f, fo, for. Tada turimuose dokumentuose ieškoma pastarųjų trigramų, ir pagal juose esančių trigramų skaičių sprendžiama, ar dokumentas yra paieškos rezultatas. Reiškinys, kurį mes išnaudojame, yra faktas, kad dažniausiai pasitaikantys trigramai sudaro labai mažą dalį tarpusavyje nepriklausomų tekstų trigramų. Tai yra žodžių išskirstymo pasekmė. Jei du nepriklausomi rašytojai parašo veikalus ta pačia tema, tokiais atvejais sutampančių trigramų bus keletas, palyginus su jų visuma. Toliau panagrinėkime keletą dažniausiai naudojamų metodų.Pagrindinė trigramų idėja paprasta: kuo žodžiai ar frazės tarpusavyje panašesnės, tuo daugiau bendrų trigramų jie turės. Iš čia, trigramų, kuriuos turi abu žodžiai(frazės), skaičius gali būti naudojamas kaip panašumo matas. Tačiau šis matas apribojamas trumpiausio žodžio trigramų skaičiumi. Todėl panašumo matui turi būti nustatyta skalė, naudojant Daiso koeficientą, kurį pasiūlė Dice, Sorenson ir Czekanowski:

kur S bendrų trigramų žodžiuose i ir j skaičius, o M ir N atitinkamai žodžių i ir j ilgiai. Du žodžiai laikomi panašiais, jei Daiso koeficientas viršija tam tikrą ribą: panašumo ribą. Varijuojant šiuo skaičiumi galima nustatyti norimą tikslumą. Pavyzdžiui, lyginant žodžius ,,tėvas” ir ,,tėvai” gauname:

,,tėv”, ,,ėva”, ,,vas” ,,tėv”, ,,ėva”, ,,vai”.Bendrų trigramų skaičius 2, ilgiai atitinkamai 5 ir 5. Apskaičiuojame Daiso koeficientą: 4 2 10 , suprastinus gauname 5.Palyginimui atlikti reikia tekstinį dokumentą pakeisti trigramų aibe, ir tada palyginti ją su kitų tekstinių dokumentų trigramų aibėmis. Jeigu sutapimų skaičius tarp dviejų dokumentų viršija nustatytą slenkstį, tokiu atveju laikoma, kad jie yra panašūs. Trigramų metodo pranašumas tame, kad dokumentai neprivalo turėti identiško žodžių išsidėstymo: panašumo pėdsakus galima nustatyti net jei kai kurie žodžiai yra ištrinti, įterpti arba pakeisti. Tarpusavyje nepriklausomai parašyti tekstai, netgi jei jų autorius tas pats ir tema tokia pat, paprastai neturi daug bendrų trigramų.Jei NA yra trigramų aibė iš dokumento A ir NB trigramų aibė iš dokumento B, tada , kur R-panašumas(resemblance)Panašumas taipogi gali būti matuojamas, kaip sutampančių trigramų ir visų skirtingų trigramų dokumente santykis.S = sutampančių trigramų skaičius * 100 % skirtingų trigramų skaičiusTuo atveju, kai reikia ieškoti ar palyginti ne du, bet žymiai daugiau tekstinių dokumentų, naudotinas trigramų svarbos skaičiavimas pagal formulę:log N n(t)N – visų dokumentų skaičius, n(t) – dokumentų, kuriuose pasitaiko trigramas t, skaičius.Šis skaičius vėliau yra naudojamas situacijose, kuriose grąžinami keli, tarpusavyje vienodai panašūs dokumentai. Pavyzdžiui ,,dokumentų valdymo sistemos” ir ,,tekstinės duomenų bazės” gali grąžinti tris dokumentus, kuriuose yra dalis abiejų trigramų, tačiau pirmojo trigramo svarba yra didesnė už antrojo. Tokiu atveju, dokumentai turintys pirmąjį trigramą laikomi svarbesniais. Paieškos metu iškyla klausimas, kuris dokumentas yra pranašesnis už kitą ir labiau atitinka paieškos kriterijus. Tada naudojame tikimybių teoriją. Iliustruokime tai pavyzdžiu: į paieškos lauką įvedamas žodis ,,logic”. Kadangi turime vieno termo užklausą, jam priskiriama tikimybė 1.0. Tuo tarpu šis termas turi tris trigramus: ,,log”, ,,ogi”, ,,gic”. Šiame įgyvendinime visi trigramai yra laikomi atskirais, be to, su jais elgiamasi vienodai, todėl kiekvienam iš jų priskiriamos tokios pat tikimybės. Šiuo atveju 1/3=0.33, kadangi trys trigramai. Gauname tokią tikimybinę išraišką:
1,0 užklausos_termas(logic)0,33 užklausos_trigramas(log)0,33 užklausos_trigramas(ogi)0,33 užklausos_trigramas(gic)Laikykime, kad ,,logic”, kaip ir visi trys trigramai ,,log”, ,,ogi” ir ,,gic”, pasirodo dokumente A_1. Tada turime(tikimybė 1, nes neatsižvelgiama į termų dažnį):1,0 termas(logic, A_1)1,0 termas(log, A_1)1,0 termas(ogi, A_1)1,0 termas(gic, A_1)Po to paimame kiekvieno iš jų svarbos koeficientus:0,53 termo_svarba(logic)0,16 termo_svarba(log)0,41 termo_svarba(ogi)0,41 termo_svarba(gic)Trigramų svarbos mažesnės, nes trigramai pasitaiko didesniame dokumentų kiekyje, negu pilnas žodis. Sekantis žingsnis svarbas sujungti su užklausų termais. ,,logic” rezultatas bus 1,0 * 0,53 = 0,53 (laikome juos nepriklausomais įvykiais). Šis rezultatas projektuojamas taip, kad dokumento ID grąžinamas kartu su jo tikimybe, čia: 0,53 rezultatas(A_1).Tokiu pačiu principu sutvarkome ir trigramus. Pavyzdžiui trigramui ,,log” galutinė tikimybė bus 0,33*0,16=0,05. Abiejų ,,ogi” ir ,,gic” trigramų rezultatai bus 0,13(0,33*0,41). Naudojame ,,log”, ,,ogi” ir ,,gic” tikimybinę sąjungą: 1-[(1-0,05)(1-0,13)(1-0,13)]=0,28.Pastarasis rezultatas sujungiamas su termo rezultatu. Gauname 0,67(=1-[(1-0,53)(1-0,28)]). Tai ir yra galutinė tikimybė, kad A_1 turi panašumų su užklausa ,,logic”. Ji naudojama dokumento eilei nustatyti(kuo didesnė tikimybė, tuo aukščiau stovi dokumentas).Dar vienas labai svarbus trigramų pranašumas prieš termus yra tas, kad jie leidžia ieškoti teksto dokumente netgi jei paieškos užklausa užduota su rašybos klaidomis. Pavyzdžiui, užklausa ,,Lietva” turės šiuos trigramus: ,,Lie”, ,,iet”, ,,etv”, ,,tva”, o originalas ,,Lietuva” – šiuos: ,,Lie”, ,,iet”, ,,etu”, ,,tuv”, ,,uva”. Termų atveju tai būtų visiškai skirtingi žodžiai, o skaidymas į trigramus leidžia aptikti jų tarpusavio panašumus. Šiuo atveju net du trigramai iš penkių(imant žodį ,,Lietuva”) sutampa. O tai jau nemažas tarpusavio panašumas.Taigi trigramai yra pakankamai naudingi ne tik tada, kai tekstiniuose dokumentuose yra rašybos klaidų, bet jie labai praverčia norint užklausą atitinkančius dokumentus sugrupuoti pagal panašumo į užklausą koeficientus. Taip pat šio metodo nauda atsiskleidžia, kai dokumentų dalyse žodžiai ar sakiniai nesikartoja identiškoje eilėje( yra pakeisti, ištrinti ar sukeisti vietomis).

1.3 Trigramų panaudojimas specializuotiems tekstams.Dažnai duomenų bazėse saugomi specializuoti tekstai, pavyzdžiui programų tekstai. Tokiu atveju, uždavinys truputėlį paprastesnis. Juk iš esmės yra konkreti kalbų gramatika, jos taisyklės. Tą mes ir bandysime panaudoti. Tarkim duomenų bazėje saugomos programos parašytos Java kalba. Turime programos fragmentą:If (x != y) then x=1;Trigramus galime traktuoti kaip trijų žodžių sekas.Gausime tokius trigramus: ,,if ( x”, ,,( x !=”, ,,x != y”, ,,!= y )”, ,,y ) then”, ,,) then x”, ,,then x =”, ,,x = 1”, ,,= 1 ;”. Juos reiktų šiek tiek modifikuoti. Kadangi pagrindinis plagijavimo principas yra kintamųjų vardų pakeitimas, reiktų kintamųjų vardus pakeisti bendru vardu, pavyzdžiui ,,kintamasis”, t.y. suvienodinti juos. Gauname: ,,if ( kintamasis”, ,,( kintamasis !=”, ,,kintamasis != kintamasis”, ,,!= kintamasis )”, ,,kintamasis ) then”, ,,) then kintamasis”, ,,then kintamasis =”, ,,kintamasis = 1”, ,,= 1 ;”. Turime kitos Java programos fragmentą: if ( sk != max) then sk=1;Veikdami kintamųjų suvienodinimo principu gauname, kad fragmentai identiški. Taipogi pastebėkime, kad sukeitus metodus vietomis, programa iš esmės nepasikeičia. O trigramai, kaip jau minėjau, leidžia palyginti tekstus, kuriuose sakiniai nesikartoja identiškoje eilėje. Yra dar ir kitų niuansų, bet mes į juos nesigilinsime.Galime teigti, kad struktūrinių tekstų palyginimas trigramų metodu iš vienos pusės yra lengvesnis, nes tekstas turi būti parašytas laikantis tam tikrų konkrečios kalbos taisyklių. Tačiau tai, kad gautus trigramus reikia modifikuoti, pakeisti kintamųjų vardus bendru vardu, apsunkina uždavinį. Vis dėlto galime tvirtinti, kad trigramų panaudojimas specializuotiems tekstams leidžia aptikti plagijavimo atvejus programose parašytose konkrečiomis kalbomis.

2. Duomenų bazių aspektas.2.1. Reliacinių duomenų bazių indeksai.Susidūrus su reliacinėmis duomenų bazėmis, kuriose saugomi tekstiniai dokumentai, atsiranda nauja problema. Dokumentų gausa būna tiesiog milžiniška, ir norėdami atlikti paiešką ar panašumo nustatymą turėtumėme sugaišti tikrai daug laiko. Paprasčiausiu atveju į duomenų bazę įtraukiant naują dokumentą reiktų palyginti jį su kiekvienu duomenų bazėje saugomu dokumentu, gauti tarpusavio panašumo koeficientus. To paspartinimui naudojami indeksai.

Lentelės duomenų indeksas reliacinėse duomenų bazių valdymo sistemose yra duomenų paieškos palengvinimo priemonė. Panašiai kaip knygos dalykinė rodyklė palengvina reikiamų puslapių paiešką knygoje, indeksavimas pagreitina informacijos išrinkimą iš duomenų bazės. Duomenų bazėje indeksas atlieka loginių nuorodų į fizinę duomenų vietą vaidmenį.Tačiau tarp indekso ir knygos dalykinės rodyklės yra ir esminių skirtumų. Skaitytojas pats nusprendžia, ar naudotis dalykine rodykle reikiamai informacijai rasti. Duomenų bazės vartotojas tik sprendžia, ar jam sukurti indeksą. Ieškant duomenų, duomenų bazės valdymo sistema sprendžia pati, ar naudoti paieškai indeksą. Vartotojas neturi jokių galimybių įtakoti duomenų bazių valdymo sistemos sprendimo. Indeksas skiriasi nuo dalykinės rodyklės ir tuo, kad duomenų bazės lentelė gana dažnai turi keletą indeksų, o knygoje paprastai tėra viena dalykinė rodyklė. Panašiai kaip knygoje gali nebūti dalykinės rodyklės, duomenų bazės lentelė gali neturėti nė vieno indekso.Indeksas – tai surūšiuota reikšmių ir nuorodų į reikšmes atitinkamas lentelės eilutės aibė. Indeksas apibrėžiamas vienam ar keletui lentelės stulpelių. Indeksas nėra lentelės duomenų dalis – tai atskiras duomenų bazės objektas. Sukūrus indeksą, duomenų bazės valdymo sistema automatiškai sukuria atitinkamą duomenų struktūrą ir stebi, kad indeksas, besikeičiant lentelės duomenims, nuolat atspindėtų jos duomenis ir kad išliktų išrūšiuotas pagal apibrėžtų stulpelių reikšmes. Indeksas yra tiesiog sūrušiuoto sąrašo kopija, tai jame laikoma tik pagrindinė informacija: požymis, pagal kurį rūšiuojama ir įrašo eilės numerisIndeksai yra labai patogūs todėl, kad duomenų paieška išrūšiuotame masyve yra daug lengvesnė negu neišrūšiuotame. Bet nereikia manyti, kad pakanka saugoti lentelėje išrūšiuotus duomenis. Lentelės duomenys gali būti išrūšiuoti tik pagal vieną kriterijų(tam tikrų stulpelių reikšmes). Jei duomenų masyvas išrūšiuotas pagal vieną kriterijų, tai jis dažnai nėra išrūšiuotas pagal kitą. Kadangi, duomenų paieška lentelėje gali vykti pagal įvairius kriterijus, tai, nors lentelė ir išrūšiuota pagal kurį nors kriterijų, efektyviai paieškai pagal kitus kriterijus reikia papildomų indeksų.
Kadangi duomenų indeksas yra fizinė sąvoka, o ne loginė, tai SQL standarte nėra galimybės kurti indeksus. Tačiau daugumoje komercinių duomenų bazių valdymo sistemų tokia galimybė yra. Kai kuriose iš jų indekso galimybės yra ypač išplėtotos. Indeksas dar reikalingas ir dėl loginės lentelės rakto vartojimo. Prisiminkime, kad lentelės kiekvienos eilutės rakto reikšmių rinkinys turi būti unikalus lentelėje. Vadinasi, kiekvieną kartą, kai į lentelę įterpiama nauja eilutė, duomenų bazių valdymo sistema turi tikrinti ar nebus pažeistas rakto vientisumas. O tai reiškia, kad duomenų bazių valdymo sistema turi patikrinti, ar tuo metu lentelėje dar nėra eilutės su nurodyta INSERT sakinyje rakto reikšme. Šią procedūrą nesunku realizuoti tik turint išrūšiuotą rakto reikšmių masyvą. Jei lentelė turi tik vieną raktą(pirminį), tai duomenų bazių valdymo sistema gali laikyti lentelę išrūšiuotą pagal to rakto reikšmes. Tačiau jei lentelė turi keletą raktų, tai reikalingas papildomas indeksas.Indeksai yra naudojami:1 Siekiant padidinti duomenų paieškos efektyvumą, kadangi paieška išrūšiuotame duomenų masyve yra kur kas lengvesnė negu neišrūšiuotame;2 Siekiant užtikrinti atitinkamų stulpelių reikšmių unikalumą lentelėje, kadangi tik išrūšiuotame duomenų masyve galima greitai patikrinti, ar atnaujinant duomenis nebus pažeistas reikšmių unikalumas.Akivaizdu, kad indeksai suteikia duomenų bazei spartesnes paieškos galimybes, kurios esant ekstremaliai dideliems duomenų kiekiams labai praverčia.

2.2 Trigramų panaudojimas tekstinėse duomenų bazėse.Žinodami trigramų metodų ir indeksų naudą, galime juos apjungti, kad gautumėme optimaliai veikiančią tekstinę duomenų bazę. Kyla klausimas, kaip efektyviausiai panaudoti šiuos dalykus. Tarkime, kad duomenų bazėje yra didelis kiekis tekstinių dokumentų. Lentelė Dokumentai su stulpeliais Numeris, Dokumento_pavadinimas, Tekstas.Dokumento_ID Pavadinimas Tekstas1. A_1 Prašau2. A_2 Prašau man

3. A_3 Mane4. A_4 Mano namas5. A_5 Namo6. A_6 Prašau namo7. A_7 Prašau manęs

Tokiu atveju, galime sukurti dar vieną lentelę Trigramai, kurioje būtų atitinkami stulpeliai Trigramo_ID, Trigramas, Dokumento_ID:

Trigramo_ID Trigramas Dokumento_ID1. pra 1,2,6,72. raš 1,2,6,73. aša 1,2,6,74. šau 1,2,6,75. au_ 2,6,76. u_m 2,77. _ma 2,78. man 2,3,4,79. ane 310. ano 411. no_ 412. o_n 413. _na 4,614. nam 4,5,615. ama 416. mas 417. amo 5,618. u_n 619. nęs 7

Turint šias dvi lenteles, paruošus užklausą, pavyzdžiui, ,,mano”, gautumėme rezultatą:,,man” pasirodo 2,3,4 dokumentuose, ,,ano” pasirodo dokumente numeris 4.Gautiems dokumentų numeriams pritaikome aibių sankirtos operaciją ir randame, kad abu trigramai, o kartu ir žodis ,,mano”, pasirodo dokumente, kurio numeris 4. Trigramai naudingi duomenų bazių valdymo sistemose. Jų pagalba dokumentų identifikacija pagal jų turimą tekstą yra pakankamai efektyvi, kiek tai gali būti. Visgi dėl paieškos efektyvumo tenka paaukoti vietą: sukurti dar vieną lentelę, bet tai nėra taip svarbu turint omenyje duomenų bazių valdymo sistemų galimybes.

2.3 Trigramų metodo tekstinėms duomenų bazėms optimizavimas.Aukščiau pateiktas metodas tikrai nėra vienintelis ir geriausiais sprendimas. Juk jeigu duomenų būtų nežmoniškai daug, tokia paieška tikrai užtruktų gerą laiko tarpą. Todėl reiktų atrasti geresnį variantą. Galbūt reiktų praplėsti lentelę Dokumentai stulpeliu su nuoroda į lentelės Trigramai stulpelį Trigramo_ID:

Dokumento_ID Pavadinimas Tekstas Trigramai1. A_1 Prašau 1,2,3,42. A_2 Prašau man 1,2,3,4,5,6,7,83. A_3 Mane 8,94. A_4 Mano namas 8,10,11,12,13,14,15,165. A_5 Namo 14,176. A_6 Prašau namo 1,2,3,4,13,14,17,187. A_7 Prašau manęs 1,2,3,4,5,6,7,8,19

Tokiu atveju gautumėme abipusias nuorodas iš lentelės Dokumentai į lentelę Trigramai, ir iš lentelės Trigramai į lentelę Dokumentai. Tai leistų efektyviau panaudoti jų sąryšius vykdant paiešką. Vėlgi šis būdas turi trūkumą tuo atveju, kai dokumentų kiekiai dideli, kadangi susidarytų labai ilgas trigramų sąrašas, kurio apdorojimui reiktų nemažai laiko. Galime lentelėje Trigramai įvesti papildomą stulpelį, kuris indikuotų kiek kartų atitinkamas trigramas yra sutinkamas visuose duomenų bazėje laikomuose dokumentuose. Tai leistų žinoti kiekvieno trigramo ,,svarbumą”. Tarkim trigramas ,,man” kartojasi keturis kartus, o trigramas ,,amo” kartojasi du kartus. Kadangi ,,amo” yra rečiau sutinkamas, tai reiškia, kad ieškant, trigramas ,,amo” turėtų didesnę svarbą už trigramą ,,man” ir galėtumėme į tai atsižvelgti. Lentelė Trigramai atrodytų maždaug taip:

Trigramo_ID Trigramas Dokumento_ID Dažnis1. Pra 1,2,6,7 42. raš 1,2,6,7 43. aša 1,2,6,7 44. šau 1,2,6,7 45. au_ 2,6,7 36. u_m 2,7 27. _ma 2,7 28. man 2,3,4,7 49. ane 3 110. ano 4 111. no_ 4 112. o_n 4 113. _na 4,6 214. nam 4,5,6 315. ama 4 116. mas 4 117. amo 5,6 218. u_n 6 119. nęs 7 1

Šios lentelės informacija galime pasinaudoti atliekant paiešką. Tarkim reikia atlikti žodžio ,,prašau man” paiešką : gauname atitinkamus trigramus ,,pra” , ,,raš”, ,,aša”, ,,šau”, ,,au_”, ,,u_m”, ,,_ma”, ,,man”. Pagal lentelės Trigramai stulpelį Dažnis nustatome, kad trigramai ,,u_m” ir ,,_ma” sutinkami dviejuose dokumentuose. Pagal juos ir nustatome, kad paiešką atitinka dokumentai A_2 ir A_7. Norėdami padidinti paieškos tikslumą, galime nustatyti trigramų, pagal kuriuos ieškosime, skaičių. Mano pateiktu atveju, jis yra 2. Tačiau nustatę skaičių 4, imtumėme dar papildomai du trigramus ,,au_”, kuris sutinkamas trijuose dokumentuose, ir ,bet kurį iš likusių, nes jų dažniai vienodi, pavyzdžiui, ,pra”, kuris sutinkamas keturiuose dokumentuose. Šio metodo efektyvumas slypi tame, kad nereikia panaudoti visų trigramų. Naudojami tik rečiausiai sutinkami.Dar galime išrūšiuoti lentelę Trigramai pagal stulpelį Dažnis. Tuomet mažiausią dažnį turintys trigramai būtų greičiausiai atrandami, nes stovėtų lentelės viršuje.Kaip matome, trigramų ir duomenų bazių valdymo sistemos apjungimas duoda pakankamai gerą paieškos idėją. Trūkumas išlieka tame, kad reikia sukurti papildomą lentelę. Taigi, tenka paaukoti vietos tam, kad gautumėme spartesnę paiešką.

3. Dokumentų grupavimo pagal tarpusavio panašumo koeficientą metodas.3.1 Metodo esmė.Dokumentus, saugomus duomenų bazėje, labai patogu palyginti tarpusavyje. Apskaičiuoti tarpusavio panašumo koeficientus, palyginti kiekvieną dokumentą su visais kitais. Tada turėtumėme aibę koeficientų nuo 0 iki 1, kurie leistų aptikti įtartinai panašius dokumentus. Kadangi trigramai puikiai tinka tekstų palyginimui, juos ir naudosime nustatinėdami panašumo koeficientus. Pasirenkame vieną iš galimų koeficientų skaičiavimo formulių, kad ir šią:

S = sutampančių trigramų skaičius

skirtingų trigramų skaičiusAišku, reiktų atlikti didelį kiekį viso teksto palyginimo, kuris užtruktų tikrai nemažą laiko tarpą. Tačiau nereikia pamiršti, kad jis bus atliekamas tik vieną kartą. O tai jau yra privalumas.Pavyzdžiui turime dokumentus A_1, A_2, A_3 ir A_4. A_1 panašumo koeficientai atitinkamai yra: su A_2 – 0,1, su A_3 – 0,3, ir su A_4 – 0,5. A_2 atitinkamai: su A_1 – 0,1, su A_3 – 0,8, o su A_4 – 0,7. Dokumento A_3: su A_1 – 0,3, su A_2 – 0,8, galiausiai su A_4 – 0,9. Ir paskutinis dokumentas A_4: su A_1 – 0,5, su A_2 – 0,7, ir su A_3 – 0,9. Toliau būtina nustatyti panašumo kriterijų, tam tikrą ribą, kurią viršijus, dokumentai būtų laikomi panašiais. Tarkim riba yra 0,75, tuomet panašiais būtų laikomi A_2 su A_3 ir A_3 su A_4. Įtraukiant naują dokumentą į duomenų bazę, reikia atlikti vienkartinį jo palyginimą su visais dokumentais. Pagal gautus panašumo koeficientus ir duotą ribą iš karto galėtumėme atrasti, kurie dokumentai yra panašūs į duotąjį. Pavyzdžiui įtraukiamas dokumentas A_5, jo panašumo koeficientai yra atitinkamai su A_1 – 0,1, su A_2 – 0,3, su A_3 – 0,2, ir su A_4 – 0,5. Tarkim, kad nustatyta riba yra 0,4. Tokiu atveju matome, kad dokumentas A_5 yra panašus į dokumentą A_4.Tai pakankamai primityvus, tačiau tikrai patikimas būdas aptikti galimus plagijavimo atvejus. Dokumentų tarpusavio panašumo koeficientai yra labai svarbi informacija, kurios pagalba galime nesunkiai nustatyti, kurie dokumentai panašūs, o kurie skirtingi.

3.2 Teorinis metodo realizavimas.Pagrindinis klausimas, kuris iškyla analizuojant metodą paprastas. Kur laikyti panašumo koeficientus? Idėja tokia: sudaryti lentelę, kurioje būtų stulpeliai Dokumento_ID, Dokumento2_ID ir Panašumas. Tačiau toks sprendimas nėra galutinis ir tinkamiausias, nes reikėtų saugoti visų dokumentų panašumus. O duomenų bazėje jų skaičius yra labai didelis. Galime pasinaudoti tuo, kad mums nelabai svarbu saugoti tuos panašumo koeficientus, kurie yra maži. Tokiu atveju, galėtumėme nustatyti ribą, kurios pagalba atmestumėme nereikalingus koeficientus. Tarkim, kad riba yra lygi 0,2. Tuomet lentelė Koeficientai atrodytų taip:

Dokumento_ID Dokumento2_ID PanašumasA_2 A_3 0,8A_2 A_4 0,7A_3 A_4 0,9A_1 A_3 0,3A_1 A_4 0,5A_2 A_5 0,3A_4 A_5 0,5

Aukščiau pateikta lentelė turi privalumą tame, kad saugomi ne visi koeficientai. Todėl sutaupoma vieta. Kad efektas būtų dar geresnis, galime išrūšiuoti lentelę Koeficientai pagal stulpelį Panašumas. Tokiu atveju, tarpusavyje panašiausi dokumentai užimtų vietą lentelės viršuje. Gauname tokią lentelę:

Dokumento_ID Dokumento2_ID PanašumasA_3 A_4 0,9A_2 A_3 0,8A_2 A_4 0,7A_1 A_4 0,5A_4 A_5 0,5A_1 A_3 0,3A_2 A_5 0,3

Šis metodas remiasi tuo, kad tereikia vieno dokumentų tarpusavio palyginimo. O jo metu gauta informacija(tarpusavio panašumo koeficientas) išsaugoma lentelėje Koeficientai ir pastoviai naudojama panašiems dokumentams aptikti. Tačiau vėlgi, kad gautumėme efektyvesnę paiešką, tenka paaukoti vietą.

IšvadosDuomenų bazių valdymo sistemos turi išsikovojusios tvirtą poziciją informacinių technologijų rinkoje. Nuo jų atsiradimo, duomenų bazių valdymo sistemos smarkiai evoliucionavo ir tapo neatsiejama mūsų gyvenimo dalimi. Jos naudojamos daugeliui įvairių tikslų, pradedant mažos firmos dokumentų laikymu ir baigiant valstybės krašto apsaugos ministerijos slaptais dokumentais. Kadangi duomenų bazėse laikomų duomenų kiekiai yra labai dideli, kartais nebeužtenka į duomenų bazių valdymo sistemą integruotų paieškos priemonių galimybių. Šiame darbe aš aptariau metodus, kurie įgalina paiešką šiek tiek pagreitinti.Mano aptartos trigraminės technologijos populiarios tekstų identifikacijos problemos sprendimuose. Pagrindinis jų privalumas glūdi tame, kad jos leidžia aptikti panašumo atvejus, kai atskiri teksto gabalai yra sukeisti vietomis, ir netgi tuo atveju, kai tekste yra gramatinių klaidų. Realizuojant jas su struktūrizuotais tekstais, galime nesunkiai aptikti panašumus netgi tuo atveju, kai dalis teksto yra pakeista. Be to, pasaulyje šiuo metu labai paplitusi plagijavimo problema. Atsiranda vis daugiau internetinių puslapių, kuriuose siūloma naudotis kitų žmonių sukurtais tekstais: rašiniais, programomis ir t.t. Savo darbu bandau prisidėti prie to, kad plagiatoriai nebegalėtų taip lengvai išsisukti nuo bausmės. Mano pateikti metodai, iš esmės, yra skirti duomenų bazėms, kuriose būtų saugojamos programos. Vos tik įtraukus naują programą į turimą duomenų bazę, iš karto būtų aptiktos panašiausios į įtrauktąją. Tai leistų patobulinti mokymosi ir švietimo procesą. Studentai ar moksleiviai tiesiog būtų priversti mokytis savarankiškai ir atsiskaitinėti savo pačių sukurtas programas.

Šiame darbe aptariau daugiausiai teorinius aspektus, tačiau sekančiais metais norėčiau kurį nors iš pateiktų metodų realizuoti praktiškai.

LITERATŪRALietuvių kalba:1. http://www.mif.vu.lt/~baronas/dbvs/book/dbs_09.pdf -Romas Baronas. Duomenų bazių sistemos, 2002, 220 KB.

Anglų kalba:1. http://www.cs.unimaas.nl/~wiesman/msctheses/braun.thesis.pdf – Loes Braun. Information retrieval from Dutch Historical Corpora, 465 KB, 2002.2. http://www.ontoweb.org/download/deliverables/wp9del.pdf – Mounia Lalmas, Andrew Graves. Demo of knowledge management support for shared educational material on the semantic web (version 1), 449 KB, 2001.3. http://cnl.psych.cornell.edu/papers/cmc-ma-thesis.pdf – Christopher M. Conway. Tactile sequential learning: artificial grammar learning by touch, 992 KB, 2001.4. http://web.umr.edu/~tauritzd/papers/dissertation.pdf – Daniel Remy Tauritz. Adaptive information filtering concepts and algorithms, 1,07 MB, 2002.5. http://homepages.feis.herts.ac.uk/~comrcml/TR5.3.5.doc – Caroline Lyon, Ruth Barrett, James Malcolm. Experiments in Electronic Plagiarism Detection. 514 KB, 2003.