Дополнить fa_matcher поиском совпадений с учетом опечаток
Issue #462
resolved
Дополнить fa_matcher поиском совпадений с учетом опечаток. Метрика расстояния между строкой и регулярным выражением - расстояние Дамерау-Левенштейна.
Comments (31)
-
reporter
-
reporter
- changed status to open
-
reporter
Получается, из всех полей после добавления ошибок, я смогу предсказать только значение поля 'is_match'(и то не всегда точно) + созданные мной поля для ошибок, я правильно понимаю?
-
repo owner
Вас, как минимум, интересуют нулевые элементы index_first и length - они показывают начало и длину совпадения. Остальные - совпадения с подмасками. full/is_match тоже надо. Вы же знаете какие ошибки и куда вы добавили. Вы можете завести свой тег для тестов, которые вы не хотите обрабатывать, если надо.
-
reporter
Как вы думаете, нормальным будет такой формат для опечаток? 'errors'=>array(qtype_preg_typo::INSERTION => array( 0 => array('pos' => 0, 'char' => 'a')) , 1 => array('pos' => 2, 'char' => 'b'))), qtype_preg_typo::SUBSTITUTION=> array( 0 => array('pos' => 1, 'char' => 'c'))))
-
repo owner
Вы хотите добавлять информацию об опечатках в тесты? Это нежелательно. Предпочтительно генерировать ее "на лету".
-
reporter
По умолчанию для отрицательных charset'ов и перехода по любому символу next_character генерирует chr(0), что соответствует пустой стоке ненулевой длины. Стоит ли вообще это как-то изменять или можно не заморачиваться?
-
reporter
Появились вопросы. Во-первых, почему ассерты выполняются не в eps-closure, а вперемешку с переходами, поглощающими символы. Во-вторых, опция mergeasserion почему-то не работает. По идее, для регулярки "^a$" автомат с смерженными ассертами должен представлять из себя один символьный переход, у которого mergedbefore каретка и mergedafter доллар, а генерируется так, как будто и не сливалось ничего(ps это исходная версия матчера, без моих изменений, так что это не из-за меня):
-
repo owner
Опция mergeasserion раобтает, вы не понимаете чего ждать. Вам бы почитать диплом Лепилкиной или статью с ней - на elibrary.ru должна быть наша общая статья в "Известиях ВолгГТУ".
У мержинга ассертов есть направления, т.к. в многострочном режиме они влияют на определенные символы (разрешая там только перевод строки). Крышка мержится только назад по движению автомата, доллар - только вперед. Поэтому в самом начале крышки остаются - и в самом конце доллары тоже. Но это не проблема - их легко пропустить. Попробуйте многострочный режим с крышкой в середине - или, проще, \b который мержится всегда.
-
reporter
Пусть regex ="^(a)(b)$" , str = "ba". В результате должно получиться совпадение с учетом 1 транспозиции. Какие совпадения должны получиться у подмасок? Ну по моему мнению, должно быть так, как будто на вход подается строка без транспозиции.
-
repo owner
А вы читали/смотрели как у Вилли, в TRE, совпадения с подмасками при учете опечаток обрабатываются? Я знаю что транспозиции там нет, но что насчет вставки и удаления символа?
-
reporter
Вот так. Для вставки символ не поглощается, для удаления и замены поглощается.
-
repo owner
Получается он работает как в совпадении - ведь удаление это символ которого нет в строке, но должен был бы быть. Значит и в случае транспозиции подмаски надо учитывать после. Рассмотрите ситуацию проще: уберите ^ и рассмотрите транспозицию на границе основного совпадения - так все будет яснее.
-
reporter
Regex = '(a|b|c|d)(c|d|e|f)' , str = 'db' . Для этого случая невозможна транспозиция, тк после поглощения 1го символа строки выиграет переход по символу 'd'(у него 0 ошибок), а для транспозиции нужно, чтобы прошел по 'b'(ну и это никак не поменять, тк приоритет по количеству ошибок - самый высокий после full'a). С одной стороны это является исключением, тк у транспозиции наивысший приоритет среди опечаток и мы ожидаем там именно ее. С другой - так ли нам нужно запариваться с этим, расстояние Д-Л все равно одинаковое для ожидаемого и для возвращенного матчером результата(в этом конкретно случае - 'dc' - 1 замена).
-
repo owner
Пока - если количество ошибок одинаковое - можно оставить так. Как корректно реализовать транспозицию в общем случае - вопрос интересный и это можно по идее сделать темой магистерской, если вы не хотите в магистратуре напрягаться и туда попадете - я боюсь, для этого понадобится попросту отложить конкуренцию на один шаг при некоторых конкретных условиях.
-
reporter
Оставить выделение цветом для нечеткого поиска? А картинка тогда будет генерироваться в специальной подсказке 'howtofixpic'
-
repo owner
Выделение цветом можно сохранить, но надо продумать его смысл. Зелеными должны быть только символы, которые окажутся в правильном ответе. Замененные и удаленные буквы должны быть красными. Места для вставки надо как-то пометить - тут надо думать ибо теоретически в регексе возможен другой символ. Возможно желтый знак вопрос или желтое многоточие (в юникоде есть многоточие как единый символ).
-
reporter
Ну я сделал полный учет транспозиций для случаев двусмысленности с помощью отложенных состояний. В результате, в худшем случае(regex = "abababab", str = "bababa" и большой допуск ошибок) для каждого шага автомата множество $currentstates будет чуть менее чем в 2 раза больше, чем было ранее.
-
reporter
Такой вопрос, для правильной работы нечеткого поиска мне нужно, чтобы для каждого шага автомата у каждого активного состояния была одинаковая длина. В текущей реализации, все ассерты симулируются не в eps_closure, а в главном цикле. В результате возникает отставание по длине от других состояний и выбор неверного состояния в узле схождения. Я перенес симуляцию таких переходов в eps_closure, однако добавились 2 фейлящихся теста(было 19, стало 21). Я наверное оставлю пока так, если останется время - буду разбираться. Обе эти ошибки связаны с частичным поиском, а в него я особо не вникал.
-
reporter
Мне там нужно обновить файл update.php, добавить пару полей в базу, на чем основывается выбор номер ревизии базы данных?
-
repo owner
Посмотрите внимательно на формат номера: там год-месяц-день и еще две цифры которые обычно нули на случай если несколько версий в один день делаешь.
-
reporter
Ну я тут решил немного поиграться, реализовать транспозиции как отдельный псевдопереход на 2 символа и посмотреть, выйдет ли быстрей, чем откладывание переходов на один шаг. В результате, версия с псевдопереходами работает чуть медленней, однако проще в реализации и убирает несколько костылей, необходимых для нормальной работы транспозиции на границах ассертов(например, в регулярке типа "a\Z[\nc]" и строки "\na"). И вот я думаю, что оставить как лучший вариант...
-
repo owner
Чуть медленнее это насколько?
В целом скорость обычно не очень критична. На количество проходимых тестовы никакого влияния не оказывает - на те проблемы, что были с транспозицией раньше?
-
reporter
ну например для тестов с 2-3 ошибками, новый метод тратит 24 минуты, старый 20. Ну по сути, те проблемы, что были с транспозициями, были решены еще раньше, просто в новом методе не нужно создавать костылей для их решения.
-
repo owner
Включая Regex = '(a|b|c|d)(c|d|e|f)' , str = 'db' ? Но если код более простой без костылей, то это обычно предпочтительнее при поддержке...
-
reporter
Да, включая.
-
repo owner
А по затратам памяти как?
Да, я надеюсь 24 минуты это не на одно совпадение регекса с 3 ошибками?
-
reporter
По памяти даже лучше, чем предыдущий метод. 24 минуты на около 5000 тестов.
-
repo owner
В таком разрезе времени некритично. Но всегда можно оставить второй вариант дополнительной именованной веткой, если вдруг захочется на на него переключиться...
-
reporter
Сделал обработку некорректных для нечеткого поиска регексов и залил на орг. + залил обновленный formal_langs
-
repo owner
- changed status to resolved
Сделано в релизе 3.2
- Log in to comment
Добавил issue, чтобы тут задавать возникающие вопросы.