Поиск строк, соответствующих шаблону "abc: *: xyz", менее чем за O (n)

Question

Учитывая кучу строк, мне нужно найти те, которые соответствуют 3 видам паттернов:

• Поиск префикса - abc *
• Шарообразный рисунок - abc: *: xyz
• Поиск по суффиксу - * xyz

где * - подстановочный знак (и может соответствовать любому числу символов).

Теперь простое решение - просто просмотреть каждую строку и посмотреть, соответствует ли она целевому шаблону. Но это O (n). Если я сохранил строки в сбалансированном дереве поиска, я могу выполнить префиксные запросы в O (log n). Если бы я создал еще одно дерево, в котором все строки были по существу перевернуты, я мог бы выполнять суффиксные запросы в O (log n). Есть ли эффективный способ эффективного поиска шаблонов «abc: *: xyz»?

Answer 1

Разве пересечение результатов двух других запросов не даст вам именно этого? И поскольку каждый из результатов равен O (log N), а пересечение по этому набору результатов равно O (N) в размере набора результатов, разве сумма не будет также O (log N) по сравнению с исходной задачей?

Answer 2

Генерация поворотов каждого слова и размещение каждого поворота в дереве суффиксов с указанием «индекса поворота».

Например, чтобы поставить строку "привет", введите

hello, 0
elloh, 1
llohe, 2
lohel, 3
ohell, 4

Кроме того, вы ставите «герой» как

hero, 0
eroh, 1
rohe, 2
oher, 3

Кроме того, вы ставите "ОХЭ" (не спрашивайте меня, что ОХЭ)

ohe, 0
heo, 1
eoh, 2

Тогда, если вам нужно искать шаблон "он * о", вам нужно вращать его, пока не получите строку с префиксом: "Оха *"

В дереве суффиксов вы найдете кандидатов: (ohell, 4), (oher, 3), (ohe, 0). Затем вы восстанавливаете их исходные версии (не поворачивая их) и выбираете правильные версии - «привет» и «герой».

Answer 3

Если «abc» и «xyz» являются фиксированными значениями, вы можете сохранить в своей коллекции три счетчика, указывающих количество строк:

• начинается с "abc", но не заканчивается на "xyz".
• не начинается с "abc", а заканчивается "xyz".
• начиная с "abc" и заканчивая "xyz".

Это дает вам O (1) временную сложность поиска за счет дополнительных вычислений при вставке или удалении из коллекции.

Если «abc» и «xyz» - произвольные строки, это O (n) для всех операций, включая одну «abc ...». Вам нужно только рассмотреть, что происходит, когда ваши коллекции состоят из элементов, начинающихся с «abc», чтобы увидеть это. Он вообще не ограничен O (logN), поскольку вам нужно обрабатывать все элементы в дереве (обе ветви каждого неконечного узла).

Я думаю, что ваше идеальное решение состоит в том, чтобы поддерживать два упорядоченных дерева, одно для нормальных строк и одно для перевернутых строк. Но не беспокойтесь о попытках пересечения между ними. Все, что вам нужно сделать, - это максимально сократить пространство поиска.

• Чтобы найти «abc ...», используйте обычное дерево, чтобы найти строки, начинающиеся с этого значения.
• Чтобы найти «... xyz», используйте обратное дерево, чтобы найти строки, заканчивающиеся обратным значением этого значения (zyx ...).
• Чтобы найти «abc ... xyz», используйте обычное дерево, чтобы найти строки, начинающиеся с этого значения, а затем отфильтруйте те, которые не заканчиваются на «xyz».

Таким образом, вам не нужно беспокоиться о пересечении значений между двумя деревьями, и вы все равно получаете улучшение производительности по сравнению с упрощенным линейным поиском.

Answer 4

Если вы учитываете возможность сохранения строк в дереве поиска, почему бы не сохранить свойства «начинается с abc» и «заканчивается xyz», используя эти свойства в качестве ключей?

Edit: Вы также можете оставить Big-O-Notation и сконцентрироваться на фактической ожидаемой продолжительности поиска в вашем конкретном случае использования. Это, вероятно, более реалистичный подход; Оценки стиля O (f (n)) для вашего алгоритма / реализации, вероятно, не дают вам много полезной информации, когда дело доходит до реальной эффективности поиска.