Какой поиск быстрее, бинарный поиск или дерево префиксов?
Предположим, у меня есть список строк и префиксное дерево этих строк, и я хотел бы найти строку по заданному ключу, какая из них быстрее? бинарный поиск или поиск по префиксу дерева?
Почему и во сколько сложность?
Спасибо!
1 ответ
Решение
Оба метода имеют свои преимущества и недостатки:
Суффикс дерево
- Преимущества:
- O(N) сложность здания
- O(M) поиск шаблона длины M
- Они позволяют онлайн строительство
- Недостатки:
- Пространство неэффективно
- Действительно сложные алгоритмы построения
Бинарный поиск (с суффиксным массивом)
- Преимущества:
- Вы можете отсортировать массив строк в O(N) времени
- Экономия пространства (в пять раз меньше памяти (как минимум))
- Простые и понятные алгоритмы построения
- Недостатки:
- Они не поддерживают онлайн-строительство
- O(M lg N) время поиска шаблона длины M среди N строк (это может быть уменьшено до O(M+lg N), но это все же немного медленнее, чем дерево суффиксов)
Обе эти структуры данных действительно мощные. Если ваше приложение требует быстрого поиска, и предоставленного места достаточно, тогда определенно используйте суффиксные деревья. Но если пространство имеет значение, тогда суффиксный массив (бинарный поиск) - единственный выбор, который у вас есть...