VILNIAUS UNIVERSITETAS
MATEMATIKOS IR INFORMATIKOS FAKULTETAS
INFORMATIKOS 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)
Vilnius
2004
Turinys
Įvadas 3
1. Trigramų technologija 4
1.1. Trigramai 4
1.2. Trigramų panaudojimas dokumentų paieškoje ir palyginime 4
1.3 Trigramų panaudojimas specializuotiems tekstams 7
2. 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 10
3. Dokumentų grupavimo pagal tarpusavio panašumo koeficientą metodas 12
3.1 Metodo esmė 12
3.2 Teorinis metodo realizavimas 13
Išvados 15
Literatū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čius
Tuo 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.