Düz ingilis dilində Ukkonen suffix ağac alqoritmi

Bu anda bir az yağ hiss edirəm. Mən başımı ağac ağacının dizaynına sarmamaq üçün günlər keçirdim, amma matematiksel mənşəyim olmadığı üçün matematiksel simvolizmi aşkardığında məndən çox şey izah edirdi. Mən tapdığım yaxşı izahata ən yaxşısı , Sufik ağacları olan xəttləri axtarın , lakin müxtəlif nöqtələri susdurur və alqoritmin bəzi aspektləri aydın deyil.

on123.ru haqqında bu alqoritmin addım-addım izahı bir çox digərləri üçün çox qiymətli olardı, amma məndən başqa.

Referans üçün burada Ukkonen alqoritmi haqqında bir məqalə var: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Mənim əsas anlayışım, indiyə qədər:

  • Mənə verilən hər bir simli T'nin hər bir ön pusu ilə təkrarlamaq lazımdır
  • Mən hər bir S sufunu P ön kodunda yinelemek və ağaca əlavə etmək lazımdır
  • Ağaca S suffixini əlavə etmək üçün S-də hər bir xarakterə görə təkrarlamaq lazımdır və ya yinelemələr ya S-də eyni simvolu C ilə başlayan və bir kənəni nəsil düyünlərinə bölmək olarsa, Aşağıya enmək üçün uyğun bir kənar yoxdursa, VEYA nişanında fərqli bir xarakter alıram. C üçün eşleme kənarında heç bir nəticə tapılmadıqda, C. üçün yeni bir səthi kənar yaranır.

Əsas alqoritm O (n 2 ), ən çox şərhlərdə göstərildiyi kimi, biz bütün prefikslərdən keçməmiz lazım olduğundan, hər prefiks üçün hər bir sonrakı keçmək lazımdır. Ukkonen alqoritmi istifadə etməli endeks-indeks üsulu sayəsində unikal görünür, baxmayaraq ki bu mənim anlayışımla qarşılaşdığım bir şeydir.

Mən də problemləri anladım:

  • dəqiq vaxt və necə "aktiv nöqtə" təyin edilmiş, istifadə edilmiş və dəyişdirilmişdir
  • alqoritm qanununun aspektinə nə gəlir
  • Niyə gördüyüm tətbiqlər istifadə etdikləri sərhəd dəyişənləri "düzəltməlidir"

Burada tam C # kodudur. Bu, yalnız düzgün deyil, həm də avtomatik canonizasiyanı dəstəkləyir və daha əlverişli mətn çıxış grafiğini nümayiş etdirir. Mənbə kodu və çıxışı:

https://gist.github.com/2373868


2017-11-04 güncellin

Uzun illərdən sonra mən əlavə ağac ağacları üçün istifadə etdim və JavaScript- də alqoritmi tətbiq etdim. Aşağıdakı Gist. Səhvsiz olmalıyıq. Js, npm install chalk eyni yerdən yükləyin və sonra bəzi parlaq çıxışları görmək üçün node.js istifadə edin. Heç bir hata kodunu almadan, eyni Gist-də ləğv edilmiş versiyası var.

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6

889
26 февр. Nathan Ridley tərəfindən 26 Fevralda təyin olundu 2012-02-26 14:30 '12 saat 14:30 'da 2012-02-26 14:30' da
@ 7 cavab

Aşağıda, Ukkonen alqoritmini təsvir etmək cəhdidir, əvvəlcə simli sadə olduqda (yəni, təkrarlanan simvollar olmadığı zaman) nə edəcəyini nümayiş etdirir və sonra tam alqoritmə genişləndirir.

Birincisi, bir neçə ilkin hesabat.

  • Quruluşumuz əsasən bir axtarış hileyinə bənzəyir. Beləliklə kök node nədir, kənarlardan çıxır, yeni qovşaqlara və digər kənarlara çıxır və s.

  • Lakin Axtarış termini markerindən fərqli olaraq, sərhədlər yalnız simvol deyildir. Bunun əvəzində, hər bir kənar bir cüt tamsayı ilə qeyd olunur. Bunlar mətn üçün göstəricidir. Bu mənada, hər bir kənar özbaşına uzunluqlu bir simli etiketi daşıyır, lakin yalnız O (1) yer (iki göstərici) götürür.

Əsas prinsip

İlk öncə ağacın, xüsusən sadə simli, təkrarlanan simvollar olmadan bir simli necə yaratmaq istərdim:

 abc 

Alqoritm adımdan, soldan sağa doğru işləyir . Simətdə hər bir xarakter üçün bir addım var . Hər bir addım birdən çox ayrı əməliyyat ola bilər, amma əməliyyatların ümumi sayı O (n) olduğuna baxacağıq (sonunda yekun qeydlərə baxın).

Beləliklə, biz soldan başlayırıq və ilk olaraq yalnız bir xarakterə daxil edək, hesabatdakı düymə kökünündən (solda) bir kənar yaradır və onu [0,#] olaraq təyin edər, yəni kənarın 0-da başlayan və sonda cari son. 1 nömrəli cari endiyi göstərmək üçün # simvolunu istifadə edirəm (dərhal sonra).

Beləliklə, bu kimi görünür bir ilk ağac var:

2019

2073
ответ дан jogojapan 01 марта '12 в 12:13 2012-03-01 12:13

Я попытался реализовать Дерево Суффикса с подходом, указанным в jogojapan-ответе, но в некоторых случаях он не работал из-за формулировки, используемой для правил. Более того, я упомянул, что с помощью этого подхода никто не смог реализовать абсолютно правильное дерево суффикса. Ниже я напишу "обзор" jogojapan-ответа с некоторыми изменениями правил. Я также опишу случай, когда мы забудем создавать суффиксные ссылки важные .

Дополнительные используемые переменные

  • активная точка - тройной (active_node; active_edge; active_length), показывающий, откуда мы должны начать вставлять новый суффикс.
  • остаток - показывает количество суффиксов, которые мы должны добавить явно. Например, если наше слово "abcaabca", а остальное = 3, это означает, что мы должны обработать 3 последних суффикса: bca , ca и a .

Давайте используем концепцию внутреннего node - всех узлов, кроме корня, а листья - внутренних узлов .

Наблюдение 1

Когда окончательный суффикс, который нам нужно вставить, уже существует в дереве, само дерево вообще не изменяется (мы обновляем только active point и remainder ).

Наблюдение 2

Если в некоторой точке active_length больше или равно длине текущего края ( edge_length ), мы перемещаем наш active point вниз, пока edge_length не будет строго больше active_length .

Теперь давайте переопределим правила:

Правило 1

Если после вставки из активного корня node =, активная длина больше 0, то:

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

Правило 2

Если мы создадим новый внутренний node OR , создадим вставку из внутреннего node, и это не первый SUCH внутренний node при текущей шаг, то мы связываем предыдущий SUCH node с ЭТО через суффиксную ссылку.

Это определение Rule 2 отличается от jogojapan ', так как здесь мы учитываем не только вновь созданные внутренние узлы, но и внутренние узлы, из которых мы делаем вставку.

Правило 3

После вставки из активного node, который не является корнем node, мы должны следовать ссылке суффикса и установить активный node на node, на который он указывает. Если нет ссылки на суффикс, установите активный node в корень node. В любом случае активный край и активная длина остаются неизменными.

В этом определении Rule 3 мы также рассмотрим вставки листовых узлов (а не только разделенные узлы).

И, наконец, Observation 3:

Когда символ, который мы хотим добавить в дерево, уже находится на краю, мы, согласно Observation 1 , обновляем только active point и remainder , оставляя дерево неизменным. НО , если есть внутренний node, помеченный как необходимая ссылка суффикса, мы должны подключить это node к нашему текущему active node через суффиксную ссылку.

Посмотрим на пример дерева суффиксов для cdddcdc , если мы добавим ссылку суффикса в этом случае, а если нет:

  • Если мы НЕ делаем соединяем узлы через суффиксную ссылку:

    • перед добавлением последней буквы c :

    2019

102
ответ дан makagonov 29 янв. '13 в 12:57 2013-01-29 12:57

У меня было довольно много проблем для реализации этой структуры данных. В итоге я нашел эту статью и смог ее реализовать. Большим плюсом для этого является то, что у вас есть пошаговый пример для довольно длинной строки, чтобы вы могли видеть, что вам следует делать. Пожалуйста, взгляните на статью, и я буду более счастлив дать советы там, где это необходимо. Я не решаюсь выпустить еще одно полномасштабное объяснение, так как в интернете есть несколько довольно много.

19
ответ дан Ivaylo Strandjev 26 февр. '12 в 14:59 2012-02-26 14:59

Моя интуиция такова:

После k итераций основного цикла вы создали дерево суффикса, которое содержит все суффиксы полной строки, начинающиеся с первых k символов.

В начале это означает, что дерево суффикса содержит один корень node, который представляет всю строку (это единственный суффикс, начинающийся с 0).

После итераций len (string) у вас есть дерево суффикса, содержащее все суффиксы.

Во время цикла ключ является активной точкой. Я предполагаю, что это представляет собой самую глубокую точку в дереве суффиксов, которая соответствует правильному суффиксу первых k символов строки. (Я считаю, что правильно означает, что суффикс не может быть всей строкой.)

Например, предположим, что вы видели символы abcabc. Активная точка будет представлять точку в дереве, соответствующую суффиксу "abc".

Активная точка представлена ​​(origin, first, last). Это означает, что вы в данный момент находитесь в точке дерева, к которому вы подключились, начиная с начала node и затем подавая символы в строке [first: last]

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

Примечание 1: Указатели суффиксов дают ссылку на следующее кратчайшее соответствие для каждого node.

Примечание 2: Когда вы добавляете новый node и резервную копию, вы добавляете новый указатель суффикса для нового node. Назначением для этого указателя суффикса будет node в сокращенной активной точке. Этот node будет либо уже существовать, либо быть создан на следующей итерации этого резервного цикла.

Примечание 3: часть канонизации просто экономит время при проверке активной точки. Например, предположим, что вы всегда использовали origin = 0 и просто изменили первый и последний. Чтобы проверить активную точку, вам нужно будет следовать дереву суффикса каждый раз по всем промежуточным узлам. Имеет смысл кэшировать результат этого пути, записывая только расстояние от последнего node.

Можете ли вы привести пример кода того, что вы подразумеваете под "фиксировать" ограничивающие переменные?

Предупреждение о безопасности: я также нашел этот алгоритм особенно трудным для понимания, поэтому, пожалуйста, поймите, что эта интуиция, вероятно, будет неправильной во всех важных деталях...

6
ответ дан Peter de Rivaz 26 февр. '12 в 23:16 2012-02-26 23:16

Привет, я попытался реализовать описанную выше процедуру в рубине, пожалуйста, проверьте ее. он работает нормально.

Единственная разница в реализации заключается в том, что я попытался использовать объект edge вместо простого использования символов.

его также присутствует в https://gist.github.com/suchitpuri/9304856

  require 'pry' class Edge attr_accessor :data , :edges , :suffix_link def initialize data @data = data @edges = [] @suffix_link = nil end def find_edge element self.edges.each do |edge| return edge if edge.data.start_with? element end return nil end end class SuffixTrees attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder def initialize @root = Edge.new nil @active_point = { active_node: @root , active_edge: nil , active_length: 0} @remainder = 0 @pending_prefixes = [] @last_split_edge = nil @remainder = 1 end def build string string.split("").each_with_index do |element , index| add_to_edges @root , element update_pending_prefix element add_pending_elements_to_tree element active_length = @active_point[:active_length] # if(@active_point[:active_edge]  @active_point[:active_edge].data  @active_point[:active_edge].data[0..active_length-1] == @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1]) # @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1] # @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data) # end if(@active_point[:active_edge]  @active_point[:active_edge].data  @active_point[:active_edge].data.length == @active_point[:active_length] ) @active_point[:active_node] = @active_point[:active_edge] @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) @active_point[:active_length] = 0 end end end def add_pending_elements_to_tree element to_be_deleted = [] update_active_length = false # binding.pry if( @active_point[:active_node].find_edge(element[0]) != nil) @active_point[:active_length] = @active_point[:active_length] + 1 @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil @remainder = @remainder + 1 return end @pending_prefixes.each_with_index do |pending_prefix , index| # binding.pry if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil @active_point[:active_node].edges << Edge.new(element) else @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge] == nil data = @active_point[:active_edge].data data = data.split("") location = @active_point[:active_length] # binding.pry if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil ) else #tree split split_edge data , index , element end end end end def update_pending_prefix element if @active_point[:active_edge] == nil @pending_prefixes = [element] return end @pending_prefixes = [] length = @active_point[:active_edge].data.length data = @active_point[:active_edge].data @remainder.times do |ctr| @pending_prefixes << data[-(ctr+1)..data.length-1] end @pending_prefixes.reverse! end def split_edge data , index , element location = @active_point[:active_length] old_edges = [] internal_node = (@active_point[:active_edge].edges != nil) if (internal_node) old_edges = @active_point[:active_edge].edges @active_point[:active_edge].edges = [] end @active_point[:active_edge].data = data[0..location-1].join @active_point[:active_edge].edges << Edge.new(data[location..data.size].join) if internal_node @active_point[:active_edge].edges << Edge.new(element) else @active_point[:active_edge].edges << Edge.new(data.last) end if internal_node @active_point[:active_edge].edges[0].edges = old_edges end #setup the suffix link if @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data @last_split_edge.suffix_link = @active_point[:active_edge] end @last_split_edge = @active_point[:active_edge] update_active_point index end def update_active_point index if(@active_point[:active_node] == @root) @active_point[:active_length] = @active_point[:active_length] - 1 @remainder = @remainder - 1 @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1]) else if @active_point[:active_node].suffix_link != nil @active_point[:active_node] = @active_point[:active_node].suffix_link else @active_point[:active_node] = @root end @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0]) @remainder = @remainder - 1 end end def add_to_edges root , element return if root == nil root.data = root.data + element if(root.data and root.edges.size == 0) root.edges.each do |edge| add_to_edges edge , element end end end suffix_tree = SuffixTrees.new suffix_tree.build("abcabxabcd") binding.pry 
3
ответ дан Suchit Puri 02 марта '14 в 13:54 2014-03-02 13:54

@jogojapan вы принесли удивительное объяснение и визуализацию. Но поскольку @makagonov упомянул об отсутствии некоторых правил относительно установки суффикс-ссылок. Это видно красиво, когда шаг за шагом на http://brenden.github.io/ukkonen-animation/ через слово aabaaabb. Когда вы переходите от шага 10 к шагу 11, нет суффикса связи от node 5 до node 2, но активная точка внезапно перемещается туда.

@makagonov, так как я живу в мире Java, я также попытался выполнить вашу реализацию, чтобы понять рабочий процесс ST, но мне было трудно:

  • объединение ребер с узлами
  • с помощью указателей указателей вместо ссылок
  • разрывает утверждения;
  • инструкции продолжения;

Итак, у меня появилась такая реализация на Java, которая, я надеюсь, будет более четко отражать все шаги и сократит время обучения для других людей Java:

 import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class ST { public class Node { private final int id; private final Map<Character, Edge> edges; private Node slink; public Node(final int id) { this.id = id; this.edges = new HashMap<>(); } public void setSlink(final Node slink) { this.slink = slink; } public Map<Character, Edge> getEdges() { return this.edges; } public Node getSlink() { return this.slink; } public String toString(final String word) { return new StringBuilder() .append("{") .append("\"id\"") .append(":") .append(this.id) .append(",") .append("\"slink\"") .append(":") .append(this.slink != null ? this.slink.id : null) .append(",") .append("\"edges\"") .append(":") .append(edgesToString(word)) .append("}") .toString(); } private StringBuilder edgesToString(final String word) { final StringBuilder edgesStringBuilder = new StringBuilder(); edgesStringBuilder.append("{"); for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) { edgesStringBuilder.append("\"") .append(entry.getKey()) .append("\"") .append(":") .append(entry.getValue().toString(word)) .append(","); } if(!this.edges.isEmpty()) { edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1); } edgesStringBuilder.append("}"); return edgesStringBuilder; } public boolean contains(final String word, final String suffix) { return !suffix.isEmpty()  this.edges.containsKey(suffix.charAt(0))  this.edges.get(suffix.charAt(0)).contains(word, suffix); } } public class Edge { private final int from; private final int to; private final Node next; public Edge(final int from, final int to, final Node next) { this.from = from; this.to = to; this.next = next; } public int getFrom() { return this.from; } public int getTo() { return this.to; } public Node getNext() { return this.next; } public int getLength() { return this.to - this.from; } public String toString(final String word) { return new StringBuilder() .append("{") .append("\"content\"") .append(":") .append("\"") .append(word.substring(this.from, this.to)) .append("\"") .append(",") .append("\"next\"") .append(":") .append(this.next != null ? this.next.toString(word) : null) .append("}") .toString(); } public boolean contains(final String word, final String suffix) { if(this.next == null) { return word.substring(this.from, this.to).equals(suffix); } return suffix.startsWith(word.substring(this.from, this.to))  this.next.contains(word, suffix.substring(this.to - this.from)); } } public class ActivePoint { private final Node activeNode; private final Character activeEdgeFirstCharacter; private final int activeLength; public ActivePoint(final Node activeNode, final Character activeEdgeFirstCharacter, final int activeLength) { this.activeNode = activeNode; this.activeEdgeFirstCharacter = activeEdgeFirstCharacter; this.activeLength = activeLength; } private Edge getActiveEdge() { return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter); } public boolean pointsToActiveNode() { return this.activeLength == 0; } public boolean activeNodeIs(final Node node) { return this.activeNode == node; } public boolean activeNodeHasEdgeStartingWith(final char character) { return this.activeNode.getEdges().containsKey(character); } public boolean activeNodeHasSlink() { return this.activeNode.getSlink() != null; } public boolean pointsToOnActiveEdge(final String word, final char character) { return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character; } public boolean pointsToTheEndOfActiveEdge() { return this.getActiveEdge().getLength() == this.activeLength; } public boolean pointsAfterTheEndOfActiveEdge() { return this.getActiveEdge().getLength() < this.activeLength; } public ActivePoint moveToEdgeStartingWithAndByOne(final char character) { return new ActivePoint(this.activeNode, character, 1); } public ActivePoint moveToNextNodeOfActiveEdge() { return new ActivePoint(this.getActiveEdge().getNext(), null, 0); } public ActivePoint moveToSlink() { return new ActivePoint(this.activeNode.getSlink(), this.activeEdgeFirstCharacter, this.activeLength); } public ActivePoint moveTo(final Node node) { return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength); } public ActivePoint moveByOneCharacter() { return new ActivePoint(this.activeNode, this.activeEdgeFirstCharacter, this.activeLength + 1); } public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node, final char character) { return new ActivePoint(node, character, this.activeLength - 1); } public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) { return new ActivePoint(this.getActiveEdge().getNext(), word.charAt(index - this.activeLength + this.getActiveEdge().getLength()), this.activeLength - this.getActiveEdge().getLength()); } public void addEdgeToActiveNode(final char character, final Edge edge) { this.activeNode.getEdges().put(character, edge); } public void splitActiveEdge(final String word, final Node nodeToAdd, final int index, final char character) { final Edge activeEdgeToSplit = this.getActiveEdge(); final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(), activeEdgeToSplit.getFrom() + this.activeLength, nodeToAdd); nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength), new Edge(activeEdgeToSplit.getFrom() + this.activeLength, activeEdgeToSplit.getTo(), activeEdgeToSplit.getNext())); nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null)); this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge); } public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode, final Node node) { if(previouslyAddedNodeOrAddedEdgeNode != null) { previouslyAddedNodeOrAddedEdgeNode.setSlink(node); } return node; } public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) { return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode); } } private static int idGenerator; private final String word; private final Node root; private ActivePoint activePoint; private int remainder; public ST(final String word) { this.word = word; this.root = new Node(idGenerator++); this.activePoint = new ActivePoint(this.root, null, 0); this.remainder = 0; build(); } private void build() { for(int i = 0; i < this.word.length(); i++) { add(i, this.word.charAt(i)); } } private void add(final int index, final char character) { this.remainder++; boolean characterFoundInTheTree = false; Node previouslyAddedNodeOrAddedEdgeNode = null; while(!characterFoundInTheTree  this.remainder > 0) { if(this.activePoint.pointsToActiveNode()) { if(this.activePoint.activeNodeHasEdgeStartingWith(character)) { activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode); characterFoundInTheTree = true; } else { if(this.activePoint.activeNodeIs(this.root)) { rootNodeHasNotEdgeStartingWithCharacter(index, character); } else { previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index, character, previouslyAddedNodeOrAddedEdgeNode); } } } else { if(this.activePoint.pointsToOnActiveEdge(this.word, character)) { activeEdgeHasCharacter(); characterFoundInTheTree = true; } else { if(this.activePoint.activeNodeIs(this.root)) { previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index, character, previouslyAddedNodeOrAddedEdgeNode); } else { previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index, character, previouslyAddedNodeOrAddedEdgeNode); } } } } } private void activeNodeHasEdgeStartingWithCharacter(final char character, final Node previouslyAddedNodeOrAddedEdgeNode) { this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode); this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character); if(this.activePoint.pointsToTheEndOfActiveEdge()) { this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(); } } private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) { this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null)); this.activePoint = this.activePoint.moveTo(this.root); this.remainder--; assert this.remainder == 0; } private Node internalNodeHasNotEdgeStartingWithCharacter(final int index, final char character, Node previouslyAddedNodeOrAddedEdgeNode) { this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null)); previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode); if(this.activePoint.activeNodeHasSlink()) { this.activePoint = this.activePoint.moveToSlink(); } else { this.activePoint = this.activePoint.moveTo(this.root); } this.remainder--; return previouslyAddedNodeOrAddedEdgeNode; } private void activeEdgeHasCharacter() { this.activePoint = this.activePoint.moveByOneCharacter(); if(this.activePoint.pointsToTheEndOfActiveEdge()) { this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(); } } private Node edgeFromRootNodeHasNotCharacter(final int index, final char character, Node previouslyAddedNodeOrAddedEdgeNode) { final Node newNode = new Node(idGenerator++); this.activePoint.splitActiveEdge(this.word, newNode, index, character); previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode); this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root, this.word.charAt(index - this.remainder + 2)); this.activePoint = walkDown(index); this.remainder--; return previouslyAddedNodeOrAddedEdgeNode; } private Node edgeFromInternalNodeHasNotCharacter(final int index, final char character, Node previouslyAddedNodeOrAddedEdgeNode) { final Node newNode = new Node(idGenerator++); this.activePoint.splitActiveEdge(this.word, newNode, index, character); previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode); if(this.activePoint.activeNodeHasSlink()) { this.activePoint = this.activePoint.moveToSlink(); } else { this.activePoint = this.activePoint.moveTo(this.root); } this.activePoint = walkDown(index); this.remainder--; return previouslyAddedNodeOrAddedEdgeNode; } private ActivePoint walkDown(final int index) { while(!this.activePoint.pointsToActiveNode()  (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) { if(this.activePoint.pointsAfterTheEndOfActiveEdge()) { this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index); } else { this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(); } } return this.activePoint; } public String toString(final String word) { return this.root.toString(word); } public boolean contains(final String suffix) { return this.root.contains(this.word, suffix); } public static void main(final String[] args) { final String[] words = { "abcabcabc$", "abc$", "abcabxabcd$", "abcabxabda$", "abcabxad$", "aabaaabb$", "aababcabcd$", "ababcabcd$", "abccba$", "mississipi$", "abacabadabacabae$", "abcabcd$", "00132220$" }; Arrays.stream(words).forEach(word -> { System.out.println("Building suffix tree for word: " + word); final ST suffixTree = new ST(word); System.out.println("Suffix tree: " + suffixTree.toString(word)); for(int i = 0; i < word.length() - 1; i++) { assert suffixTree.contains(word.substring(i)) : word.substring(i); } }); } } 
0
ответ дан Kamil 21 апр. '17 в 17:22 2017-04-21 17:22

Другие вопросы по меткам или Задайте вопрос