Поправим. Он путается когда несколько дат в запросе. Можно написать эвристики выбора самой правдоподобной или же требовать задавать другие даты в кавычках.
проект play+maven module+gae module. Были странные ошибки с тем что play не понимал как собрать war. Но после переустановки все начало работать правильно и просто.
А да согласен, все что говорю относится к привязке к началу. Но и DFA будет не O(N) если мы делаем сдвиг на символ и матчим снова… Правда как правило все двигаются по границам токенов что существенно оптимизирует процесс.
В Trie откатов не происходит(мы не ищем строку а проверяем на соответствие т.е. патерн ^...$). Мой пример превращается в такое дерево.
ad
--asddsa
--sasd
jav
--ajava
--ggaaa
--vva
При обработке строки asddsa. Мы проверим первый символ первого патерна(второй не подходит так как начинается на j), второй символ на этом патерн перестанет работать т.е. как альтернатив нет. и будет всего 2 проверки символов.
Т.е. в такой оптимизации никаких откатов нет так же как и альтернатив.
По моему все же ДНА. Определение ДНА на каждом шаге существует только один возможный переход — детерминированность. В случае Trie существует только один путь по дереву для любой строки или он отсутствует вообще. Т.е. это DFA. И затраты на каждый символ будут равны ветвистости дерева.
Насчет памяти не знаю, так как Pattern сериализируеться в строку. Словарь городов(около 15000) уменьшился в 1.5 раза, в сравнении с простой склейкой.
Скорость работы в сравнении с обычным регекспом в 100 раз быстрее, на корпусе нтмл страниц.
Моя структура дынных временная, так как все что она делает это создает новую строку, которая используется в дальнейших регулярных выражениях — сама структура выбрасывается и далее все зависит от движка RE.
Оптимальное в данном случае по скорости это массив размером 32(кол букв), где много пустых ветвей — вообще надо отказаться от указателей и перейти к индексам в массиве везде где только можно — но это уже не ява а С++ какой то ). Надо что то использовать из специальных быстрых коллекций типа bak.pcj.
В общем если делать просто поиск слов по словарям то лучше хеш, правда возникает вопрос границ если есть фразы длины 4,5 в словаре. Это структура удобна если пишется много регулярок из них собираются сложные и в автомат сложно вставить свой оператор.
Я уже не так уверен, но вопрос все равно спорный. Тут можно посмореть сравнение трех этих структур данных Trie(префиксная оптимизация), Hash, Tree.
По скорости построения, Trie самая быстрая. По скорости считывания для очень больших данных выигрывает Hash, но идеальный(когда мало коллизий) и слова очень разные — мало общих префиксов, Tree всегда хуже Trie в поиске.
Я все еще остаюсь при своем мнении Trie для регекспов самый быстрый способ если работать с обычным тестом где много общий префиксов. Но это мнение ИМХО, так как это не всегда верно.
А это вроде как и есть DFA полученный из NFA. Понятие «Префиксная оптимизация» я придумал, возможно статью стоило назвать получение DFA в частном случае.
Нет, как раз в этом случае скорость все равно будет больше у такой регулярки.
Увы теоретически у меня не получается объяснить почему, т.е. я вроде все аргументировал, но мне не верят ) Еще последние два аргумента:
в википедии нет другого алгоритма поиска множества строк в тексте кроме en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm — значит он оптимальный на сегодняшний день, а это почти в точности что я описал.
Просто сделайте тест. Когда теория становится слишком сложной можно просто провести эксперимент.
Да, именно. Но насчет разбора это не совсем так. Парсер из строки в регулярное выражение ничего из вышеописанного не сделает — он не оптимизирует, он просто строит автомат как есть. Я же подготавливаю для него строку которая описывает более быстрый автомат.
Да, ДКА это сила, но у него другая проблема — его размеры — при компиляции он разворачивается в огромную структуру данных. Как всегда дилемма процессорного времени и памяти…
1. добавление имеет сложность количество символов добавляемого слова и проверок происходит столько же. Мы читаем символы слова только один раз и сразу определяем куда класть.
2. Мы движемся по строке, это же автомат и сравниваем каждый раз по символу, до первого несовпадения.
Это кардинально отличается от поиска по дереву где:
а. на каждом шаге сравниваются две строки.
б. останов происходит когда доходим до узла дерева что всегда равно logN.
RE 1. добавление новой строки, вроде как, имеет сложность не меньше чем C*N, где N — размер слова, что в любом медленнее чем добавление в сбалансированное дерево (logN).
Скорость генерация регулярного выражения не имеет значения, так как происходит один раз для словаря, это как время компиляции. В случае же бинарного дерева, имеет значение, так как производится каждый раз при сравнении слова с паттерном.
RE 2. количество проверок для бинарного дерева logN, это точно, но ведь у вас же тоже строки должны сравниваться тем же regexp'ом на равенство. Это ведь будет не меньше чем N.
Каждая проверка в моем случае это сравнении одного символа, в случае бинарного дерева это сравнения целых строк. Сравнений может быть меньше чем N, например если первый символ не подходит для словаря то произойдет всего одна символьная проверка, в дереве же logN строковых сравнений- что значительно более трудоемко.
ad
--asddsa
--sasd
jav
--ajava
--ggaaa
--vva
При обработке строки asddsa. Мы проверим первый символ первого патерна(второй не подходит так как начинается на j), второй символ на этом патерн перестанет работать т.е. как альтернатив нет. и будет всего 2 проверки символов.
Т.е. в такой оптимизации никаких откатов нет так же как и альтернатив.
Скорость работы в сравнении с обычным регекспом в 100 раз быстрее, на корпусе нтмл страниц.
Моя структура дынных временная, так как все что она делает это создает новую строку, которая используется в дальнейших регулярных выражениях — сама структура выбрасывается и далее все зависит от движка RE.
Оптимальное в данном случае по скорости это массив размером 32(кол букв), где много пустых ветвей — вообще надо отказаться от указателей и перейти к индексам в массиве везде где только можно — но это уже не ява а С++ какой то ). Надо что то использовать из специальных быстрых коллекций типа bak.pcj.
В общем если делать просто поиск слов по словарям то лучше хеш, правда возникает вопрос границ если есть фразы длины 4,5 в словаре. Это структура удобна если пишется много регулярок из них собираются сложные и в автомат сложно вставить свой оператор.
По скорости построения, Trie самая быстрая. По скорости считывания для очень больших данных выигрывает Hash, но идеальный(когда мало коллизий) и слова очень разные — мало общих префиксов, Tree всегда хуже Trie в поиске.
Я все еще остаюсь при своем мнении Trie для регекспов самый быстрый способ если работать с обычным тестом где много общий префиксов. Но это мнение ИМХО, так как это не всегда верно.
Язык программирования указал в тегах и заголовке.
Увы теоретически у меня не получается объяснить почему, т.е. я вроде все аргументировал, но мне не верят ) Еще последние два аргумента:
в википедии нет другого алгоритма поиска множества строк в тексте кроме en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm — значит он оптимальный на сегодняшний день, а это почти в точности что я описал.
Просто сделайте тест. Когда теория становится слишком сложной можно просто провести эксперимент.
2. Мы движемся по строке, это же автомат и сравниваем каждый раз по символу, до первого несовпадения.
Это кардинально отличается от поиска по дереву где:
а. на каждом шаге сравниваются две строки.
б. останов происходит когда доходим до узла дерева что всегда равно logN.
Скорость генерация регулярного выражения не имеет значения, так как происходит один раз для словаря, это как время компиляции. В случае же бинарного дерева, имеет значение, так как производится каждый раз при сравнении слова с паттерном.
RE 2. количество проверок для бинарного дерева logN, это точно, но ведь у вас же тоже строки должны сравниваться тем же regexp'ом на равенство. Это ведь будет не меньше чем N.
Каждая проверка в моем случае это сравнении одного символа, в случае бинарного дерева это сравнения целых строк. Сравнений может быть меньше чем N, например если первый символ не подходит для словаря то произойдет всего одна символьная проверка, в дереве же logN строковых сравнений- что значительно более трудоемко.