Czy możecie polecić jakąś książkę, stronkę odnośnie wykrywania powtarzalności kodu

[Elzulninho 0]

Witam.

Znacie może jakieś ciekawe strony,książki cokolowiek co może pomóc w zrobieniu zadania które ma polegać na porównywaniu tekstu(wykrywanie ciągu podobieństw) w języku C. Coś na zasadzie plagiatora np prac dyplomowych.

Pozdrawiam

[unic0rn 0]

osobiscie sie z tym nie spotkalem, ale podstawowa zasada bedzie odnajdywanie ciagow o tym samym znaczeniu. trudniejsze w przypadku C niz jezyka dajmy na to polskiego.

 

w przypadku polskiego wycialbym nadmiarowe whitespace, interpunkcje, sprowadzil wszystko do lowercase, wycial znaki diakrytyczne i szukal identycznych ciagow.

 

w przypadku C podobienstwo konczy sie na wycieciu nadmiarowych whitespace, przy czym wycinalbym absolutnie wszystko co nie wplynie na dzialanie kodu.

 

kolejny etap bylby juz o wiele bardziej zlozony - nalezaloby zastapic wszystkie nazwy zmiennych/stalych identyfikatorem o stalej dlugosci, zawierajacym w sobie numer przypisany do danej zmiennej/stalej, po czym szukac identycznych ciagow, jednoczesnie laczac identyfikatory z obu ciagow w pary, by moc wyjsc z petli wczesniej w przypadku znalezienia niezgodnosci (optymalizacja wydajnosciowa).

 

mozna tez podejsc do problemu od strony kompilatora:

http://gcc-python-plugin.readthedocs.io/en/latest/gcc-overview.html

https://gcc.gnu.org/onlinedocs/gccint/index.html

 

generalnie chodzi o znalezienie kodu, ktory dziala tak samo, niekoniecznie bedac prostym copy-paste. wypadaloby tez wziasc pod uwage, ze ktos chcacy celowo ominac tego typu detekcje moze dodac w kodzie zrodlowym operacje logiczne nie majace wplywu na wynik, ktore proste porownywanie tekstu z mapowaniem zmiennych beda w stanie oszukac, i jedyna pewna metoda na detekcje tego byloby porownywanie reprezentacji posredniej wygenerowanej przez kompilator po fazie optymalizacji kodu.

 

jeszcze inna kwestia w przypadku porownywania rozwiazan zadan rodem z uczelni jest fakt, ze po wyeliminowaniu czynnikow typu formatowanie czy nazwy zmiennych, moze sie okazac ze to samo zadanie zostalo rozwiazane przez dwie rozne osoby w sposob identyczny, gdyz zostalo to wymuszone przez jego prostote.

[209458 867]

https://en.wikipedia.org/wiki/Plagiarism_detection#In_source_code tu masz wiki na start, a ogólnie jak wpiszesz w google "source code plagiarism" wyskakuje sporo artykułów. Generalnie może być tak, że autorzy rozwiązań praktycznych mogą nie chcieć zdradzać wszystkich detali, bo ich znajomość ułatwia znajdowanie sposobów na oszukiwanie. Byłem dawno temu na prezentacji gościa, który brał udział w opracowaniu takiego systemu na potrzeby olimpiady informatycznej. I tam generalnie koncentrowali się na parsowaniu składni, tak jak robi to IDE/Kompilator. Dodatkowy bonus z takiego podejścia jest taki, że jak masz parsery różnych języków do wspólnej struktury możesz wyłapywać plagiaty polegające na przepisaniu kodu na inny język o odmiennej składni, choć nie wiem czy tego akurat potrzebujesz. Do tego oczywiście znikną różnice wynikające ze zmian nieistotnych składniowo jak komentarze, podział linii itp. Natomiast parsowanie pełnej gramatyki rozwiniętego języka jak C czy java jest skomplikowane, choć można szukać gotowców na sieci. Natomiast z tego co zrozumiałem przy tej olimpiadzie skupiali się przede wszystkim na strukturze instrukcji sterujących: warunkowych (if, switch), pętli i wywołań funkcji, z założenia, że inne instrukcje łatwo przerobić na pałę (tu i ówdzie pozmieniać kolejność, gdzie nie ma znaczenia), podzielić wyrażenia wprowadzając zmienne pośrednie, ew. dodać jakieś instrukcje nadmiarowe). Z tym, że tu też znaczenie m sama baza programów do analizy, bo zadania algorytmiczne są jednak dość specyficzne.