1. Oleg Sychev Avatar Oleg Sychev
  2. POAS Moodle plugins
  3. Moodle Plugins
  4. Issues

НКА - большие конечные квантификаторы вызывают вылеты...

Issue #115 closed
Oleg Sychev repo owner created an issue

Originally reported on Google Code with ID 115

Реализовать в НКА метод Вилли по ограничению количества затрачиваемой памяти при хранении
совпадений с подмасками в процессе реализации НКА.

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

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

Reported by oasychev on 2012-04-07 04:34:12

Comments (26)

  1. Oleg Sychev reporter

    Reported by `oasychev` on 2012-04-07 10:49:35 - Labels added: Component-Preg - Labels removed: Component-Poasassignment

  2. Oleg Sychev reporter

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

    Reported by `oasychev` on 2012-04-14 20:29:05

  3. Valeriy Streltsov

    ``` Вот такая ситуация: с нулевого состояния просмотрятся переходы a, b, eps. Когда дело дойдет до eps, то при узле 1 уже будет стоять метка "len = 1", и этот путь с eps будет отброшен. Хотя именно он привел бы к полному совпадению.

    Можно было бы использовать eps-closure, но это выльется в рекурсивные вызовы - сначала просмотреть от 1 состояния, а затем от 0. Плюс ко всему там может быть не eps, а какой-нибудь \b... ```

    Reported by `vostreltsov` on 2012-04-17 17:03:14

    <hr>

  4. Oleg Sychev reporter

    ``` Ничего не могу так сказать. Какая строка? Откуда взялись приоритеты? Вроде я выше говорил про сравнение совпадений, достигнутых в данном состоянии автомата , а не про приоритеты...

    ```

    Reported by `oasychev` on 2012-04-19 15:19:29

  5. Valeriy Streltsov

    ``` Забыл написать, что выражение было (?:a|b)*abb$ Приоритеты здесь ни при чем, они просто так отображены (я вроде уже давно говорил, что их можно убрать из переходов). Порядок просмотра здесь вообще неважен. Строка, например, "aabb". При любом порядке просмотра переходов, идущих из начального состояния, путь, начинающийся с eps, отбросится при использовании тех правил (переход "a" захватит символ, а eps - нет). ```

    Reported by `vostreltsov` on 2012-04-19 16:24:36

  6. Valeriy Streltsov

    ``` Предлагаю следующую идею.

    В класс моего qtype_preg_nfa_processing_state добавить метод zero_length_closure($pos). Этот метод для заданной позиции $pos возвратит двумерный массив, каждый элемент этого массива будет содержать: [0] - индексы состояний, куда возможен переход без съедания символов (сюда войдут все ассерты, eps, обратные ссылки нулевой длины); [1] - массив номеров начавшихся подмасок для состояния [0]; [2] - массив номеров закончившихся подмасок для состояния [0].

    Этот метод будет вызываться: - вначале match() - начальных состояний будет несколько при наличии eps-переходов; - в конце каждого шага волны.

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

    P.S. Что делать с индексацией состояний? При построении автомата она неудобная, но при проходе без неё теперь не обойтись... Может, динамически создавать поле id в функции прохода автомата? Это будет просто, автомат уже целый и готовый, при построении их будет труднее присваивать. ```

    Reported by `vostreltsov` on 2012-04-22 18:08:19

  7. Valeriy Streltsov

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

    На счет генерации след. символа еще порисую примеры, там может быть не все так просто. ```

    Reported by `vostreltsov` on 2012-04-24 17:37:09

  8. Oleg Sychev reporter

    ``` Относительно рисунка в комментарии 3: у Вилли там больше эпсилонов вставляется при * - см. рис. у него в диссере, так что там проблемы не будет с одним вариантом на состояние автомата. В вашем рисунке проблема в том что эпсилон, обходящий * ведет в то же состояние, что и дуга съедающая символ, а у Вилли там лишние эпсилоны и лишние состояние. ```

    Reported by `oasychev` on 2012-04-25 06:10:21

  9. Oleg Sychev reporter

    ``` Это надо перевести в Fixed? ```

    Reported by `oasychev` on 2012-05-09 19:30:40

  11. Oleg Sychev reporter

    ``` Пишу как в одно из наиболее близких НКА - задач. Я не уверен насчет вашего последнего коммита. Количество символов, боюсь, надо определять в любом случае - на него же worse_than ориентируется... А вот сами символы генерировать не надо... ```

    Reported by `oasychev` on 2012-08-07 11:37:59

  12. Valeriy Streltsov

    ``` У меня для этого одна функция. Придется как-то хитро ее модифицировать чтоб next_character не вызывался ```

    Reported by `vostreltsov` on 2012-08-07 14:25:00

  13. Oleg Sychev reporter

    ``` А чего там хитрого? Параметр логический добавьте, да и все...

    next_character я надеюсь вызывается не по всей волне, а по одному пути? ```

    Reported by `oasychev` on 2012-08-09 16:34:19

  14. Valeriy Streltsov

    ``` По всей. Думаете, все пути запоминать - лучше? ```

    Reported by `vostreltsov` on 2012-08-10 07:50:11

  15. Oleg Sychev reporter

    ``` Зачем все пути запоминать? Можно генерировать при обратном проходе волны, выделяя лучший путь...

    Или это из-за ассертов? ```

    Reported by `oasychev` on 2012-08-11 15:44:04

  16. Oleg Sychev reporter

    ``` P.S. Удачи на море. Возьмите с собой маску для ныряния или там найдите - не пожалеете. В море - у трещин волнорезов например - с маской гораздо интереснее, чем на реке... ```

    Reported by `oasychev` on 2012-08-11 15:49:05

  17. Valeriy Streltsov

    ``` Добавил тест a{1,124} - это самое большое, что смог вынести php. Строка длиной 100 символов тоже максимум (так что не-экспоненциальность роста состояний на действительно большом автомате протестить не вышло - он тупо не строится) ```

    Reported by `vostreltsov` on 2012-09-03 20:27:34

  18. Oleg Sychev reporter

    ``` Вы имеете ввиду что preg_match не выдерживает больше чем a{1,124}?

    Может быть сделать специальный тег для кросс-тестинга чтобы проверять только по данным, без запуска через другой матчер? ```

    Reported by `oasychev` on 2012-09-04 12:22:29

  19. Valeriy Streltsov

    ``` Я про наш матчер, автомат больше 124 даже не строится - пхп кидает исключение. ```

    Reported by `vostreltsov` on 2012-09-05 07:15:28

  20. Oleg Sychev reporter

    ``` А в чем дело? Что за исключение и по какой причине оно возникает? ```

    Reported by `oasychev` on 2012-09-05 15:09:56

  21. Oleg Sychev reporter

    ``` Ну я бы пока не считал это Fixed пока не разберемся что за исключение, и может ли быть устранено.

    По идее в Вилли-НКА не должно быть проблем с большими квантификаторами, там все линейно. ```

    Reported by `oasychev` on 2012-09-26 16:54:55 - Status changed: `InProgress`

  22. Oleg Sychev reporter 
    Помимо багов, обнаруженных кросс-тестами, остается вопрос почему не строится автомат
в случае больших квантификаторов - что за исключением там возникает и почему...

    Reported by oasychev on 2013-01-06 19:51:30

  24. Valeriy Streltsov 
    Как-то оно само собой пофиксилось, наверное при реализации posix-совместимости.
a{1,1000} работал 2 секунды на строке длиной 1000 символов (там тормозит построение)
a{1,} работает моментально на такой же строке

    Reported by vostreltsov on 2013-05-19 18:24:44 - Status changed: Fixed

  25. Oleg Sychev reporter 
    Я думаю, для закрытия этого пункта надо добавить тест типа a{1,1000} (ну можно 400-500)
в кросс-тесты, может со специальным тегом для долгосрочного запуска.)

    Reported by oasychev on 2013-05-19 19:06:58

  26. Valeriy Streltsov 
    Исправил уже существующий тест {1,124} на {1,500} - обошлось без тега, время почти не
увеличилось.
Когда увеличил лимиты размеров при тестировании, ДКА где-то кинул исключение при матчинге.

    Reported by vostreltsov on 2013-05-27 07:36:06 - Status changed: Done

  27. Log in to comment
Assignee
Type
enhancement
Priority
minor
Status
closed
Component
–
Votes
0
Watchers
0
Jira: the preferred issue tracker for Bitbucket. Join the team!