Opis algorytmów

Z Otwarty System Antyplagiatowy
Wersja z dnia 11:46, 8 paź 2015 autorstwa Acacko (dyskusja | edycje)

(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Skocz do: nawigacja, szukaj

System OSA jest tworzony przez polskich naukowców i doświadczonych programistów/administratorów. Używamy nowoczesnego autorskiego algorytmu będącego wynikiem połączenia kilku metod antyplagiatowych i wzięcia z nich to co najlepsze. Jako jedyni chwalimy się naszymi metodami w świecie naukowym na konferencjach jak i w artykułach naukowych co czyni je pewnymi i sprawdzonymi przez grono polskich i światowych specjalistów.

Przegląd znanych metod i algorytmów

Poniżej zamieszczamy przegląd znanych i opisanych w literaturze naukowej algorytmów antyplagiatowych wraz z wyróżnieniem ich najmocniejszych i najsłabszych cech.

Porównywanie czystych tekstów i wyszukiwanie wspólnych części (String matching)

Najpopularniejszy i najstarszy algorytm używany przez większość firm antyplagiatowych na świecie.

  • Wymaga dostępu do treści wszystkich prac w oryginale
  • Wyszukuje wspólne podciągi słów / znaków
  • Bardzo powolne
  • Złożoność liniowa przy wyszukiwaniu
  • Złożoność kwadratowa przy analizie całej bazy
  • Konieczność iteracji po wszystkich elementach

Model wektorowy (Vector Space Model)

Algorytm w którym każda z prac jest reprezentowana jej modelem matematycznym, zwykle wektorem i na podstawie miar podobieństwa tych wektorów wyliczane jest podobieństwo samych prac.

  • Wymaga przygotowania bazy
  • Krótszy czas porównania dokumentów
  • Możliwość zastosowania różnych miar i metryk podobieństwa
  • Złożoność liniowa / kwadratowa
  • Nie korzysta z oryginałów
  • Konieczność sprawdzenia kandydatów na koniec innym algorytmem
  • Wymaga przechowywania nadmiarowych danych

Odciski palców (Fingerprinting)

  • Wymaga przetworzenia bazy
  • Porównywanie nie pracuje na oryginałach
  • Najszybsze w działaniu
  • Długa faza przygotowania
  • Możliwość zastosowania w bardzo dużych zbiorach
  • Możliwość zbudowania wydajnego indeksu (złożoność logarytmiczna lub stała względem bazy)
  • Konieczność przechowywania nadmiarowych danych

Analiza języka naturalnego (Semantic comparison)

  • Rozpoznawanie tekstów podobnych, o tym samym znaczeniu, parafraza
  • Bardzo dokładne
  • Starają się zrozumieć tekst analogicznie do człowieka
  • Bardzo duża złożoność obliczeniowa, działanie "w sąsiedztwie"

Analiza cytowań (Semantic analysis)

  • Wymagana jest solidnie zrobiona bibliografia wraz z odnośnikami
  • Stosowana głównie w pracach naukowych
  • Bardzo szybka metoda
  • Łatwo oszukać manipulując bibliografią i cytowaniami
  • Można użyć jako dodatkowego algorytmu preselekcji

Uczenie maszynowe (Machine Learning)

  • Wymagany bardzo dobry zbiór uczący
  • Duża złożoność obliczeniowa
  • Naśladują człowieka (sieci neuronowe)
  • Możliwość wykrywania dokumentów podobnych

Stylometria (Stylometry)

  • Możliwość wyszukiwania osób piszących prace dyplomowe na zlecenie (analiza całej bazy)
  • Można ocenić czy praca jest danego studenta na podstawie innych jego tekstów
  • Analiza "gorących słów"
  • Używana w historii (wiek tekstu, autorstwo tekstu)
  • Można oszukać poprzez wcześniejsze użycie programu stylometrycznego, częste błędy użytkownika są poprawiane przez automaty

Algorytmy używane przez Otwarty System Antyplagiatowy

OSA jest systemem hybrydowym, to znaczy, używane przez nią algorytm należy do kilku powyższych grup.

Pierwszym etapem działania algorytmu jest wygenerowanie struktur wyszukujących. Odbywa się to podczas dodawania dokumentów do bazy. Podczas tego procesu dla każdego dokumentu w bazie są wyliczanie specjalne interpretacje matematyczne (wektory, hashe, etc) które służą do zbudowania indeksu dla kolejnych wyszukań. Jest to mechanizm bardzo podobny do generowania indeksów wyszukujących jak to robią wszystkie wyszukiwarki internetowe jak Nekst, Google czy Bing. Prostszą analogią jest indeks w bazie danych.

Powyższa operacja jest dość ciężka, to znaczy że wygenerowanie indeksów może potrwać w zależności od wielkości bazy, ale ta operacja jest wykonywana jednokrotnie dla każdego dokumentu w bazie a dzięki niej samo wyszukanie czegoś w bazie jest nieporównywalnie szybsze niż iteracja po wszystkich dokumentach w bazie. Dodatkowo budując specjalne struktury można złożoność obliczeniową sprowadzić do stałej względem bazy co daje niesamowite przyśpieszenie wyszukiwania w bardzo dużych zbiorach danych jak Nekst czy ORPPD.

Sam proces wyszukiwania czegoś można podzielić na dwa etapy:

  1. Zapytanie do indeksu wyszukującego
  2. Szczegółowe porównanie

W pierwszym kroku wybieramy w bardzo krótkim czasie kandydatów wobec których jest istotne podejrzenie o naruszenie praw autorskich, zaś w drugim generowane jest podgląd graficzny dla osoby oglądającej wyniki ułatwiający ostateczną decyzję promotorowi czy dana praca jest plagiatem czy nie (Interpretacja wyników). Druga faza jest droższa obliczeniowo, ale z racji wykonywania jej na ograniczonym i małym zbiorze kandydatów, jest nadal bardzo szybka.

Przy generowaniu indeksów są używane metody z rodziny: algorytmów wektorowych, generujących skróty (fingerprinting), analizy języka naturalnego, zaś do generowania szczegółowych porównań używane są algorytmy z rodziny analizy języka naturalnego i porównywania tekstów.

Obecnie pracujemy nad włączeniem do algorytmu analizy cytowań oraz rozpoznawania stylu piszącego.