Производительность фильтра ненормативной лексики в Java

9

У меня есть требование отфильтровать ненормативную лексику по представлениям пользователей в веб-приложении на основе Java. Клиент знает как о проблеме Сканторпа, так и о проблеме Clbuttic и принял последствия. Пожалуйста, я не желаю спорить о достоинствах отсутствия цензуры.

Есть два бита данных:

  1. Представление пользователя, которое может содержать 500 слов или около того;
  2. Таблица базы данных с одним столбцом, содержащая запрещенные слова. В этой таблице может быть много тысяч записей.

Настоящее решение кажется мне неправильным:

  1. Вся таблица загружается в статическую строку [] при запуске в синглтоне (таким образом, находится в памяти).
  2. Для каждой пользовательской отправки мы выполняем цикл по массиву и выполняем .indexOf (), чтобы увидеть, появляется ли какое-либо данное слово в строке [] в отправке.
  3. Если он появится, мы заменим его символами в стиле% $ # @%. Это делается путем токенизации пользовательской отправки, повторения всей пользовательской отправки в виде токенов (снова) и замены каждого экземпляра найденного слова.

В этом решении может быть блеск, но я настроен скептически. И, посмотрев на это какое-то время, я не могу найти дорогу.

Вопрос в том, что такое решение, которое даст хорошую производительность и, будем надеяться, будет разумным для будущих разработчиков поддерживать после того, как меня уволят за неспособность отфильтровать какое-то неясное слово, о котором я никогда не слышал?

blueishgoldfish
источник
Вы говорите, что это кажется вам неправильным, не говоря нам, почему вы думаете, что это неправильно. Затем вы запрашиваете эффективное решение, не сообщая нам, каким образом текущее решение недостаточно. Сколько текстов в секунду вы получаете, сколько из них вы можете обработать?
пользователь неизвестен
Я думал, что решение было неправильным, прежде всего потому, что кодовая база, в которой я работаю, неадекватна и небрежна. Учитывая мою предвзятость, я не доверял своему собственному недоверию. Я чувствовал, что мнение других будет полезным. То, что вызывало у меня сигналы тревоги, было String [] (что это за 1999?), Циклически перебирая очень большой String [] вместо гораздо меньшего набора данных, который пользователь отправляет, вложив цикл в цикл String [] с отправкой токенов и так далее. Ожидаемое использование не определено, в идеале было бы неплохо элегантное решение с разумной производительностью.
blueishgoldfish
2
«Разумная производительность» может означать что угодно. Если у вас нет конкретной цели, вы не можете знать, достигли ли вы ее. Если вы ускорите процесс, который будет в 100 раз быстрее - это цель? Если пользователь ждет 1 мс или 1/10 с? Пользователь не получит выгоды от вашей работы.
пользователь неизвестен

Ответы:

18

Единственный способ сделать интеллектуальный фильтр слов - это использовать систему фонового сопоставления. Я написал очень эффективный фильтр ненормативной лексики для очень популярной многопользовательской онлайн-игры для подростков и подростков несколько лет назад на Java.

Он был основан на сильно модифицированном алгоритме Double MetaPhone , который был настроен так , чтобы быть более точным, а не по умолчанию, который должен соответствовать как можно большему количеству вещей. Это было так чрезвычайно эффективно, так как оно уловило неправильное и фонетическое написание точно так же, как и настоящие слова. Я добавил l33tговорить и txtговорить с алгоритмом MetaPhone, что делает его более похожим на алгоритм Triple / Quad Metaphone.

Он имел препроцессор, который сжимал бегущие буквы и обнаруживал такие вещи, как дети, складывающие вещи w o r d s, интеллектуально сжимая буквы вместе и удаляя дубликаты, например wwoorrddss, он был очень специализирован только для английского языка.

Это было достаточно быстро 8 лет назад, чтобы использовать его в потоковом режиме в режиме реального времени без каких-либо заметных задержек с десятками тысяч пользователей в одноядерной системе ЦП.

У нас был список слов, которые были зашифрованы Метафоном в таблице в базе данных, и он был загружен в удивительно небольшую статическую карту, и нам никогда не приходилось делать ничего особенного, чтобы получить доступ к списку запрещенных слов, я смог добавить Обнаружение фразы с использованием тех же приемов практически бесплатно.

Конечно, у меня был текущий журнал всех чатов от тысяч детей, пытающихся сломать систему в режиме реального времени, поэтому у меня был довольно полный набор данных для работы. Я вел журнал, когда кто-то запускал фильтр с положительным результатом, и я регистрировал следующие несколько сообщений чата, которые не запускали фильтр , таким образом, если они находили способ обойти определенное слово или фразу, я мог адаптировать мою систему и поймать это. Я был довольно пуленепробиваемым всего через пару недель.


источник
3
Это решение кажется лучшим. Проблема в том (или было на этом этапе), что я должен был решить ее во второй половине дня. Если будет достаточно времени, я либо воспользуюсь подходом Double MetaPhone, либо найму вас для этого. :-)
blueishgoldfish
Итак, я думаю, что половина людей перестанет играть в игру сейчас: D
Davor Ždralo
2

Если вы хотите сделать сопоставление эффективно, алгоритм Aho Corasick является довольно хорошим вариантом (я уверен, что вы можете найти реализацию Java, плавающую вокруг).

Конечно, вы, вероятно, захотите предварительно обработать отправку, чтобы заменить любые орфографические ошибки ('$' -> 's', '@' -> 'a', '| <' -> 'k' и т. Д.)

Дмитрий
источник
Именно то, что я искал, спасибо! Вот реализация Java: hkn.eecs.berkeley.edu/~dyoo/java
Реми Мелиссон,
0

Вместо загрузки в статическую строку [], используйте HashMap [] или какой-либо другой тип двоичного дерева (если вы хотите улучшить поиск), сделав строку вашим ключом в хэше. Разделите вашу строку пробелами и удалите знаки препинания. Затем вы можете запросить HashMap для каждого слова в вашей строке split; если hashmap возвращается с ненулевым значением, вы знаете, что у вас плохое слово.

Здесь не работает проблема Clbuttic, когда кто-то добавляет случайные символы вокруг плохого слова ex. bhassda

Suroot
источник
Я думаю, что последнее предостережение делает это решение практически бесполезным - нет способа распространить его на что-либо, кроме целых слов.
Это справедливое утверждение; но становится трудно уловить все возможные вещи, которые человеческий разум может придумать, чтобы избежать фильтра ненормативной лексики. Вы всегда можете создать огромное регулярное выражение с операторами OR, чтобы объединить все параметры, а затем сопоставить регулярное выражение с вводом. ИЛИ вы можете сделать выбор из базы данных с «полем плохого слова» из базы данных с RLIKE против ввода. Return указывает на плохое слово, а также возвращает плохое слово.
@ Сурот, нетрудно поймать любое слово или фразу с фонетическим соответствием, о чем говорит мой вопрос. Абсолютные совпадения никогда не будут работать или масштабироваться, но фонетическое сопоставление работает как можно ближе к 100% времени, как только вы можете его настроить.
-1

Использование фонетической системы - не единственное решение, но оно может быть самым простым, поскольку существует множество библиотек с открытым исходным кодом, которые делают подобные вещи.

Сложная часть всегда будет подходящей частью любого алгоритма, и звучит так, будто ваш матч довольно медленный и наивный. Вы не можете предполагать, что indexOf будет соответствовать правильно без какой-либо вспомогательной проверки.

Кроме того, вы закончите цикл по всей строке N раз, где N - количество слов в вашем черном списке. Предложения по использованию Set или HashMap определенно улучшат ситуацию.

В большинстве случаев алгоритм на основе линейного состояния является лучшим и быстрым. Я написал решение для Clean Speak, и он использует этот тип алгоритма с системой фонового сопоставления перед обработкой. Это было единственное решение, которое не усложнялось, когда в него вставлялась ненормативная лексика (если foo - ненормативная лексика, встраивание - это foosucker), и она могла сохранять высокий уровень производительности. Он также хорошо масштабируется для других языков без внедрения новых кодеков.

Наконец, предварительной обработки любой формы, как правило, следует избегать. В большинстве случаев вы можете делать то же самое линейным способом, когда обрабатываете каждый из символов в строке.

Конечно, я бы посоветовал взглянуть на другие решения в долгосрочной перспективе, потому что в большинстве приложений обработка пользовательского контента сложнее, чем просто фильтрация ненормативной лексики. Часто вы хотите также фильтровать личную информацию, такую ​​как электронные письма и номера социального страхования, а иногда и такие вещи, как URL-адреса. Кроме того, мы обнаружили, что большинству приложений нужна система модерирования и поиск контента. Это значительно увеличивает сложность.

Брайан Понтарелли
источник
-2

В таком случае вы хотите определить, какой из двух списков слов является меньшим. Скажем, ваш список «verboten» содержит 2000 слов, а максимальное количество пользователей - 500 слов. В этом случае вы будете перебирать список слов в представлении пользователя и искать их одно за другим в списке запрещенных слов и наоборот.

Другое изменение, которое я хотел бы сделать, это то, что вы не сохраняете список запрещенных слов в строке [] - если вы выполняете поиск в массиве, вы получаете O (n) поиск по слову в представлении пользователя. Это довольно плохо. Я бы попытался поместить структуру данных, которую вы просматриваете, в некий ассоциативный контейнер или древовидную структуру, которая имеет лучшую производительность поиска (log n вместо n). Сложность здесь заключается в том, что если вы поместите пользовательскую отправку в этот контейнер, вам придется отслеживать положение слова, чтобы вы могли либо восстановить ввод, либо обновить строку ввода, если у вас есть поисковый запрос.

Тимо Гюш
источник