Jakich algorytmów mogę użyć do wykrycia, czy artykuły lub posty są duplikatami?


17

Próbuję wykryć, czy artykuł lub post na forum jest zduplikowanym wpisem w bazie danych. Zastanowiłem się nad tym, dochodząc do wniosku, że ktoś, kto powiela treść, zrobi to za pomocą jednego z trzech (w malejącym, trudnym do wykrycia):

  1. prosta kopia wklej cały tekst
  2. kopiuj i wklejaj fragmenty tekstu łącząc je z własnymi
  3. skopiuj artykuł z zewnętrznej strony i zamaskuj jako własną

Przygotowanie tekstu do analizy

Zasadniczo wszelkie anomalie; celem jest uczynienie tekstu możliwie „czystym”. Aby uzyskać dokładniejsze wyniki, tekst jest „standaryzowany” przez:

  1. Usuwanie zduplikowanych białych znaków i przycinanie na początku i na końcu.
  2. Nowe linie są znormalizowane do \ n.
  3. Tagi HTML są usuwane.
  4. Za pomocą RegEx o nazwie Daring Fireball URL są usuwane.
  5. Używam kodu BB w mojej aplikacji, więc idzie do.
  6. (ä) wyśrodkowane i obce (oprócz Enlgisha) są konwertowane na ich obce formy.

Informacje o każdym artykule przechowuję w (1) tabeli statystyk oraz w (2) tabeli słów kluczowych.

(1) Tabela statystyk Poniższe statystyki są przechowywane o treści tekstowej (podobnie jak ten post)

  1. długość tekstu
  2. liczba liter
  3. Liczba słów
  4. liczba zdań
  5. średnia słów na zdanie
  6. wskaźnik automatycznej czytelności
  7. wynik strzelającej mgły

W przypadku języków europejskich należy stosować Coleman-Liau i indeks zautomatyzowanej czytelności, ponieważ nie używają liczenia sylab, dlatego powinny dawać dość dokładny wynik.

(2) Tabela słów kluczowych

Słowa kluczowe są generowane przez wykluczenie ogromnej listy słów stop (słów wspólnych), np. „The”, „a”, „of”, „to” itp. Itp.

Przykładowe dane

  • długość_tekstu, 3963
  • liczba_literów, 3052
  • word_count, 684
  • zdanie_licznik, 33
  • word_per_sentence, 21
  • gunning_fog, 11.5
  • auto_read_index, 9.9
  • słowo kluczowe 1, zabity
  • słowo kluczowe 2, oficerowie
  • słowo kluczowe 3, policja

Należy zauważyć, że po zaktualizowaniu artykułu wszystkie powyższe statystyki są generowane ponownie i mogą mieć zupełnie inne wartości.

Jak mogę wykorzystać powyższe informacje do wykrycia, czy artykuł, który jest publikowany po raz pierwszy, już istnieje w bazie danych?


Wiem, że wszystko, co zaprojektuję, nie będzie idealne, największym ryzykiem jest (1) Treść, która nie jest duplikatem, zostanie oznaczona jako duplikat (2) System zezwala na duplikowanie treści.

Algorytm powinien więc wygenerować numer oceny ryzyka od 0, że nie jest duplikatem, ryzyko 5 jest możliwe, że jest duplikatem, a 10 jest duplikatem. Jeśli jest powyżej 5, istnieje duża możliwość, że treść jest zduplikowana. W takim przypadku treść może zostać oflagowana i powiązana z artykułami, które są możliwymi duplikatami, a człowiek może zdecydować, czy usunąć, czy zezwolić.

Jak powiedziałem wcześniej, przechowuję słowa kluczowe do całego artykułu, jednak zastanawiam się, czy mógłbym zrobić to samo na podstawie akapitów; oznaczałoby to również dalsze oddzielenie moich danych w bazie danych, ale ułatwiłoby to wykrycie (2) w moim początkowym poście.

Myślę o średniej ważonej między statystykami, ale w jakiej kolejności i jakie byłyby konsekwencje ...


Jeśli jest to dokładne dopasowanie, możesz po prostu ustawić pole na unikalne. Jeśli nie, musisz zdecydować, w którym momencie tekst może zostać uznany za kopię lub ściśle powiązane dzieło.
James P.,

2
Istnieje wiele kierunków, w których może pójść tego rodzaju analiza. Ludzie piszą całe książki na ten temat. Jeśli Twoim celem jest określenie „względnej bliskości”, naprawdę nie masz innego wyboru, jak zagłębić się w tak zwane przetwarzanie języka naturalnego i uczenie maszynowe . Tak nazywają to informatycy, ale tak naprawdę to tylko zaawansowana analiza statystyczna. Dobrym punktem wyjścia może być analiza odległości levenshtein, ale „głupie” statystyki, takie jak liczba słów / zdań, prawdopodobnie niewiele dla ciebie zrobią.
rdlowrey

1
Ponadto przed migracją z SO oznaczono to [php], więc możesz sprawdzić natywną funkcję levenshtein w php
rdlowrey

Świetny pomysł na sprawdzenie przez człowieka prawdopodobnie duplikatów! Możesz być w stanie automatycznie zdecydować, że> 7 jest duplikatem, a <6 jest inny i ludzie sprawdzają tylko wyniki 6 lub 7. Wiem, że przy identyfikacji spamu istnieje maszyna-nie-zna-i-człowiek- nie zna żadnej z tych kategorii; szara strefa między niemal duplikatem a oryginalnym dziełem, w której najlepsze, co możesz zrobić, to wykonać nieco arbitralną decyzję.
GlenPeterson

@rdlowrey - Algorytmy Levenshteina wykorzystałem w podobnym projekcie, który zrobiłem w języku C #. Zgadzam się, to dobre miejsce na rozpoczęcie i może być wystarczające.
jfrankcarr

Odpowiedzi:


4

Istnieje wiele algorytmów zajmujących się podobieństwem dokumentów w NLP. Oto przełomowy artykuł opisujący różne algorytmy. Również wikipedia ma większą kolekcję. Opowiadam się za miarą Jaro Winklera i wykorzystałem ją do projektów szkolnych w metodach skupiania aglomeracyjnego.


6

Spójrz na algborithm Rabin-Karp . Używa kroczącego skrótu, podobnie jak rsync, aby zminimalizować bajty przesyłane podczas synchronizacji. Dostosowując rozmiar okna używanego dla skrótu, możesz uczynić go mniej lub bardziej wrażliwym. RK służy między innymi do wykrywania plagiatu, który w zasadzie szuka swoistych duplikatów.


4
Problem, który opisuje OP, przypomina dokładnie wykrywanie plagiatu i sugerowałbym to jako pierwsze miejsce, w którym należy szukać pomocy. (Pamiętaj tylko, aby podać swoje źródła!)
Caleb,

4

Pierwszym krokiem może być wykrycie zdań (lub innego rozsądnego bloku danych. Weź te bloki i usuń wszelkie dane mete, html losowe białe spacje, zwroty itp. Weź MD5 wyniku i zapisz go w tabeli. Możesz następnie dopasuj do tych bloków, aby spróbować znaleźć dopasowania.

Jeśli to nie zadziała, możesz spróbować n-gramów. Tutaj potrzebujesz jednego wpisu każdego słowa na stronie, ale powinno być w stanie dać ci całkiem dobre dopasowanie.

http://en.wikipedia.org/wiki/N-gram


Miary oparte na n-gramach są znacznie lepsze niż wartości mieszające md5, szczególnie w przypadku danych częściowo ustrukturyzowanych, takich jak HTML.
Candide

1

Aby uzyskać dokładną matematykę, przechowuję skrót, a następnie go porównuję.

Myślę, że systemy używane do egzaminów mierzą grupy słów, a następnie częstotliwość grup każdej wielkości. Na przykład łańcuch 30 skopiowanych słów uzyskałby 5 punktów ryzyka, a 5 wystąpień 10 łańcuchów wyraziłoby 5 punktów. Wtedy będziesz miał 30 punktów za każde 500 słów.

Naprawdę potrzebujesz algorytmu semantycznego, aby słowa takie jak „także” i „i” były parsowane tak samo.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.