Описание тега suffix-tree
Суффиксное дерево - это структура данных, в которой хранятся все суффиксы строки. Это основа для многих быстрых алгоритмов на основе строк.
1
ответ
Параллельные вставки в суффикс-дереве
Некоторое время назад я опубликовал вопрос о сохранении / получении суффиксного дерева с диска. Это, наконец, работает нормально, но сейчас строительство идет очень медленно, и я не хочу сейчас связываться с алгоритмом Укконена (линейное построение)…
10 дек '11 в 15:44
1
ответ
Сопоставление с шаблоном java для первого появления шаблона s в дереве суффиксов для реализации алгоритма Укконена Марком Нельсоном
Я попытался построить дерево суффиксов на основе реализации алгоритма Укконена Марком Нельсоном в коде Java, который является вариантом кода по адресу: http://www.sanfoundry.com/java-program-implement-suffix-tree/ Следующий код создает компактное де…
28 окт '15 в 00:08
1
ответ
Haskell: ошибка алгебраических типов (деревья суффиксов: рекурсия)
Работая над функцией, для которой в качестве входных данных задано SuffixTree, выводится список целых чисел в этом дереве суффиксов. Например. getIndices tree1 = [2,4,1,3,5,0] . Порядок списка целых чисел не имеет значения. Я получаю сообщение об ош…
02 янв '14 в 21:07
1
ответ
Суффиксный массив / суффиксное дерево с числами
Могут ли суффиксные деревья или суффиксные массивы эффективно использоваться с числами? Например: Можно ли использовать с массивом [1,2,3,4,5,3,9,8,5,3,9,8,6,4,5,3,9,11,9,8,7,11] извлечь все возможные непересекающиеся повторяющиеся подстроки всех ра…
21 янв '16 в 14:22
0
ответов
Как получить ключ и значения в Суффикс tree.substringdict
Я использую суффиксное дерево для извлечения совпавшей подстроки. readme файл содержит пример как - >>> import SuffixTree.SubstringDict >>> d = SubstringDict.SubstringDict() >>> d['foobar'] = 1 >>> d['barfoo'] = 2…
10 сен '17 в 04:21
1
ответ
Являются ли ссылки суффиксов в дереве суффиксов такими же, как рёбра неудачи в ахо-коразическом автомате?
Если да, может ли кто-нибудь объяснить назначение суффиксных ссылок в дереве суффиксов для точного сопоставления строк?
04 окт '16 в 15:52
1
ответ
Сопоставляет перекрывающиеся взгляды на LZ77/LZSS с суффиксными деревьями
Предыстория: у меня есть реализация универсального бэкэнда LZSS на C++ (доступно здесь. Алгоритм сопоставления, который я использую в этой версии, чрезвычайно прост, потому что он изначально предназначался для сжатия относительно небольших файлов (м…
10 июл '15 в 18:13
2
ответа
Что такое суффикс автомат?
Может кто-нибудь объяснить мне, что такое суффиксный автомат, и как он работает и отличается от суффиксных деревьев и суффиксных массивов? Я уже пробовал поиск в Интернете, но не смог найти четкого исчерпывающего объяснения. Я нашел следующую ссылку…
25 июн '14 в 14:10
2
ответа
Можно ли посчитать количество различных подстрок в строке в O(n)?
Учитывая строку s длины nМожно ли посчитать количество различных подстрок в s в O(N)? пример Входные данные: abb Выход: 5 ('abb', 'ab', 'bb', 'a', 'b') Я провел некоторые исследования, но я не могу найти алгоритм, который решает эту проблему таким э…
19 янв '16 в 17:00
0
ответов
Все взаимно отличающиеся битовые маски из списка
Учитывая список строк, я хочу найти количество битовых масок, я хочу найти количество пар, где bit-mask1 & bit-mask2 = 0, Эта проблема была дана на внутришкольном конкурсе в моей школе для учеников 12 класса. Я получил вопросник, и это была сама…
07 июл '16 в 11:59
3
ответа
Как работают Суффикс-деревья?
Я просматриваю главу о структурах данных в Руководстве по разработке алгоритмов и наткнулся на деревья суффиксов. Пример гласит: Входные данные: XYZXYZ$ YZXYZ$ ZXYZ$ XYZ$ YZ$ Z$ $ Выход: Я не могу понять, как это дерево генерируется из заданной вход…
13 июн '12 в 16:53
2
ответа
Алгоритм для сопоставления двух шаблонных строк
Мне нужно написать алгоритм для самого длинного совпадения префикса / суффикса с двумя образцами, сложность которого равна O(n+m1+m2), где n - длина строки, а m1, m2 - длины pattern1 и pattern2 соответственно. Пример: если строка - "OBANTAO", а Patt…
17 фев '14 в 20:22
1
ответ
Может кто-нибудь объяснить, когда и как расширить дерево суффиксов?
Я работаю над PHP-скриптом, который должен найти самую длинную повторяемую подстроку. Я нашел эту вещь Суффикс-Три. Я пытаюсь реализовать алгоритм Укконнена, но не могу понять, когда и как расширить дерево. Это нормально, если у меня есть новый симв…
16 апр '11 в 12:16
1
ответ
Как эффективно извлечь исходную строку из дерева суффиксов?
Если у нас есть дерево суффиксов строки, а также то, что дерево суффиксов не является деревом суффиксов ukkonen, т. Е. Нам дается нормальное дерево суффиксов, где метки ребер являются строками. Как эффективно вернуть исходную строку из этого дерева …
21 окт '16 в 01:09
1
ответ
Как связать соседние узлы на одной высоте при рисовании в GraphViz?
Я пытаюсь нарисовать следующее (суффикс-дерево) с помощью GraphViz: digraph G { 1[label = " "]; 2[label = " "]; 3[label = " "]; 4[label = " "]; 5[label = " "]; 6[label = " "]; 7[label = " "]; 8[label = " "]; // edges drawn vertically, all fine. 1 -&…
26 авг '14 в 14:24
2
ответа
Самая длинная повторяющаяся подстрока с правильностью не менее k вхождений
Алгоритмы нахождения самой длинной повторяющейся подстроки формулируются следующим образом 1)build the suffix tree 2)find the deepest internal node with at least k leaf children Но я не могу понять, почему это работает, так что в основном, что делае…
15 ноя '16 в 14:58
2
ответа
Корневая идентификация в списке данных в python:
Я новичок в Python. Я пытался придумать "Root Identification" из списка данных. Но это не работает. Вот код, который я пробовал: listData=["blackish", "blacken","blacked"] Результат, который я ожидаю: root = [black] and suffixLi = ["ish", "en", "ed"…
14 сен '15 в 22:43
1
ответ
Почему перевод этого фрагмента кода из C# в C++ снижает производительность?
Я гораздо лучше знаком с C#, чем с C++, поэтому я должен спросить совета по этому вопросу. Мне пришлось переписать некоторые куски кода на C++, а затем (что удивительно) столкнулся с проблемами производительности. Я сузил проблему до следующих фрагм…
17 авг '17 в 22:57
1
ответ
Реализация Java с обобщенным суффиксным деревом для больших наборов данных
У меня есть коллекция из 50 миллионов строк, каждая из которых содержит около 100 символов. Я ищу очень эффективную (во время выполнения и использование памяти) обобщенную реализацию дерева суффиксов. Я пробовал https://github.com/npgall/concurrent-…
03 ноя '15 в 20:32
1
ответ
Поиск в неявном суффиксном дереве, построенном по алгоритму Укконена
Я столкнулся с проблемой, которая требует структуру данных, которая будет содержать строку S и позволит мне: Проверьте, является ли слово W подсловом слова S за O(|W|) Найти самый длинный суффикс S, который также является префиксом заданного слова U…
11 янв '13 в 08:18