как найти индексы всех совпадающих подстрок с помощью дерева суффиксов?

Я создал дерево суффиксов из этого удивительного ответа. Работает как часы!

На данный момент, если я ищу «кошку» в «Этот кот - красивая кошка», он вернет 5 как первое появление «кошки», как для начального индекса 5.

Но я не могу найти способ отслеживать все суффиксы в алгоритме для создания. Так что в основном я могу найти индекс первого совпадения, но не всех разных вхождений.

На данный момент у меня есть:

class Edge
{
    int textIndexFrom;
    Node* nodefrom;
    Node* nodeTo;
    int textIndexTo;
}

class Node
{
    std::map<char,Edge*> m_childEdges;
    Edge* m_pParentEdge;
    Node* m_pLinkedNode;
}

Я просто поместил соответствующие переменные в код выше. Я предполагаю, что для хранения различных начальных позиций в Edge требуется std::vector, но я не вижу, когда добавлять новый индекс. Мы могли бы использовать активную точку, но с суффиксными ссылками это становится сложнее.

Может ли кто-нибудь объяснить?


c++ algorithm suffix-tree
person dyesdyes    schedule 11.06.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я предполагаю, что вы построили дерево суффиксов для строки S$, где $ — это какой-то специальный символ, отсутствующий в S. Символ $ гарантирует, что каждый суффикс имеет свой собственный лист в дереве. Количество вхождений слова w в S равно количеству листьев в поддереве w.

Я думаю, что для хранения всех начальных позиций в каждом ребре/узле потребуется квадратичная память. Например, если T является идеально сбалансированным бинарным деревом, то на уровне 0 (корневом) у вас будет n записей, а на уровне 1 у вас будет 2 * n/2. записи и так далее. После суммирования это дает нам n^2. Это требует доказательств, поэтому, пожалуйста, поправьте меня, если я ошибаюсь.

Вместо этого я думаю, что лучше хранить все листья в списке в том порядке, в котором они появляются при обходе дерева в dfs (слева направо, если вы рисуете изображение дерева). И в каждом узле v держите 2 указателя на элементы этого списка. Первый должен указывать на первый лист поддерева v, а второй — на последний лист поддерева v. Все это можно вычислить с помощью простой процедуры поиска в глубину. Теперь, если, например, «кошка» окажется в середине некоторого ребра, пройдите через это ребро к некоторому узлу v и получите листья из этого узла. Кроме того, в каждом листе вы должны хранить длину пути от корня до этого листа. Это поможет вам найти положение этого конкретного случая «кошки».

person piotrekg2    schedule 11.06.2014
comment
Да, я не думал о том, чтобы поставить уникальный символ в конце, чтобы иметь все возможные случаи. Что касается места для хранения, я тоже так думал, но я немного не знал, как это сделать. - person dyesdyes; 12.06.2014
comment
Я на самом деле не думаю, что вам нужно все, что вы сказали. Если вы спуститесь по дереву со строкой для поиска и окажетесь в конце ребра, которое не является листом, то у вас есть несколько совпадений, и тогда вам просто нужно взять начальный индекс каждого ребра, начиная со следующего узла, чтобы вычислить правильные индексы. - person dyesdyes; 12.06.2014
comment
Сначала определите все листья. Предположим, что N — длина всей строки, L — длина суффикса, соответствующего некоторому листу l. Позиция в S - N - L. - person piotrekg2; 12.06.2014

arrow_upward
0
arrow_downward

Пройдитесь по всему поддереву cat. Каждый лист в этом поддереве соответствует суффиксу, который начинается с cat. Если вы знаете длину строки, с которой вы сопоставлялись, и длину строки, каждый раз, когда вы сталкиваетесь с листом, вы можете выполнять вычитание, чтобы найти индекс соответствующего вхождения cat.

person tmyklebu    schedule 11.06.2014