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

[arseniiv]

Нет, зачем, допустим, что реализация поиска любой строки словаря в данной на вход строке достаточно оптимальна, деревом там или чем. Регэкспы тоже в современном мире умеют компилироваться в подобное представление и матчиться быстрее. Вся разница будет в выразительности: список слов будет эквивалентен регэкспу слово1|слово2|…, и по занимаемому скомпилированным представлением месту, если предположить отсутствие оптимизаций при компиляции регэкспа, тоже.

-- Вс янв 21, 2018 16:19:59 --

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

Задача для веб, поэтому язык будет интерпретируемым.

Какая-то странная связь.

[gevaraweb]

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

список слов будет эквивалентен регэкспу слово1|слово2|…, и

ну это по идее тот же внутренний цикл из 4000 витков, с оптимизациями )

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

Какая-то странная связь.

тут вы правы, по привычке наверно так называю )

[arseniiv]

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

ну это по идее тот же внутренний цикл из 4000 витков, с оптимизациями )

Так я ведь не зря написал «компиляция». В результате уже не будет цикла, будет недетерминированный конечный автомат. А для конструкции слово1|слово2|… — даже детерминированный.

-- Вс янв 21, 2018 17:23:19 --

А, ну не, всё ещё не детерминированный — в самом начале будет ε-переход — но почти что детерминированный, особенно если компиляция неглупая и выдаст не такой наивный результат.

-- Вс янв 21, 2018 17:25:35 --

Обычно НКА не превращают в ДКА, потому что размер может возрасти экспоненциально. Но некоторые хорошие случаи, в принципе, возможно определять.

[gevaraweb]

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

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

А, понятно. Всегда я был слаб в вопросах компилятора. Не уверен, что это есть, например, в пхп. Я больше думаю об оптимизации до компиляции )

[arseniiv]

Есть. Компилируются и хранятся в кэше: https://stackoverflow.com/questions/209906/compile-regex-in-php.

-- Вс янв 21, 2018 21:15:12 --

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

Всегда я был слаб в вопросах компилятора.

Компиляция регэкспов не относится к компиляции самого кода, она выполняется в рантайме.

[gevaraweb]

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

Есть. Компилируются и хранятся в кэше

Не силен в англ, но мне кажется, что там говорят о другой задаче. Я понял, что им нужно одну, сравнительно небольшую регулярку применить много раз подряд на разных текстах. Тогда есть смысл ее скомпилировать. У нас же одна развесистая (я так понимаю длинная? регулярка вида слово1|слово2|…, и п ) применяется на тексте по мере необходимости.

И еще все равно не укладывается у меня в голове, что скомпилированная регулярка из 4000 слагаемых вдруг сработает на тексте намного быстрее, чем 4000-ый цикл с простой проверкой вхождения слова в текст.

[arseniiv]

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

У нас же одна развесистая (я так понимаю длинная? регулярка вида слово1|слово2|…, и п ) применяется на тексте по мере необходимости.

Длинная; применяется ко многим текстам одна и та же по разу к каждому тексту, потому её оптимизированную форму можно где-то сохранить (если на PHP можно написать сервер, работающий вечно, а не скрипт, вызывающийся каждый раз при отправке поста в свежем контексте — тогда компиляция будет, конечно, каждый раз заново, и толку ноль).

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

И еще все равно не укладывается у меня в голове, что скомпилированная регулярка из 4000 слагаемых вдруг сработает на тексте намного быстрее, чем 4000-ый цикл с простой проверкой вхождения слова в текст.

Это вопрос не укладывания в голове, а эксперимента. Действительно, может случиться, что для некоторых (и даже многих) реализаций цикл будет быстрее. Просто в идеале он быстрее не будет, а где к этому идеалу уже приблизились достаточно — гадать не буду, PHP у меня не стоит.

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

[gevaraweb]

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

Тут разве не проще составить развесистый регэксп и скомпилировать?

А это, значит, тоже была гипотеза? Я то думал - императив!

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

Это вопрос не укладывания в голове, а эксперимента. Действительно, может случиться, что для некоторых (и даже многих) реализаций цикл будет быстрее. Просто в идеале он быстрее не будет, а где к этому идеалу уже приблизились достаточно — гадать не буду, PHP у меня не стоит.

Не соглашусь, тут как раз достаточно простого рассуждения. Ведь что такое регулярка? Удобные правила поиска подстроки в строке. Поэтому ну никак они не могут работать быстрее обычного поиска вхождения подстроки в строку. Да, там есть оптимизация. Но она для особых случаев вызовов. Эта "не та" оптимизация. Поэтому цикл будет работать быстрее (при прочих равных условиях).

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

а не скрипт, вызывающийся каждый раз при отправке поста в свежем контексте

Да, про такой именно скрипт и речь.

[arseniiv]

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

А это, значит, тоже была гипотеза? Я то думал - императив!

Скажем, нечто среднее. Я предполагал, что лучше регэксп, но теперь видно, что, во-первых, возможно, не всегда это будет быстрее выполняться (я сначала представил несколько лучший вид конечного автомата, но потом вспомнил), да и premature optimization.

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

Да, про такой именно скрипт и речь.

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

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

Не соглашусь, тут как достаточно простого рассуждения. Ведь что такое регулярка? Удобные правила поиска подстроки в строке. Поэтому ну никак они не могут работать быстрее обычного поиска строки.

Так вон для обсуждаемого изначально Ахо—Корасик возможен поиск без перебора каждой из искомых строк сразу всех из них. Если только найти хороший эквивалентный ДКА, будет всё ровно так же. Просто его, скорее всего, при компиляции искать не будут.

[Dmitriy40]

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

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

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

Аналогично и для второй буквы, тривиальный поиск проверит все 4000 слов, КА проверит максимум 33 буквы (или даже меньше если некоторых комбинаций первых двух букв в искомых словах не встречается). И так далее для всех остальных букв.

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

[gevaraweb]

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

Не утерплю и покажу пример когда могут.

Еще один не утерпел . Не смогут опять.

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

все искомые слова начинаются на одну и ту же букву; используется тривиальный алгоритм сравнения слов (подстрок).

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

[wrest]

gevaraweb
Как-то 4000 слов для антимата многовато...
Ну вот допустим приняли слово "нести" как нецензурное.
У вас в словаре прям все его словоформы типа "занес, внес, вынес, пронес, перенес, занести, внести, перенести, занесенный, перенесенный" ну и так далее? Или именно "уникальных" 4 тысячи? И как вы хотите обрабатывать разделители - в "шлюз, а не сетевое" должно матчиться "занесет"?

[gevaraweb]

wrest в сообщении #1286398 писал(а):

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

Вроде да. Посмотрел словарь (бр...), вроде его можно сократить. Там много слов типа слон, слонище, слоноподобный, и пр. Можно удалить словоформы и оставить только слон. Может, можно до 2000 довести. Или другой словарик поискать...

Хотел не заморачиваться, и просто удалять все пробелы и небуквенные знаки. В принципе, arseniiv меня почти убедил, что цикл 4000 не так уж и много. Можно на js написать скриптик попробовать. Слова в словаре думаю может еще зашифровать простым шифром, хоть Цезарем. Чтоб глаза не мозолили.

[arseniiv]

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

В принципе, arseniiv меня почти убедил, что цикл 4000 не так уж и много.

Вот те раз. Ну если вы так хотите список слов, ради Диэдра, сделайте Ахо—Корасик, это ведь не какой-то хитрый алгоритм умножения матриц со сложностью $o(n^3)$, там всё прозрачнее и писать меньше.

[Dmitriy40]

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

Вы не сможете предупредить регэксп, что все слова начинаются на одну букву. Нет там такого АПИ или ИИ.

Да и не нужно, при попытке использовать регэсп он при выполнении превратится в автомат распознающий данный регэсп (просто потому что это стандартный и формальный подход, работающий для любых регэспов) и если при преобразовании регэспа в состояния автомата окажется что первая буква всегда одна и та же - то и в автомате будет ровно одна проверка входного символа на эту самую букву. Одна, а не 4000. Ну хотя бы потому что даже поставив 4000 одинаковых проверок с переходом в одно и то же состояние их все грохнет оптимизатор и оставит ровно одну. Но на самом деле до оптимизатора даже не дойдёт, ещё на стадии построения автомата чисто формально они все срежутся до одной.
Даже в худшем случае, если искомые слова могут начинаться на любую букву русского алфавита, даже в этом случае каждый символ входного потока будет проверяться лишь на 33 (даже меньше) варианта, а не 4000.
И снова повторю, оптимизация поиска слов (например использование алгоритма Ахо-Корасик как выше рекомендовано) приведёт точно к такому же результату, будет построен фактически аналогичный автомат. Просто для Ахо-Корасика Вы наверняка должны будете сами это делать, а с регэспами всё сделают за вас (надеюсь).
Хотя, как это всё реально реализовано конкретно в PHP я не в курсе.