Реализовать систему, которая для документа сможет проверить, подходит ли он под правила вида: “слово1 и (слово2 или слово3) и не слово4”, например: “центр и (Екатеринбург или Екб) и не Москва”. Каждое “слово” тут - это операция проверки вхождения слова в документ, и/или/не - логические операторы. В примере под указанные критерии подойдет документ, в котором встречаются слова “центр”, одно из слов “Екатеринбург” или “Екб” и не встречается слово “Москва”. Правило может быть любой сложности, скобки могут быть вложенными.
- Правило (логическое выражение) приводится к обратной польской записи.
- Текст документа преобразуется в список нормализованных, с помощью библиотеки pymorphy2, слов.
- Вычисляется значение логического выражения для списка нормализованных слов.
- В случае соответствия текста заданному правилу, возвращается True.
- Парсинг логического выражения:
Сложность: O(n), где n - длина логического выражения. - Нормализация текста:
Сложность: O(d * k), где d - средняя длина слова, k - общее количество слов в тексте. - Вычисление логического выражения:
Сложность: O(n), где n - количество токенов в логическом выражении.
Общая алгоритмическая сложность будет максимум из сложностей этих этапов. Если самым ресурсоемким этапом является нормализация текста, то общая сложность будет O(d * k), где d - средняя длина слова, k - общее количество слов в тексте.