Описание тега suffix-array
Массив суффиксов - это структура данных, которая представляет собой лексикографически отсортированный список всех суффиксов строки (в информатике, а не в лингвистике, смысл слова "суффикс"). Это основа для многих высокопроизводительных алгоритмов, выполняемых с очень большими строками, например полнотекстового поиска или сжатия.
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
2
ответа
Что такое суффикс автомат?
Может кто-нибудь объяснить мне, что такое суффиксный автомат, и как он работает и отличается от суффиксных деревьев и суффиксных массивов? Я уже пробовал поиск в Интернете, но не смог найти четкого исчерпывающего объяснения. Я нашел следующую ссылку…
25 июн '14 в 14:10
3
ответа
Как отсортировать массив суффиксов?
Я смотрю на примеры массивов суффиксов и самых длинных общих префиксов, но я не понимаю критерии сортировки массива суффиксов. Я смотрю на пример в Википедии, где они используют банан $ Может кто-нибудь объяснить, как сортируется массив суффиксов? М…
15 авг '14 в 05:35
1
ответ
Как я могу найти номер вхождения каждого суффикса в строке?
Я хочу узнать, сколько раз каждый суффикс строки встречается в исходной строке за O(nlogn) или O(n) время. Например, для строки aba суффикс a появляется дважды, ba появляется один раз, aba появляется один раз.
15 окт '16 в 01:59
3
ответа
Двоичный поиск, чтобы найти самый длинный общий префикс
Для школьного задания мы реализуем суффикс-массив с методами его построения и нахождения самого длинного общего префикса. Мне удается довольно легко построить и отсортировать массив суффиксов, но я борюсь с LCP. Я пытаюсь найти самый длинный общий п…
16 дек '17 в 19:56
2
ответа
Самая длинная повторяющаяся подстрока с правильностью не менее k вхождений
Алгоритмы нахождения самой длинной повторяющейся подстроки формулируются следующим образом 1)build the suffix tree 2)find the deepest internal node with at least k leaf children Но я не могу понять, почему это работает, так что в основном, что делае…
15 ноя '16 в 14:58
0
ответов
Сумма LCP всех пар подстрок данной строки
Как найти сумму длинных общих префиксов всех пар подстрок данной строки. Например, ответ для строки "aba" - 8. |s|<=1e5.
20 мар '17 в 19:11
1
ответ
Как вы на самом деле применяете суффиксные массивы к любому виду текста?
Я читаю о Suffix Arrays и код для его создания прост. Но все ресурсы, которые я нашел, обычно используют тривиальный пример текста, который обычно banana, чтобы объяснить концепцию.Таким образом, хотя текст примера тривиален и массив суффиксов предс…
15 дек '12 в 10:37
1
ответ
Используется ли сортировка по основанию для сортировки суффиксов?
Я пытаюсь реализовать сортировку блоков. Это из бумаги Берроуз Уилер. (Перед этим шагом вы создаете массив суффиксов V из S) Q4. [радикальная сортировка] Сортируйте элементы V, используя первые два символа каждого суффикса в качестве ключа сортировк…
15 июн '11 в 03:26
1
ответ
Самая длинная общая подстрока с использованием суффиксных автоматов
Я использовал для вычисления самой длинной общей подстроки, используя динамическое программирование O (m * n), дерево суффиксов O (m + n), массив суффиксов O(nlog^2 n) в соответствии с моими потребностями. Недавно я выучил Suffix Automaton, который …
16 мар '14 в 20:18
2
ответа
Как LCP помогает определить количество вхождений паттерна?
Я прочитал, что Longest Common Prefix (LCP) можно использовать для определения количества вхождений шаблона в строку. В частности, вам просто нужно создать массив суффиксов текста, отсортировать его, а затем вместо того, чтобы выполнять бинарный пои…
07 июл '12 в 08:18
1
ответ
Каково значение суффиксов, сортируемых в массив суффиксов?
Я знаю, что само определение суффиксного массива состоит в том, что это отсортированный массив всех суффиксов строки. Но я пытаюсь понять, каково значение этой операции сортировки здесь? Предположим, что мы создаем массив всех суффиксов строки и выб…
14 июн '14 в 11:29
1
ответ
Реализация Java с обобщенным суффиксным деревом для больших наборов данных
У меня есть коллекция из 50 миллионов строк, каждая из которых содержит около 100 символов. Я ищу очень эффективную (во время выполнения и использование памяти) обобщенную реализацию дерева суффиксов. Я пробовал https://github.com/npgall/concurrent-…
03 ноя '15 в 20:32
2
ответа
Хорошие педагогические ресурсы по массивам суффиксов
Я просто не могу найти хорошего педагогического ресурса, объясняющего массивы суффиксов. Даже "Библия" не покрывает это. Где я могу найти четкое и полное объяснение массивов суффиксов и их использования? (Видеокурс был бы идеальным, потому что я лен…
25 фев '12 в 00:50
2
ответа
Соответствие шаблону строки, суффиксный массив может решить эту проблему или иметь больше решений?
У меня есть строка, которая генерируется случайным образом с помощью специальных символов (B,C,D,F,X,Z), например, чтобы создать следующий список строк: B D Z Z Z C D C Z B D C B Z Z Z D X D B Z F Z B D C C Z B D C F Z .......... у меня также есть с…
22 фев '12 в 10:02
8
ответов
Эффективное сопоставление строк и шаблонов в C++ (суффиксарри, trie, суффикстри?)
Я ищу эффективную структуру данных для сопоставления строк и шаблонов с огромным набором строк. Я узнал о попытках, суффикс-деревьях и суффикс-массивах. Но я пока не смог найти готовую реализацию в C/C++ (и сам по себе ее реализация кажется сложной …
13 ноя '12 в 16:41
3
ответа
Создание суффиксного массива nlogn
Я изучал создание массивов суффиксов, и я понимаю, что сначала мы сортируем все суффиксы по первому символу, затем по первым 2 символам, затем по первым 4 символам и т. Д., В то время как количество символов, которые нужно рассмотреть, меньше, чем 2…
17 июл '16 в 07:48
1
ответ
Эффективный Подсчет всех подстрок в отсортированном порядке
Вам дают строку найти частоту всех отсортированных подстрок (в порядке убывания) в соответствии с их частотой. Например: ababa {"a", "b", "a", "b", "a", "ab", "ba", "ab", "ba", "aba", "bab", "aba", "abab", "baba", "ababa"}. выход: 3,2,2,2,2,1,1,1,1 …
09 июн '15 в 19:24
1
ответ
cocos2d-iphone. Spritesheet в зависимости от разрешения экрана?
cocos2d добавляет суффиксы к ресурсам так же, как "@2x" работает для обычных приложений iOS. Я также хочу поместить эти картинки в спрайт-лист. Проблема заключается в том, что спрайт-лист cocos2d по умолчанию представлен в виде одного png и одного p…
21 июл '13 в 19:37
1
ответ
Быстрый способ найти подстроку в тексте, используя суффикс массив и lcp
Я пытаюсь найти слова, которые содержат подстроку (в качестве входных данных) в большом тексте. Текст выглядит так: * америка * питон * эрика * escape *.. Пример: ввод: "рика" => вывод: америка, эрика Я использую массив суффиксов. Мой псевдокод (пох…
10 май '14 в 19:23