поиск слова из словаря в данных

[gevaraweb]

arseniiv в сообщении #1286466 писал(а):

Вот те раз

Да, имеется в виду, за разговорами о компиляторах я вспомнил, как сейчас пишут , что код в js не уступает в скорости С++ (когда нет обращения к ДОМ). Поэтому цикл должен быть быстр. Ахо-Корасика не, не осилю, лень думать. Дерева тяжелая вещь.

-- 22.01.2018, 19:39 --

Dmitriy40 в сообщении #1286508 писал(а):

как это всё реально реализовано конкретно в PHP я не в курсе.

а в каком распространенном языке описываемый вами процесс точно будет происходить?

[Dmitriy40]

gevaraweb в сообщении #1286511 писал(а):

а в каком распространенном языке описываемый вами процесс точно будет происходить?

Да без понятия, я давно не слежу за всеми новинками в языкостроении.
Просто преобразование регэспа в конечный автомат и применение последнего - давным давно стандартная практика, это просто самый удобный и формальный способ обработки регэспа, любого. Собственно немалой доли популярности регэспы обязаны именно простоте и формальности перевода в КА (ИМХО), подчеркну, формальности перевода регэспа любой сложности в очень быстро выполняющийся код. И раз формально - это легко делает сам компилятор (или интерпретатор) языка. Просто потому что иначе - намного сложнее.
Потому и думаю что регэспы компилируются практически везде, в любых поддерживающих их языках.
Вы можете сами проверить свой компилятор: сравнить время выполнения двух осмысленных регэспов на одном и том же достаточно большом тексте, в первом регэспе забить 40 слов, во втором 400. Уж отличить линейное время от квадратичного несложно.

[gevaraweb]

Dmitriy40 в сообщении #1286524 писал(а):

Просто преобразование регэспа в конечный автомат и применение последнего - давным давно стандартная практика, это просто самый удобный и формальный способ обработки регэспа, любого. Собственно немалой доли популярности регэспы обязаны именно простоте и формальности перевода в КА (ИМХО), подчеркну, формальности перевода регэспа любой сложности в очень быстро выполняющийся код. И раз формально - это легко делает сам компилятор (или интерпретатор) языка. Просто потому что иначе - намного сложнее.
Потому и думаю что регэспы компилируются практически везде, в любых поддерживающих их языках.
Вы можете сами проверить свой компилятор: сравнить время выполнения двух осмысленных регэспов на одном и том же достаточно большом тексте, в первом регэспе забить 40 слов, во втором 400. Уж отличить линейное время от квадратичного несложно.

Я не возражаю против этого всего, пожалуйста. Это все хорошо. Но это не совсем то. Вы же заявили, что регэсп будет работать быстрее на наборе 4000 слов, начинающихся на одну букву, чем на наборе из 4000 слов, не начинающихся на одну букву. Или это тоже гипотеза? Раз уж

Dmitriy40 в сообщении #1286524 писал(а):

Да без понятия

[Dmitriy40]

gevaraweb в сообщении #1286537 писал(а):

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

Разве? Я вообще то заявлял что регэсп любой сложности будет работать быстрее тривиального сравнения списка подстрок.
Впрочем, процитированное утверждение тоже верно, т.к. для слов на одну букву будет лишь одно сравнение в начальном состоянии КА, для слов на 25 разных букв сравнений будет 25, что теоретически медленнее (но на практике незаметно).

Поймите же, регэспы тем и хороши, что абсолютно понятным образом (по формальным правилам) преобразуются в КА, код которого выполняется очень быстро, это вошло во все учебники уже лет 30 как. Нет никакого смысла (кроме как в учебных целях) обрабатывать регэспы как-то по другому. Тем более достаточно сложные, несводимые к десятку сравнений. И потому хоть я и не знаю как они реализованы в любом конкретном языке, но не вижу никаких причин для любого вменяемого человека (а авторов компиляторов/интерпретаторов распространённых языков априори считаем таковыми) реализовывать регэспы как-то иначе.

В общем я сказал всё что хотел. Хотите скорости - делайте Ахо-Корасик. Вполне вероятно что получите скорость лишь совсем капельку хуже огромного регэспа (за счёт лучшей оптимизированности последнего глубоко внутри кода библиотек).

[arseniiv]

gevaraweb в сообщении #1286511 писал(а):

Поэтому цикл должен быть быстр.

Цикл — О от размера словаря, умноженного на длину проверяемой строки, а Ахо—Корасик — О от длины строки. Впрочем, чего я буду вас уговаривать.

gevaraweb в сообщении #1286511 писал(а):

Ахо-Корасика не, не осилю, лень думать. Дерева тяжелая вещь.

А вот проверки, конечно, дело в любом случае. (Хотя и их надо делать грамотно… Нельзя просто взять сколько-то времён и найти среднее; и даже вычисление дисперсии не спасёт от неточности измерения самих этих времён.)

[gevaraweb]

Dmitriy40 в сообщении #1286548 писал(а):

Разве?

Дык, вот пожалуйста

gevaraweb в сообщении #1286285 писал(а):

регулярки ... никак они не могут работать быстрее обычного поиска вхождения подстроки в строку.

Dmitriy40 в сообщении #1286314 писал(а):

Не утерплю и покажу пример когда могут.
Предварительно сделаем пару правдоподобных предположений: все искомые слова начинаются на одну и ту же букву; используется тривиальный алгоритм сравнения слов (подстрок).
Итак, при тривиальном алгоритме чтобы проверить наличие слова в тексте надо для каждого символа текста сравнить две подстроки: вырезанную с текущего символа из текста и каждое из 4000 искомых слов. А для этого будет сделано 4000 сравнений текущего символа текста и первой буквы каждого из слов. Несмотря на то что они все одинаковые! Общая сложность не меньше чем $4000 \cdot L$ ($L$ - длина текста). Длину слов не учитываем - считаем её намного меньшей длины всего текста.
КА же не будет делать 4000 сравнений первой буквы всех слов с текущим символом текста, он выполнит ровно 1 сравнение текущего символа текста с одинаковой первой буквой всех слов.

[Dmitriy40]

Хорошо, предложу ещё один метод, попроще КА и побыстрее сравнения списка подстрок.
Постулат: ищем только русские слова, из алфавита 31 буквы (е и ё можно безопасно объединить в одну, ну и знаки ъ и ь тоже) плюс пустой заполнитель.
Для представления символа алфавита достаточно 5 битов, для представления 5-ти первых букв слова достаточно 25 битов.
Заводим массив из $2^{25}$ битов, это всего 4 мегабайта, биты устанавливаем в 1 если эти 5 букв являются началом какого-то слова в словаре искомых (здесь и нужен пустой заполнитель для учёта слов короче пяти букв).
После этого для каждого символа входного потока проверяем последние полученные 5 символов входного потока как 25-ти битный указатель в массив и если там нулевой бит - в этой позиции (точнее конечно 5 символов назад) искомых слов не начинается. Сложность линейная по размеру текста и константная по размеру словаря искомых строк.
Конечно если бит равен единице, то надо проверять дальше, но и это можно оптимизировать, например задать массив указателей на списки слов для любых комбинаций первых трёх символов, это всего $2^{15}$ указателей, 256 килобайт обычно (ну или из 4-х букв, это $2^{20}$ указателей, обычно 4 мегабайта), в каждом таком списке слов будет уже далеко не 4000, а всего с десяток-два, их проверить уже быстро. Можно конечно и вообще отказаться от битового массива и проверять по три символа прямо по массиву указателей, но это будет немного медленнее из-за большего количества ложных срабатываний, приводящих к проверке списка слов (хоть он и на два порядка короче, но всё же).
Да, по видимому от пустого заполнителя можно отказаться и знаки ъ и ь не объединять, все короткие слова (менее 3-х или 4-х букв) всё равно попадут в списки.
Фактически это простейший вариант хэштаблиц.

-- 22.01.2018, 20:43 --

gevaraweb в сообщении #1286560 писал(а):

Дык, вот пожалуйста

Наверное я отупел спросонья, но не вижу в моих словах сравнений двух регэспов, вижу только сравнение регэспа и тривиального сравнения подстрок.

[gevaraweb]

Пардон, вы меня сбили этим

Dmitriy40 в сообщении #1286524 писал(а):

сравнить время выполнения двух осмысленных регэспов на одном и том же достаточно большом тексте

Поправлю вопрос: Я не возражаю против этого всего, пожалуйста. Это все хорошо. Но это не совсем то. Вы же заявили, что регэсп будет работать быстрее на наборе 4000 слов, начинающихся на одну букву, чем простой поиск. Или это тоже гипотеза?

[Dmitriy40]

gevaraweb в сообщении #1286579 писал(а):

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

Тут есть тонкость что понимать под простым поиском. Я не зря выше оговаривался что сравниваю с тривиальным поиском, реализуемым как посимвольное сравнение подстрок. С ним да, регэсп будет быстрее, потому что для каждого символа будет не 4000 сравнений, а лишь 33 или менее.
Вот если список искомых слов организовать в дерево, то выигрыш регэспа (всё равно) будет, но уже за счёт других механизмов, за счёт более простого кода. Если конечно слова хоть как-то пересекаются (имеют одинаковые подстроки), если не пересекаются, то и дерево и регэсп вырождаются в практически одинаковый код.

[gevaraweb]

Dmitriy40 в сообщении #1286587 писал(а):

Тут есть тонкость что понимать под простым поиском. Я не зря выше оговаривался что сравниваю с тривиальным поиском, реализуемым как посимвольное сравнение подстрок.

Это да, но я то такой оговорки не делал Прятал туза в рукаве - обычный поиск в ЯВУ вполне может оказаться оптимизированным ) Хотя думаю, что и тривиальный поиск не уступит регэксу для этой задачи, но нужно проверить.

[Dmitriy40]

Как бы ни был оптимизирован поиск одного слова, он в любом случае линеен относительно входного текста (т.е. $O(L)$), а Вам придётся повторить его 4000 раз. Да, в самом лучшем случае (для списков некоторых очень специальных слов!) можно общее количество сравнений уменьшить с $4000L$ до $4000L/k$ ($k$ длина искомых слов), что собственно алгоритм Бойера-Мура и делает, но это эффективно для длинных искомых слов.
Поиск Ахо-Корасик (как собственно и КА распознающий этот же список слов) производит не более 33 сравнений на каждый символ входного текста, т.е. всего не более $33L$ (а очень часто - сильно меньше).
Средний случай я оценить не берусь (я не Кнут), а вот худший можно. Для поиска худшим будет $4000L$ сравнений, для КА $33L$. Комментарии излишни. Но основная беда в том, что для поиска слов худших случаев относительно больше чем для КА (для реальных текстов и списков слов). Ну а достаточно длинных слов, чтобы оправдать поиск, в языке просто нет (ведь при этом и КА тоже будет сильно меньше 33 сравнений на каждую букву).
Потому как бы ни был оптимизирован поиск одного слова, повторение его 4000 раз всегда медленнее КА распознающего эти же 4000 слов. И сравниться они могут лишь для скажем десятка искомых слов (ну или порядка сотни, но очень-очень специальных).

[grizzly]

Dmitriy40 в сообщении #1286625 писал(а):

Как бы ни был оптимизирован поиск одного слова, он в любом случае линеен относительно входного текста (т.е. $O(L)$)

А что если отсортировать слова текста в порядке возрастания и затем в этом массиве искать отсортированные же слова словаря? Так мы пройдём по тексту только один раз (или по словарю, смотря что длиннее). Для сортировки можно брать какой-нибудь Quicksort, который на естественных текстах должен быть достаточно быстрым. И вообще в практических целях можно ограничиться первыми несколькими буквами слов текста и словаря (это уже зависит от целей ТС).

[arseniiv]

В общем случае текст — это одно длинное неподелённое «слово», и проверяется, нет ли у него данных подслов. К формулировке gevaraweb о матфильтре это тоже подходит (или эффективность будет совсем никакая).

[Dmitriy40]

grizzly
Тоже неплохая идея, да.
Но мне кажется для длинных текстов она будет невыгодной, ведь если не ошибаюсь сложность сортировки $O(n \log n)$, сложность же Ахо-Корасика (да и по видимому любого КА распознающего регэсп) $O(n)$ (если отвлечься от зависимости по размеру словаря). Т.е. для текста из сотен и тысяч слов сложность сортировки съест выигрыш в константе.
А для коротких текстов кстати можно побить текст на слова и каждое из них (даже без сортировки и исключение дублей) проверить на вхождение в словарь, который для этого преобразовать в префиксное дерево (собственно это снова фактически КА). Кажется получим ту же зависимость $O(n \log m)$ (от длины текста или количества слов, без разницы, $n$ проходов по дереву глубиной $m$), что и для регэспа. (Оценки не худшие, в среднем!)
Ограничение несколькими первыми буквами я уже тоже предложил выше, использовать первые буквы проверяемого слова как индекс в массиве указателей на списки искомых слов на эти буквы. Если искомые слова хорошо размазаны по первым буквам, то это выгодно. Фактически это простейшая хэштаблица.

В общем вариантов решения много. И для не слишком больших текстов они выгодны по разному. Ну а в пределе (для больших текстов и списков искомых слов) все более-менее оптимальные варианты сводятся к примерно одинаковому КА, возможно по разному закодированному, ИМХО.

-- 23.01.2018, 01:48 --

Вообще, чтобы выбрать конкретный алгоритм, надо бы точно знать какие структуры данных и какие операции над ними поддерживает сам используемый язык. А то может уже мы изобретаем велосипед, а в языке реализован один из методов проверки вхождения слова в список - и тогда останется лишь поделить текст на слова и прогнать их по списку искомых слов (или наоборот, смотря кого меньше). Или регэспы хорошо встроены в язык и работают быстро (на что я надеюсь) и тогда изобретать что-то ещё нет смысла.

[realeugene]

gevaraweb в сообщении #1286080 писал(а):

Задача такая - обнаружить, присутствует ли слова из ненормативной лексики в указанном тексте. Соответственно, имеется словарь нехороших слов (~4000).

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