Проблемы с производительностью Regex - Фильтр ненормативной лексики

Question

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

Прямо сейчас вот пример строки с регулярным выражением, это отфильтровывает 2 слова,foo и bar.

(?i)f(?>[.,;:*`'^+~\\/#|]*+|.)o(?>[.,;:*`'^+~\\/#|]*+|.)o|b(?>[.,;:*`'^+~\\/#|]*+|.)a(?>[.,;:*`'^+~\\/#|]*+|.)r

По сути, я игнорирую регистр, затем помещаю (?>[.,;:*'^+~\\/#|]*+|.) между каждой буквой проклятого слова и | между каждым полным регулярным словом regex.

Работает, но довольно медленно.

Если в фильтре 6 слов, он отфильтрует довольно длинную строку (500 символов) за 939 548 наносекунд.Когда у меня 12, оно примерно удваивается.

Итак, примерно 1 мс на 6 ругательств с этим.Но мой фильтр будет иметь сотни (400 или около того).Для расчета этой длинной строки потребуется около 66 мс.

Это сервер чата, который я создаю, и если у меня много пользователей (скажем, 5000) и 1 из 5 общаются в чатеза 1 секунду (1000 сообщений чата) мне нужно отфильтровать сообщение примерно за 1 мс.

Требуется ли слишком много регулярных выражений?Будет ли быстрее сделать свой собственный специализированный тип фильтра вручную?Есть ли способы оптимизировать это?

Я прекомпилирую регулярное выражение.

Если вы хотите увидеть эффект этого регулярного выражения http://regexr.com? 30454

Обновление: Еще одна вещь, которую я мог бы сделать, - это фильтровать сообщения чата на стороне клиента в ActionScript.

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

Answer 1

Чтобы ответить на ваш вопрос «я слишком много задаю регулярных выражений?» - Да

Большую часть двух лет я потратил на работу над фильтром ненормативной лексики с использованием регулярных выражений и, наконец, сдался. За это время я попробовал все эти вещи:

• Pre-компилирования
• Классы символов (знаки препинания, пробелы и т. Д.)
• Группы без захвата (упомянутые выше и могут значительно уменьшить память и увеличить скорость)
• Объединение похожих регулярных выражений (также упоминалось выше)
• Обрезка пробелов (str.trim ())
• Обработка регистра (str.toLowerCase ())
• Упаковка и распаковка пробелов (преобразование нескольких соседних пробелов в один пробел и наоборот)
• Написание собственного пользовательского движка регулярных выражений (крайне не рекомендуется, поскольку он сложен и не масштабируется)

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

Мы обнаружили, что мы также смогли выполнить несколько многопоточных и других оптимизаций после того, как перестали использовать регулярные выражения и перешли от обработки 600-700 сообщений в секунду до 10000+ сообщений в секунду.

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

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

Answer 2

Можете ли вы использовать любой из встроенных классов символов, например,

 \bf\W?o\W?o\W?\b

для обнаружения «foo» с любыми не-буквами между буквами, но не с «food» или «snafoo»(sic)

Однако слабым местом этого является то, что "_" считается символом слова: - (

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

Обновление :Думал об этом после того, как я пошел домой, но Qtax попал туда первым (см. Другой ответ) - попробуйте сначала удалить все знаки препинания, а затем запустите простые текстовые шаблоны на тексте. Это должно сделать шаблоны слов намного проще ибыстрее, особенно когда вам нужно проверить много слов.

Наконец, обратите внимание, что в [] вам не нужно экранировать специальные символы регулярного выражения, поэтому:

[.,;:*`'^+~\\/#|]

- этоОК (обратная косая черта все еще нуждается в экранировании)

Answer 3

Когда у вас много слов, сгруппируйте их по первым равным символам, и вы увидите, что для добавленных слов вы увидите увеличение менее чем линейное время.

Я имею в виду, что если у вас есть два слова "foobar" и "fook"msgstr "сделать регулярное выражение, сформированное как foo(?:bar|k).

Использование групп без обратного отслеживания вместо захвата может повысить производительность.Т.е. замените (?:...) на (?>...).

Еще одним предложением может быть сначала просто удалить все знаки препинания в строке, а затем применить более простое выражение.

Кроме того, если вы можетепопробуйте применить выражение к более длинным строкам.Поскольку это, вероятно, будет быстрее, чем делать одно сообщение за раз.Возможно объединить несколько сообщений для первой проверки.

Answer 4

можно попробовать заменить все

[.,;:*`'^+~\\/#|]+

с пустыми строками и затем просто проверьте

\b(foo|bar)\b

UPDATE:

если вы более параноидальны в отношении пробелов f( *+)o\1o|b( *+)a\2r

или больше параноиков в целом f([^o]?)o\1o|b([^a]?)a\2r