Вопросы по теме 'suffix-tree'

Построение суффиксного дерева для алгоритма сопоставления строк в большой базе данных
На прошлой неделе у меня было собеседование на стажировку, и мне задали вопрос о поиске определенной строки в большой базе данных. Я совершенно ничего не знал об этом во время интервью, хотя я просто дал ответ «многоуровневое хеширование», поскольку...
1292 просмотров
database string-matching data-structures suffix-tree
schedule 15.04.2023
Может кто-нибудь объяснить, когда и как расширить суффиксное дерево?
Я работаю над php-скриптом, который должен найти самую длинную повторяющуюся подстроку. Я нашел эту штуку Suffix-Tree. Я пытаюсь реализовать алгоритм Укконнена, но не могу понять, когда и как расширить дерево. Ничего страшного, если у меня есть...
635 просмотров
php suffix-tree
schedule 01.09.2023
Самый длинный палиндром в строке с использованием дерева суффиксов
Я пытался найти самый длинный палиндром в цепочке. Решение методом грубой силы занимает O (n ^ 3) времени. Я читал, что для этого есть алгоритм линейного времени, использующий суффиксные деревья. Я знаком с суффиксными деревьями и мне комфортно их...
26701 просмотров
algorithm palindrome suffix-tree
schedule 24.10.2022
Сопоставьте и замените смайлики в строке — как эффективнее всего?
Википедия определяет множество возможных смайликов, которые люди могут использовать. Я хочу сопоставить этот список со словами в строке. Теперь у меня есть это: $string = "Lorem ipsum :-) dolor :-| samet"; $emoticons = array( '[HAPPY]' =>...
2717 просмотров
php performance regex string-matching suffix-tree
schedule 26.01.2023
Поиск самой длинной повторяющейся подстроки
Каким будет лучший подход (с точки зрения производительности) для решения этой проблемы? Мне рекомендовали использовать суффиксные деревья. Это лучший подход?
33835 просмотров
algorithm pattern-recognition suffix-tree suffix-array
schedule 08.03.2022
Python исчерпывает память (используя деревья суффиксов)
У меня возникли небольшие проблемы с некоторым кодом. Пожалуйста, имейте в виду, что я ужасный программист, поэтому мое решение, вероятно, не очень красноречиво (и, вероятно, причина, по которой у меня заканчивается память - у меня 4 гигабайта, и...
531 просмотров
python memory-leaks large-data python-c-extension suffix-tree
schedule 14.05.2023
Максимальное и минимальное количество ребер в суффиксном дереве
Каково максимальное и минимальное количество ребер в суффиксном дереве? Я знаю, что максимум 2м-1, но я не понимаю, почему это так.
1225 просмотров
algorithm suffix-tree
schedule 26.04.2023
Застрял в поиске самого глубокого пути в общем обходе дерева, пытаясь найти самую большую общую подстроку
Я пытаюсь решить проблему наибольшей общей подстроки между двумя строками. Я сведу свою проблему к следующему: я создал общее дерево суффиксов и, насколько я понимаю, самая большая общая подстрока — это самый глубокий путь, состоящий из узлов,...
1027 просмотров
java algorithm data-structures tree suffix-tree
schedule 11.06.2022
Создание суффиксного дерева строки S[2..m] из суффиксного дерева строки S[1..m]
Существует ли быстрый (время сложности O(1)) способ создания суффиксного дерева строки S[2..m ] из суффиксного дерева строки S[1..m]? Я знаком с Укконеном, поэтому знаю, как составить быстрое суффиксное дерево строки S[1..m+1] из суффиксного...
328 просмотров
algorithm data-structures complexity-theory suffix-tree
schedule 24.10.2022
Приблизительное сопоставление подстрок с использованием дерева суффиксов
В этой статье обсуждаются методы приблизительного сопоставления подстрок, использующие дерево суффиксов для улучшения времени сопоставления. Каждый ответ относится к другому алгоритму. Приблизительное сопоставление подстроки пытается найти...
4927 просмотров
algorithm string-matching edit-distance suffix-tree
schedule 06.06.2023
В чем разница между суффиксными ссылками и неудачными ссылками?
В этом семестре я изучаю алгоритмы и прочитал об алгоритме сопоставления строк Ахо-Корасика и алгоритм Укконена для построения суффиксных деревьев. Я прочитал их оба, но не могу понять основных основных различий между ними, за исключением того,...
1223 просмотров
exact-match algorithm pattern-matching suffix-tree aho-corasick
schedule 14.06.2023
Как получить связанные соседние узлы на одной высоте при рисовании в GraphViz?
Я пытаюсь нарисовать следующее (суффиксное дерево) с помощью GraphViz : digraph G { 1[label = " "]; 2[label = " "]; 3[label = " "]; 4[label = " "]; 5[label = " "]; 6[label = " "]; 7[label = " "]; 8[label = " "]; // edges drawn...
332 просмотров
graph graphviz suffix-tree
schedule 25.03.2022
Является ли дерево суффиксов уникальным?
Я работаю над алгоритмом дерева суффиксов в биоинформатике. Я хочу знать, уникально ли дерево суффиксов? Например , String str = "xabaxe" Эта строка или другие примеры строк имеют альтернативное дерево суффиксов?
206 просмотров
algorithm bioinformatics suffix-tree
schedule 30.10.2022
Связывание в древовидных структурах
Поработав сейчас с длинными строками, я столкнулся с довольно большой проблемой при создании деревьев суффиксов в Haskell. Некоторые алгоритмы построения (например, эта версия алгоритма Укконена) требуют установления ссылок между узлами. Эти...
134 просмотров
haskell suffix-tree
schedule 27.06.2022
Как построить суффикс Trie для всех подстрок строки?
Я хочу построить эффективный суффикс для всех подстрок строки; Предположим, что длина строки равна 5000, тогда количество подстрок будет примерно 25 * 10 ^ 6, и для каждого узла я храню массив связанных данных размером 26, поэтому общая память = 26 *...
224 просмотров
substring suffix-tree suffix-array
schedule 24.04.2022
как получить самую длинную повторяющуюся строку в подстроке из дерева суффиксов
Мне нужно найти самую длинную повторяющуюся строку в подстроке. Допустим, у меня есть строка "bannana" Википедия говорит следующее: В информатике проблема самой длинной повторяющейся подстроки — это задача поиска самой длинной подстроки...
1353 просмотров
string algorithm tree perl suffix-tree
schedule 17.01.2023
Обобщенная реализация дерева суффиксов Java для больших наборов данных
У меня есть коллекция из 50 миллионов строк, каждая из которых содержит около 100 символов. Я ищу очень эффективную (время работы и использование памяти) реализацию обобщенного дерева суффиксов. Я пробовал...
366 просмотров
full-text-search data-structures suffix-tree suffix-array
schedule 20.11.2022
Как я могу найти такую ​​строку за линейное время, используя дерево суффиксов?
Для заданной строки s длины n найдите самую длинную строку t, которая встречается как в прямом, так и в обратном порядке в s. например, s = yabcxqcbaz, затем вернуть t = abc или t = cba Я рассматриваю возможность использования обобщенного дерева...
195 просмотров
search algorithm data-structures suffix-tree
schedule 31.07.2023
Являются ли суффиксные ссылки в суффиксном дереве такими же, как ребра отказа в автомате ахо-корасика?
Если да, может ли кто-нибудь объяснить назначение суффиксных ссылок в суффиксном дереве для точного сопоставления строк?
218 просмотров
algorithm suffix-tree aho-corasick
schedule 10.07.2023
как эффективно извлечь исходную строку из дерева суффиксов?
Если у нас есть суффиксное дерево строки, а также это суффиксное дерево не является суффиксным деревом укконена, т. Е. Нам дано нормальное суффиксное дерево, где метки ребер являются строками. Как эффективно вернуть исходную строку из этого дерева...
148 просмотров
string algorithm suffix-tree
schedule 09.07.2022