Где суффиксный массив предпочтительнее суффиксного дерева? - PullRequest
Новая
       27

Где суффиксный массив предпочтительнее суффиксного дерева?

2 голосов
/ 21 августа 2011

Две тесно связанные структуры данных - это дерево суффиксов и массив суффиксов.Из того, что я прочитал, дерево суффиксов является более быстрым, более мощным, более гибким и более эффективным, чем массив суффиксов.Однако в этом предыдущем вопросе один из лучших ответов упоминал, что суффиксные массивы более широко используются на практике.У меня нет опыта использования какой-либо из этих структур, но сейчас мне кажется, что я всегда предпочел бы дерево суффиксов вместо массива суффиксов для задач, которым требовалась предоставляемая ими функциональность (например, быстрая проверка подстрок).

При каких обстоятельствах массив суффиксов предпочтительнее дерева суффиксов?

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

Ответы [ 2 ]

3 голосов
/ 21 августа 2011

Ссылаясь на http://www.youtube.com/watch?v=1DGZxd-PP7U

Суффиксные массивы и суффиксные деревья раньше были разными. Но в наши дни Суффиксные массивы - это просто способ реализации суффиксного дерева (или наоборот). Versa). Смотрите: Ким, Ким и Парк. Линейное суффиксное дерево: эффективный индексировать структуру данных с возможностями суффиксных деревьев и суффиксов массивы. Алгоритмика, 2007.

1007
1 голос
/ 19 июня 2012

Суффиксный массив почти всегда предпочтителен, кроме:

  • Если вы собираетесь индексировать небольшие количества данных.
  • Если вы проводите исследования на предмет совпадения белков или мутаций ДНК и имеете доступ к чрезвычайно дорогим компьютерам.
  • Если вам нужно любой ценой использовать поиск ошибок с подстановочными знаками.

Для реализации дерева суффиксов можно использовать массив суффиксов. Значение суффиксного дерева может быть массивом суффиксов и несколькими дополнительными структурами данных для имитации функциональности дерева суффиксов.

Таким образом:

  • Суффиксные массивы занимают меньше места (намного меньше)
  • Суффиксные деревья строятся медленнее
  • Суффиксные деревья быстрее выполняют операции сопоставления с образцом
  • Деревья суффиксов могут выполнять больше операций, лучше всего сопоставлять шаблоны ошибок с подстановочными знаками (массив суффиксов также выполняет сопоставление с образцами, но не с подстановочными знаками)

Если вы хотите проиндексировать много данных, например, более 50 мегабайт. Дерево суффиксов занимает столько места, что на вашем компьютере недостаточно оперативной памяти, чтобы хранить его в центральной памяти. Поэтому он начинает использовать вторичную память, и вы увидите огромное снижение скорости. (например, человеческая днк использует 700 мегабайт, дерево суффиксов этих данных «может» использовать 40 гигабайт -> * «может» в зависимости от реализации *)

Из-за этого дерево суффиксов практически никогда не используется на практике. На практике используется массив суффиксов, а небольшие дополнительные структуры данных дают ему дополнительную функциональность (никогда не полное дерево суффиксов).

Однако они разные. Во многих случаях для сопоставления с образцом предпочтителен массив с суффиксами из-за эффективной скорости, высокой скорости построения и малого использования пространства.

...