поиска строк, соответствующих шаблон «а: *: хуг» меньше, чем O (N)

Question

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

• Префикса - а *
• Glob-подобный узор - а: *: хуг поиск
• суффикса - * хуг

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

• начиная с «ABC», но не заканчивая «А».
• не начинается с буквы "abc", но заканчивается на "xyz".
• начиная с буквы "abc" и заканчивая на "xyz".

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

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

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

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

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

Answer 4

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

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

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

Кроме того, вы положили "герой", как

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

Кроме того, вы положили "Оха" (не спрашивай мне что Оха)

ohe, 0 
heo, 1 
eoh, 2 

Затем, если вам нужно найти шаблон «он * о», вам нужно повернуть его, пока вы не получите префикс ed string: "ohe *"

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