Что есть из готового ((возможно из boost) функторов) для частичного лексикографического поиска в ассоциативных контейнерах хранящих строки?
Например по wildcard.
Допустим есть массив со строками:
[1]aa
[2]aabcd
[3]aabde
[4]cdbe
Задана маска *ab*
Результат два итератора [3],[4]

Здравствуйте, nen777w, Вы писали:

N>Что есть из готового ((возможно из boost) функторов) для частичного лексикографического поиска в ассоциативных контейнерах хранящих строки?

Что такое "частичный лексикографический поиск"?
"Лексикографический" предполагает упорядоченность — ну так ассоциативный контейнер (std::set?) и без того упорядочен.

Вопрос в том, чтобы сделать поиск более эффективно, чем линейно пробежаться и проверить каждый элемент на совпадение с маской?
Вынужден огорчить: в общем случае углы срезать не получится.
Всё, что мы можем сделать — это взять префикс из маски (скажем, для "abc*def*ghi" — префикс будет "abc") и ограничить область забега диапазоном ["abc"-"abd")

Или вопрос в том, что маска известна заранее, и хочется построить контейнер, который
— отделяет подходящие строки от неподходящих (ну это банально: делаем два контейнера, проверяем каждую свежедобавляемую строку и кладём её в соответствующий)
— упорядочивает слова по маске (т.е. для *a* слова bAr и cAs считаются эквивалентными)
?

N>>Что есть из готового ((возможно из boost) функторов) для частичного лексикографического поиска в ассоциативных контейнерах хранящих строки?

К>Что такое "частичный лексикографический поиск"?
К>"Лексикографический" предполагает упорядоченность — ну так ассоциативный контейнер (std::set?) и без того упорядочен.
Да я это и имел в виду, просто неправильно пообрал слова, наверно потому что под вечер устал.

К>Вопрос в том, чтобы сделать поиск более эффективно, чем линейно пробежаться и проверить каждый элемент на совпадение с маской?
К>Вынужден огорчить: в общем случае углы срезать не получится.
К>Всё, что мы можем сделать — это взять префикс из маски (скажем, для "abc*def*ghi" — префикс будет "abc") и ограничить область забега диапазоном ["abc"-"abd")
Гм... неужели никак не получится написать такой предикат, префикс конечно самый простой вариант но нет то. Получается что свойство что множество строк упорядоченно
никак нельзя использовать что бы матчить его на wildcard. Только find_if — слишком долго

К>Или вопрос в том, что маска известна заранее, и хочется построить контейнер, который
К>- отделяет подходящие строки от неподходящих (ну это банально: делаем два контейнера, проверяем каждую свежедобавляемую строку и кладём её в соответствующий)
К>- упорядочивает слова по маске (т.е. для *a* слова bAr и cAs считаются эквивалентными)
Не, не это слишком просто и статично.

Здравствуйте, Кодт, Вы писали:

К>Вопрос в том, чтобы сделать поиск более эффективно, чем линейно пробежаться и проверить каждый элемент на совпадение с маской?
К>Вынужден огорчить: в общем случае углы срезать не получится.
Да ладно, есть же суффиксные деревья и подобные структуры данных. Вот вообще поиск произвольного регулярного выражения за сублинейное время научились делать: Fast text searching for regular expressions or automaton searching on tries.

К>Всё, что мы можем сделать — это взять префикс из маски (скажем, для "abc*def*ghi" — префикс будет "abc") и ограничить область забега диапазоном ["abc"-"abd")
При таких ограничениях всякие DAWG хорошо себя показывают. Особенно если под символом «*» понимается джокер, то есть единственный символ входного алфавита (ну или когда есть другие ограничения на возможные подстановки). Впрочем я тоже не понял что конкретно нужно автору темы.

Здравствуйте, nen777w, Вы писали:

К>>Вопрос в том, чтобы сделать поиск более эффективно, чем линейно пробежаться и проверить каждый элемент на совпадение с маской?
К>>Вынужден огорчить: в общем случае углы срезать не получится.
К>>Всё, что мы можем сделать — это взять префикс из маски (скажем, для "abc*def*ghi" — префикс будет "abc") и ограничить область забега диапазоном ["abc"-"abd")
N>Гм... неужели никак не получится написать такой предикат, префикс конечно самый простой вариант но нет то. Получается что свойство что множество строк упорядоченно
N>никак нельзя использовать что бы матчить его на wildcard. Только find_if — слишком долго :-(
Так расскажи подробнее чего хочешь добиться, а не как это сейчас решаешь.
Если тебе разные нужно регулярные выражения в коллекции строк искать, то это делается по другому. Нужно строить и поддерживать индексы. А тут уже возможны варианты: от быстрых но сложных суффиксных деревьев, до простых, но часто эффективных, n-грамных индексов (вот например). Ну и от вида поискового запроса выбор эффективного алгоритма зависит — вдруг у тебя там алфавит огромный или наоборот, или ограничение на максимальную длину замены «*» есть.

WM>Так расскажи подробнее чего хочешь добиться, а не как это сейчас решаешь.
WM>Если тебе разные нужно регулярные выражения в коллекции строк искать, то это делается по другому. Нужно строить и поддерживать индексы. А тут уже возможны варианты: от быстрых но сложных суффиксных деревьев, до простых, но часто эффективных, n-грамных индексов (вот например). Ну и от вида поискового запроса выбор эффективного алгоритма зависит — вдруг у тебя там алфавит огромный или наоборот, или ограничение на максимальную длину замены «*» есть.

Спасибо за ссылки и подсказки буду изучать.
Да, нужен поиск как в словаре некотрого подмножества, только не с первой буквы а по какой то заданной маске (wildcard). Словарь лежит упорядоченный в лексографическом порядке.
O(n) — очень медленно.

Здравствуйте, nen777w, Вы писали:

N>Задана маска *ab*
N>Результат два итератора [3],[4]
Если длина строки ограничена, хотя бы в вероятностном смысле (90% строк имеют длину меньше k), я бы попробовал построить "индексы сортировки" по каждому i-му символу. Дальше поиск О(log(n)) много раз.
Я не уверен, что это будет работать и быстрее, чем O(n). Предложение более как идея, чем проверенная реализация.
И даже не уверен, что подобные извращения стоят того. Времени подобная реализация и ее отладка может занять очень много с неизвестным результатом.

Здравствуйте, watch-maker, Вы писали:

К>>Вопрос в том, чтобы сделать поиск более эффективно, чем линейно пробежаться и проверить каждый элемент на совпадение с маской?
К>>Вынужден огорчить: в общем случае углы срезать не получится.
WM>Да ладно, есть же суффиксные деревья и подобные структуры данных. Вот вообще поиск произвольного регулярного выражения за сублинейное время научились делать: Fast text searching for regular expressions or automaton searching on tries.

Ну так это на триях. (как это по-рюсски?)

К>>Всё, что мы можем сделать — это взять префикс из маски (скажем, для "abc*def*ghi" — префикс будет "abc") и ограничить область забега диапазоном ["abc"-"abd")
WM>При таких ограничениях всякие DAWG хорошо себя показывают. Особенно если под символом «*» понимается джокер, то есть единственный символ входного алфавита (ну или когда есть другие ограничения на возможные подстановки). Впрочем я тоже не понял что конкретно нужно автору темы.

Для джокера обычно используют символ "?" или ".", а "*" — это обычно колода джокеров

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, watch-maker, Вы писали:

К>>>Вопрос в том, чтобы сделать поиск более эффективно, чем линейно пробежаться и проверить каждый элемент на совпадение с маской?
К>>>Вынужден огорчить: в общем случае углы срезать не получится.
WM>>Да ладно, есть же суффиксные деревья и подобные структуры данных. Вот вообще поиск произвольного регулярного выражения за сублинейное время научились делать: Fast text searching for regular expressions or automaton searching on tries.

К>Ну так это на триях.
Ну так trie же и есть «ассоциативный контейнер хранящий строки» (как это и написано в первом сообщении) — прямо-таки классический представитель такого рода структур. Есть, конечно, ещё деревья и хэш-таблицы (правда упорядоченность только у perfect-hash разновидности есть), но trie ничем не хуже, и уж всё равно популярнее остальной экзотики.

К>(как это по-рюсски?)
Префиксное дерево, наверное.

К>>>Всё, что мы можем сделать — это взять префикс из маски (скажем, для "abc*def*ghi" — префикс будет "abc") и ограничить область забега диапазоном ["abc"-"abd")
WM>>При таких ограничениях всякие DAWG хорошо себя показывают. Особенно если под символом «*» понимается джокер, то есть единственный символ входного алфавита (ну или когда есть другие ограничения на возможные подстановки). Впрочем я тоже не понял что конкретно нужно автору темы.

К>Для джокера обычно используют символ "?" или ".", а "*" — это обычно колода джокеров :)
Да. Просто может оказаться, что если задачу можно свести к джокерам, то это позволит реализовать более эффективный алгоритм. Например, вместо «[a-z]+» иногда можно просто сказать «произвольное слово», а в терминах строк, состоящих из слов, это уже джокер. Конечно не всегда так можно сделать, но если задача это допускает, то нужно пользоваться.

Здравствуйте, nen777w, Вы писали:

N>Да, нужен поиск как в словаре некотрого подмножества, только не с первой буквы а по какой то заданной маске (wildcard).

какие маски используются? опишите более подробно есть ли у них ограничения? какой словарь используется? сколько там слов? какие длины у них?
если вы пишете приложение для тупого юзера, то подозреваю, что поиск идет по подстроке, то есть паттернов типа a?bc**a???z не будет а есть лишь некая подстрока и нужно найти все (опять же точно все? или только 5?) слова из словаря, которую содержат указанную подстроку
какие маски чаще всего будет использовать юзер? зависит от специфики вашего приложения и на кого он ориентирован
без этих уточнений я не вижу как вы сможете оптимизировать поиск, задача в общем случае решается линейно относительно размера словаря имхо