Мне нужно эффективно сопоставить входную строку с большим набором ранее вставленных строк, все известной длины N.
Эту проблему обычно можно решить с помощью радикальных деревьев (пример вопрос здесь ), но у меня есть некоторые особые свойства, которые, по моему мнению, отличают эту проблему от того, что я видел до сих пор:
- И входные, и сохраненные строки могут содержать символы подстановки
_ (нетстрока - сохраненная или входная - может содержать только символы подстановки).Например, a_c будет соответствовать _bc, но не __b. - Набор изменяется, поэтому вставка / удаление записей должно быть простым.
- Строки не являются произвольными;допустимые символы различны для каждой позиции в строке.Например, первый символ может быть только в
[a-c], в то время как второй символ может быть в [a-z].Это известно заранее и никогда не меняется. - Мне не нужно возвращать совпадения строк.Вместо этого мне нужны идентификаторы соответствующих строк.Я упоминаю об этом в случае, если есть эффективный способ сохранить график без представления всех вставленных строк.
Мое текущее решение состоит в том, чтобы сохранить трехмерный набор векторов, где первое измерение соответствует позициисимвола в строке и другого с его значением (включая подстановочный знак);третье измерение содержит все идентификаторы, которые соответствуют этой конкретной позиции / значению.Чтобы найти набор совпадений, я вычисляю set_intersection всех идентификаторов, которые я получаю, просматривая эту матрицу с входной строкой (аналогично это предлагаемое решение ).
Однако эторешение все еще не достаточно быстрое (это мое текущее узкое место), и мне было интересно, есть ли способ сделать лучше.