Mam obowiązek odfiltrowywania wulgaryzmów od zgłoszeń użytkowników w aplikacji internetowej opartej na Javie. Klient jest świadomy zarówno problemu Scunthorpe, jak i problemu Clbuttic i zaakceptował konsekwencje. Proszę, nie chcę debaty na temat zalet jej braku cenzury.
Istnieją dwa bity danych:
- Zgłoszenie użytkownika, które może potencjalnie zawierać około 500 słów;
- Jednokolumnowa tabela bazy danych zawierająca niedozwolone słowa. Tabela może zawierać wiele tysięcy rekordów.
Wydaje mi się, że obecne rozwiązanie jest złe:
- Cała tabela jest ładowana do statycznego ciągu [] podczas uruchamiania w singletonie (tym samym rezydując w pamięci).
- Dla każdego zgłoszenia użytkownika przeglądamy tablicę i wykonujemy .indexOf (), aby sprawdzić, czy jakieś słowo w ciągu String [] pojawia się w zgłoszeniu.
- Jeśli się pojawi, zastępujemy znakami w stylu% $ # @% -. Odbywa się to poprzez tokenizowanie przesłania użytkownika, przechodzenie przez całe przesyłanie użytkownika jako tokeny (ponownie) i zastępowanie każdego wystąpienia znalezionego słowa.
W tym rozwiązaniu może być błyskotliwość, ale jestem sceptyczny. I patrząc na to przez jakiś czas, nie mogę znaleźć drogi, by to minąć.
Pytanie brzmi: jakie rozwiązanie zapewni dobrą wydajność i, miejmy nadzieję, rozsądne zachowanie dla przyszłych programistów po zwolnieniu mnie z powodu niefiltrowania jakiegoś niejasnego słowa, o którym nigdy nie słyszałem?
Odpowiedzi:
Jedynym sposobem inteligentnego filtrowania słów jest użycie fonicznego systemu dopasowywania. Kilka lat temu napisałem bardzo skuteczny filtr wulgaryzmów dla bardzo popularnej gry online dla wielu graczy dla nastolatków i nastolatków.
Został oparty na wysoce zmodyfikowanym algorytmie Double MetaPhone , który został ulepszony, aby był bardziej dokładny zamiast domyślnego, który ma dopasować jak najwięcej rzeczy. Był tak niezwykle skuteczny, ponieważ wychwytywał błędy ortograficzne i fonetyczne tak samo jak rzeczywiste słowa. Dodałem także
l33tmów itxtmów do algorytmu MetaPhone, co czyni go bardziej algorytmem Triple / Quad Metaphone.Zawierał procesor wstępny, który kompresował bieżące litery i wykrywał takie rzeczy, jak dzieci układające rzeczy
w o r d spoprzez inteligentne kompresowanie liter razem i eliminowanie uruchamiania duplikatówwwoorrddss, ponieważ był bardzo wyspecjalizowany tylko w języku angielskim.8 lat temu było wystarczająco szybkie, aby można było go używać w strumieniu systemu czatu w czasie rzeczywistym bez zauważalnego opóźnienia z dziesiątkami tysięcy użytkowników na jednym rdzeniu systemu CPU.
Mieliśmy listę słów zakodowanych w tabeli w bazie danych przez Metaphone i została ona załadowana do statycznej mapy, która była zaskakująco mała i nigdy nie musieliśmy robić nic specjalnego, aby uzyskać dostęp do listy zabronionych słów, mogłem dodać wykrywanie fraz przy użyciu tych samych technik za darmo.
Oczywiście miałem bieżący dziennik wszystkich czatów od tysięcy dzieciaków próbujących złamać system w czasie rzeczywistym, więc miałem dość obszerny zestaw danych, z którymi mogłem pracować. Sposób, w jaki rejestrowałem, był taki, kiedy ktoś uruchomił filtr z wartością pozytywną, zalogowałem kilka kolejnych wiadomości czatu, które nie uruchomiły filtru w ten sposób, w ten sposób, jeśli znalazł sposób obejścia określonego słowa lub frazy, mógłbym dostosuj mój system i złap to. Po kilku tygodniach byłem dość kuloodporny.
źródło
Jeśli chcesz skutecznie dopasowywać, algorytm Aho Corasick jest całkiem dobrą opcją (jestem pewien, że można znaleźć implementację Java).
Oczywiście prawdopodobnie zechcesz wstępnie przetworzyć zgłoszenie w celu zastąpienia nieprawidłowości w pisowni („$ '->' s ',' @ '->' a ',' | <'->' k 'itp.)
źródło
Zamiast ładować do statycznego ciągu [], użyj HashMap [] lub innego rodzaju drzewa binarnego (jeśli chcesz poprawić wyszukiwanie), ustawiając ciąg jako klucz w haszu. Podziel łańcuch na spacje i usuń znaki interpunkcyjne. Następnie możesz zapytać HashMap dla każdego słowa w podziale ciągu; jeśli skrót mapy wróci z wartością inną niż null, to wiesz, że masz złe słowo.
To, co zawodzi tutaj, to problem Clbuttic, w którym ktoś dodaje losowe znaki wokół złego słowa ex.
bhassdaźródło
Korzystanie z systemu fonicznego nie jest jedynym rozwiązaniem w jakikolwiek sposób, ale może być najprostsze, ponieważ istnieje wiele bibliotek open source, które robią takie rzeczy.
Najtrudniejszą częścią zawsze będzie pasująca część każdego algorytmu i brzmi to tak, jakby twój mecz był dość powolny i naiwny. Nie można zakładać, że indexOf będzie pasował poprawnie bez jakiejkolwiek formy kontroli pomocniczej.
Ponadto skończysz zapętlanie się przez cały Ciąg N razy, gdzie N jest liczbą słów na czarnej liście. Sugestie użycia Set lub HashMap z pewnością nieco poprawią.
W większości przypadków algorytm oparty na stanie liniowym jest najlepszy i najszybszy. Napisałem rozwiązanie dla Clean Speak, które wykorzystuje ten typ algorytmu z systemem dopasowania fonicznego przed procesem. To było jedyne rozwiązanie, które nie komplikowało się, gdy osadzone jest wulgaryzmy (jeśli foo to wulgaryzmy, osadzanie jest obrzydliwe) i było w stanie zachować wysoki poziom wydajności. Ładnie skaluje się także dla innych języków bez implementacji nowych kodeksów.
Wreszcie, wstępne przetwarzanie dowolnej formy jest na ogół czymś, czego należy unikać. W większości przypadków możesz zrobić to samo w sposób liniowy, posługując się każdym ze znaków w ciągu.
Oczywiście sugeruję spojrzenie na inne rozwiązania w dłuższej perspektywie, ponieważ w większości aplikacji obsługa treści generowanych przez użytkowników jest bardziej złożona niż tylko filtrowanie wulgaryzmów. Często chcesz również filtrować dane osobowe, takie jak e-maile i numery ubezpieczenia społecznego, a czasem takie rzeczy jak adresy URL. Ponadto stwierdziliśmy, że większość aplikacji wymaga pewnego rodzaju systemu moderacji i wyszukiwania treści. Zwiększa to znacznie złożoność.
źródło
To, co chcesz zrobić w takim przypadku, to określenie, która z dwóch list słów jest mniejsza. Powiedz, że Twoja lista „verboten” zawiera 2000 słów, a maksymalna liczba zgłoszeń użytkownika to 500 słów. W takim przypadku przejdziesz przez listę słów w zgłoszeniu użytkownika i po kolei przeszukasz je na liście zabronionych słów i odwrotnie.
Inną zmianą, którą wprowadziłbym, jest to, że nie przechowujesz listy zabronionych słów w ciągu [] - jeśli przeszukujesz tablicę, masz wyszukiwanie O (n) na słowo w zgłoszeniu użytkownika. To bardzo źle. Spróbuję umieścić strukturę danych, w której patrzysz, w jakiejś asocjacyjnej strukturze kontenera lub drzewa, która ma lepszą wydajność wyszukiwania (log n zamiast n). Wyzwanie polegałoby na tym, że jeśli umieścisz zgłoszenie użytkownika w tym kontenerze, będziesz musiał śledzić pozycję słowa, abyś mógł zrekonstruować dane wejściowe lub zaktualizować ciąg wejściowy, jeśli masz trafienie wyszukiwania.
źródło