Úvod
Cílem projektu Plagiáty z webu, který jsem vytvořil v rámci předmětu Projekt z umělé inteligence, je vytvoření webové aplikace, která umožní ověřit, zda některé části zadaného textu nebyly opsány z dokumentů dostupných na Internetu. Pro nalezení odkazů na potenciální zdrojové dokumentů je použita API internetového vyhledávače Yahoo. Dokumenty z nadějných odkazů jsou staženy a podrobeny metodě na prověření podobnosti. Aplikace funguje poloautomaticky – uživatel rozhoduje jestli se mají vyhledat další odkazy nebo ověřit další potenciálně podobné dokumenty z nalezených odkazů.
Aby byla aplikace schopná nalézt plagiát, musí být splněny následující podmínky:
- zdrojový dokument podobné pasáže je indexován vyhledávací službou Yahoo, veřejně přístupný a formátu HTML
- podobná pasáž se skládá z pěti a více slov, ne nutně v totožném pořadí a může obsahovat několik vložených slov
Změny
| 21. května 2008 | – rozšíření dokumentace |
| 19. května 2008 | – přidána možnost volby maximální délky vzorku |
| 15. května 2008 | – vylepšení dokumentace |
| 13. května 2008 | – přidán zdrojový kód ke stažení |
| 12. května 2008 |
– zvolena metoda pro výběr vyhledávacích vzorků
– vytvořen adaptabilní systém pro omezení požadovaného počtu výsledků vyhledávání u jednotlivých vzorků – vylepšen a zrychlen algoritmus pro nalezení podobných částí mezi dvěma texty |
| 28. dubna 2008 |
– naprogramován převod HTML stránek na prostý text
– implementován algoritmus pro nalezení podobných částí mezi dvěma texty |
| 1. dubna 2008 | – zvolena API Yahoo pro vyhledávání na Internetu |
| 28. března 2008 | – založena webová stránka projektu |
Ke stažení
Zdrojový kód CGI skriptu v Ruby (obsahuje jedno rozšíření Ruby v C), pod licencí GNU GPL: plagiaty_z_webu.tgz
Popis fungování aplikace
Aplikace se skládá z CGI skriptu, který jsem naprogramoval pomocí jazyka Ruby. Ke generování dynamických WWW stránek využívám šablonový systém eRuby a Ruby modul CGI. První krok pro nalezení podobných dokumentů spočívá ve využití internetové vyhledávače k získání odkazů na potenciálně podobné dokumenty.
Algoritmus pro získání nadějných odkazů na podobné dokumenty
Ověřovaný text se rozloží na jednotlivá slova (oddělovači jsou mezery, tabelátory a nové řádky). Aplikace vytvoří vzorky pokrývající celý ověřovaný text, které obsahují několik desítek po sobě jdoucích slov. To kvůli snížení množství vyhledávacích dotazů pro dlouhé texty a omezení velikosti dotazu na 1 kB. Uživatel může ovlivnit maximální délku vzorků – kratší usnadňují vyhledání nadějných odkazů, ale vedou ke zpomalení jednotlivých kroků vyhledávání. Sousední vzorky se překrývají na několika slovech, aby se eliminovala možnost rozdělení podobné pasáže na porovnávacím algoritmem nerozpoznatelné části.
Pro každý vzorek jsou paralelně získány výsledky vyhledávání pomocí vyhledávací API Yahoo. V počáteční fázi je vyhledávání nastaveno na hledání všech slov ze vzorku (all). Z výsledku vyhledávání aplikace využije odkaz, MIME formát souboru a shrnutí s úryvky pasáží (oddělené třemi tečkami), které obsahují vyhledávaná slova. Nadějnost toho kterého odkazu na nalezení plagiátu mě napadlo zjistit porovnáním podobnosti úryvků ze shrnutí s vyhledávanými slovy. K tomu účelu jsem použil stejný algoritmus, který dále využívám na určení míry podobnosti dvou dokumentů. Počet požadovaných výsledků vyhledávání je pro každý vzorek variabilní a po každém kroku se mění v závislosti na úspěšnosti vyhledaných odkazů. Pokud není nalezen pro vzorek žádný odkaz, změní se způsob vyhledávání ze všech (all) jen na některá slova (any).
Z nadějných výsledků vyhledávání jsou vybrány odkazy na dokumenty (zatím jen HTML stránky) s nejvyšší mírou podobnosti, u kterých může být dále prozkoumávána podobnost s ověřovaným textem. V tom případě jsou jednotlivé dokumenty paralelně staženy, převedeny do textové podoby a podrobeny algoritmu na vyhledávání podobných částí.
Algoritmus pro nalezení podobných částí mezi dvěma texty
Nabízelo se využít např. algoritmus pro nalezení nejdelšího shodného podřetězce (Longest common subsequence problem), který je používán nástrojem diff. S ohledem na kvadratickou složitost vzhledem k počtu slov, jsem musel zvolit odlišný přístup. Výhodou bylo, že hledaný algoritmus nemusel být úplně přesný. Dále pomohlo, že podobné pasáže se sestávají ze shluků podobných slov, takže postačuje ověřovat jen určité okolí každého slova.
Princip algoritmu spočívá v nalezení takových totožných slov v obou textech, které mají co nejmenší vzdálenost v každém z textů od dalších totožných slov. Nalezené vzdálenosti jsou základem pro výpočet indexu podobnosti těchto slov. Dále jsou vybrána jen podobná slova vytvářející shluky.
Nejprve je pro ověřovaný text vytvořena hešovací tabulka jednotlivých slov odkazující na pole všech pozic výskytu tohoto slova v textu. Porovnávaný text je taktéž rozložen na slova, pro která se postupně určí index podobnosti. Základ výpočtu indexu podobnosti tvoří kombinovaná vzdálenost dvojice slov v porovnávaném i ověřovaném textu, která se získá sečtením těchto dvou vzdáleností a zvýšením o jedna v případě, že pořadí dvojice slov je mezi oběma texty opačné. Každá vzdálenost potom odpovídá nepřímou úměrou určitému indexu podobnosti. Celkový index podobnosti jednoho slova porovnávaného textu se získá jako maximum součtu indexů podobnosti, které se vypočítá z minimálních kombinovaných vzdáleností mezi zvolenou pozicí tohoto slova a pozicí okolních slov v ověřovaném textu. Pro tuto část algoritmu bylo, vzhledem k velkému počtu opakování jednoduchého výpočtu, použití Ruby velmi zpomalující, proto jsem ji naimplementoval jako rozšíření Ruby napsané v C.
V posledním kroku dochází k eliminaci indexu podobnosti u slov, která se nevyskytují ve větším shluku. Kontroluje se hustota slov s vyšší mírou indexu podobnosti, než je přednastavený limit, v každém úseku osmi slov porovnávaného textu. Všechna slova, kterou nejsou součástí nějakého z úseků s dostatečnou hustotou podobných slov (pět slov na úsek), jsou brána jako nepodobná.
Výsledkem algoritmu je pole s indexem podobnosti (0 – 100 %) pro každé slovo porovnávaného textu. Dále je zjištěn celkový počet podobných slov a míra podobnosti celého porovnávaného textu s ověřovaným textem, která se vypočítá jako součet míry podobnosti pro všechna slova porovnávaného textu dělený počtem podobných slov.
Závěr
Aplikace funguje celkem obstojně, i když by bylo vhodné lépe vyladit některé parametry na reálných datech. Dále se nabízí množství funkcí, které by bylo vhodné vylepšit. Například při porovnávání textů by bylo vhodné přeskakovat netextové symboly (čárky, tečky, atd.). Většina nyní přednastavených parametrů by mohla být v určitém rozsahu volitelná. Také by se vyplatilo rozšířit ověřování na další formáty dokumentů: pdf, ps, txt a jiné textové dokumenty.
Kontakt
S připomínkami a dotazy mě můžete kontaktovat na e-mailové adrese: _tom_ at centrum.cz.