Подстановочный знак обратного просмотра - PullRequest
Новая
       27

Подстановочный знак обратного просмотра

0 голосов
/ 16 сентября 2018

У меня есть список шаблонов, которые содержат ноль или более символов подстановки (*) в любом месте своего тела: 

bleurgh
p0*
p*w
p*w*
*01
*.nowsich.* (dots here are meaningless)

Разрешены только символы подстановки (это не полное регулярное выражение любого рода) иони могут появляться в любом месте шаблона.Шаблон только с подстановочными знаками недопустим, и двойной подстановочный знак (**) не имеет смысла, поскольку он идентичен * (но гарантированно кто-то попробует его.) Их порядка от 100 000 до миллиона.

Код увидит новые целевые строки, которым он может соответствовать: 

p01w01
pod01whiskey02
ppp.nowsich.com
aZL8u4qXfg!LooksLikeRandomGarbageToMe!kx961giRVV
callmeishmael

Эти строки не ограничены, но, вероятно, будут меньше, скажем, 32 символа, и код увидит ихпорядка двух в секунду (это вещи с низкой скоростью.)

Я ищу способ обратного поиска шаблонов, которым могут соответствовать строки: (входные данные для выходных данных, здесь)

m01z01 -> *01
p03w01 -> p0*, p*w*, *01
bleurgh -> bleurgh
www.nowsich.org -> *.nowsich.*
wut -> [the empty list]

Меня не ограничивает память;более быстрый поиск, безусловно, лучше.

Лучшее, что я могу придумать, - это построить ориентированный граф компонентов шаблона, где каждый компонент является выходным значением split("*", pattern), а конечные символы подстановки связаны с их листом:

        ___   {implied root node} 
       /      /    |           \
[bleurgh]  [p0]   [p]          [] // leading wildcard?
           /      /           /  \
         [w]    [w*]       [01]  [.nowsich.*]

... и сделать DFS на дереве, выбирая те поддеревья, чьи регулярные выражения корневых узлов совпадают с шаблоном, перекомпилированным из родительских узлов поддерева (вплоть до корня.) Я ненравится идея что, O(log n)?регулярные выражения, но набор данных не огромен.Кроме того, я считаю, что мне нужно всегда искать ветку "ведущего символа подстановки" дерева, поэтому, возможно, поиск пары этих деревьев (одно с и без переднего символа подстановки) - это путь.

Существует некоторый предыдущий уровень техники, который, кажется, не применяется по разным причинам:

Хороший алгоритм и структура данных для поиска слов с пропущенными буквами?

Эффективный алгоритм сопоставления строк

Оба имеют свои собственные ограничения, которые не соответствуют моим.

Вопрос в том, а) подходит ли подход Iизложенное выше имеет смысл;и б) у вас есть лучший подход?

1 Ответ

0 голосов
/ 21 сентября 2018

Сделал что-то реальное, чтобы сделать это, и вот что я выучил:

  • Эта идея работает, но вместо дерева используйте дерево. При проверке строк на соответствие шаблонам вы можете пропустить узлы, которые не имеют значения и имеют только одного дочернего элемента, что уменьшает количество необходимых регулярных выражений.
  • Конечные и ведущие подстановочные знаки нуждаются в особой обработке, по крайней мере, в моем случае (напомним, что только подстановочный знак - * - символ имеет особое значение в моем случае.) Если нет начального или конечного подстановочных знаков, вам необходимо включить привязка к первому или последнему ключу, сохраненному для шаблона. Это означает, что шаблон *p0* и p0* представлен двумя узлами в дереве. (Аналогично для листовых узлов - то есть, последний токен в шаблоне.)
  • Еще одно примечание, характерное для моей ситуации: мне нужно было избегать всего, что имеет значение для регулярных выражений, но не значило для меня - например, символы ., [, ], {, } и скоро. Можно было бы включить их в последовательность сопоставления с образцом, но вам пришлось бы токенизировать по-другому.
  • Хранение скомпилированного регулярного выражения для сопоставления - это повышение скорости. В моем случае это написано на Go, поэтому я могу сохранить результат regexp.Compile([interstitial-pattern]) для каждого узла в дереве.
...