[Javascript] خوارزمية شجرة لاحقة Ukkonen في سهل الانجليزية


Answers

حاولت تنفيذ Suffix Tree بالطريقة المذكورة في إجابة jogojapan ، ولكنها لم تنجح في بعض الحالات بسبب الصياغة المستخدمة للقواعد. علاوة على ذلك ، لقد ذكرت أنه لم يتمكن أحد من تنفيذ شجرة لاحقة صحيحة تمامًا باستخدام هذا الأسلوب. أدناه سأكتب "نظرة عامة" على إجابة jogojapan مع بعض التعديلات على القواعد. سوف أصف أيضًا الحالة عندما ننسى إنشاء روابط لاحقة مهمة .

المتغيرات الإضافية المستخدمة

  1. نقطة نشطة - ثلاثية (active_node ؛ active_edge ؛ active_length) ، تظهر من حيث يجب أن نبدأ في إدخال لاحقة جديدة.
  2. الباقي - يعرض عدد اللواحق التي يجب إضافتها بشكل صريح . على سبيل المثال ، إذا كانت كلمتنا هي "abcaabca" ، والباقي = 3 ، فهذا يعني أنه يجب علينا معالجة 3 لاحقات أخيرة : bca ، ca و a .

دعونا نستخدم مفهوم عقدة داخلية - جميع العقد ، باستثناء الجذر والأوراق هي العقد الداخلية .

الملاحظة 1

عندما تكون اللاحقة النهائية التي نحتاج لإدخالها موجودة في الشجرة بالفعل ، فإن الشجرة نفسها لم تتغير على الإطلاق (نقوم فقط بتحديث active point remainder ).

الملاحظة 2

إذا كان active_length نقطة ما أكبر أو مساوياً لطول الحافة الحالية ( edge_length ) ، فإننا نقوم بنقل edge_length active point لأسفل حتى تكون edge_length أكبر من active_length .

الآن ، دعنا نعيد تعريف القواعد:

المادة 1

إذا كان بعد الإدراج من العقدة النشطة = الجذر ، يكون الطول النشط أكبر من 0 ، ثم:

  1. العقدة النشطة لا تتغير
  2. طول نشط هو decremented
  3. يتم إزاحة الحافة النشطة (إلى الحرف الأول لللاحقة التالية التي يجب إدراجها)

القاعدة 2

إذا قمنا بإنشاء عقدة داخلية جديدة أو جعل الواقي من العقدة الداخلية ، وليست هذه أول عقدة داخلية من نوع SUCH في الخطوة الحالية ، فسنقوم بربط عقدة SUCH السابقة بهذا الوصلة من خلال وصلة لاحقة .

هذا التعريف Rule 2 يختلف عن jogojapan ، حيث أننا لا نأخذ بعين الاعتبار العقد الداخلية التي تم إنشاؤها حديثًا فحسب ، بل أيضًا العقد الداخلية ، التي ندخل منها.

القاعدة 3

بعد إدخال من العقدة النشطة التي ليست العقدة الجذرية ، يجب أن نتبع رابط اللاحقة وضبط العقدة النشطة إلى العقدة التي تشير إليها. إذا لم يكن هناك رابط لاحقة ، فاضبط العقدة النشطة على عقدة الجذر . وفي كلتا الحالتين ، تبقى الحافة النشطة والطول النشط دون تغيير.

في هذا التعريف Rule 3 نأخذ بعين الاعتبار أيضًا إدراجات العقد الورقية (وليس فقط العقد المقسمة).

وأخيرًا ، الملاحظة 3:

عندما يكون الرمز الذي نريد إضافته إلى الشجرة موجودًا بالفعل على الحافة ، نقوم ، وفقًا Observation 1 ، بتحديث active point remainder ، تاركًا الشجرة دون تغيير. ولكن إذا كانت هناك عقدة داخلية تم تحديدها بأنها تحتاج إلى وصلة لاحقة ، فيجب أن نربط تلك العقدة مع active node الحالية من خلال وصلة لاحقة.

دعنا ننظر إلى مثال شجرة لاحقة لـ cdddcdc إذا قمنا بإضافة ارتباط لاحقة في مثل هذه الحالة وإذا لم نفعل ذلك:

  1. إذا لم نقم بتوصيل العقد من خلال رابط لاحقة:

    • قبل إضافة الحرف الأخير c :

    • بعد إضافة الحرف الأخير c :

  2. إذا قمنا بتوصيل العقد من خلال وصلة لاحقة:

    • قبل إضافة الحرف الأخير c :

    • بعد إضافة الحرف الأخير c :

يبدو أنه لا يوجد فرق كبير: في الحالة الثانية هناك رابطان لاحقتان إضافيتان. لكن هذه الروابط لاحقة صحيحة ، وواحد منها - من العقدة الزرقاء إلى اللون الأحمر - مهم جدا لنهجنا مع نقطة نشطة . المشكلة هي أنه إذا لم نقم بوضع رابط لاحقة هنا ، لاحقًا ، عندما نضيف بعض الأحرف الجديدة إلى الشجرة ، قد نلغي إضافة بعض العقد إلى الشجرة بسبب Rule 3 ، لأنه ، وفقًا لذلك ، لا رابط لاحقة ، ثم يجب علينا وضع active_node على الجذر.

عندما كنا نضيف الحرف الأخير إلى الشجرة ، كانت العقدة الحمراء موجودة بالفعل قبل أن نقوم بإدخال جزء من العقدة الزرقاء (الحافة المسجلة "c" ). نظرًا لوجود إدراج من العقدة الزرقاء ، فإننا نضع علامة على أنه يحتاج إلى وصلة لاحقة . بعد ذلك ، بالاعتماد على نهج النقطة النشطة ، تم تعيين active node إلى العقدة الحمراء. ولكننا لا نقوم بإدخال جزء من العقدة الحمراء ، حيث أن الحرف 'c' موجود بالفعل على الحافة. هل هذا يعني أنه يجب ترك العقدة الزرقاء بدون رابط لاحقة؟ لا ، يجب أن نربط العقدة الزرقاء باللون الأحمر من خلال وصلة لاحقة. لماذا هذا صحيح؟ لأن نهج النقطة النشطة يضمن وصولنا إلى المكان المناسب ، أي إلى المكان التالي حيث يجب علينا معالجة إدخال لاحقة أقصر .

أخيرًا ، إليك تطبيقاتي الخاصة بـ Suffix Tree:

  1. Java
  2. C++

نأمل أن تساعد هذه "النظرة العامة" جنبا إلى جنب مع الإجابة المفصلة لجوجوجابان شخصًا ما على تنفيذ شجرة لاحقة خاصة به.

Question

أشعر بقليل من السميك عند هذه النقطة. لقد أمضيت أياماً في محاولة لف رأسي حول بناء شجرة لاحقة بالكامل ، ولكن لأنني لا أملك خلفية رياضية ، فإن العديد من التفسيرات تستعصي عليّ عندما تبدأ في الاستخدام المفرط للرموز الرياضية. الأقرب إلى التفسير الجيد الذي وجدته هو البحث عن سلسلة سريعة مع أشجار لاحقة ، لكنه يتفوق على نقاط مختلفة وبعض جوانب الخوارزمية تبقى غير واضحة.

سيكون تفسيرا مفصلا لهذه الخوارزمية هنا على لا يقدر بثمن بالنسبة للعديد من الآخرين إلى جانب أنا ، أنا متأكد.

للرجوع إليها ، إليك ورقة Ukkonen حول الخوارزمية: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

فهمي الأساسي ، حتى الآن:

  • أحتاج إلى التكرار من خلال كل بادئة P لسلسلة معينة T
  • أحتاج إلى التكرار من خلال كل لاحقة S في البادئة P وإضافة ذلك إلى الشجرة
  • لإضافة لاحقة S إلى الشجرة ، أحتاج إلى التكرار من خلال كل حرف في S ، مع التكرارات التي تتكون إما من السير إلى أسفل فرع موجود يبدأ بنفس مجموعة الأحرف C في S ويحتمل أن تقسم الحافة إلى العقد التابعة عندما أكون الوصول إلى حرف مختلف في اللاحقة ، أو إذا لم يكن هناك حافة مطابقة للمشي. عندما لا يتم العثور على حافة مطابقة للمشي على C ، يتم إنشاء حافة أوراق جديدة لـ C.

يبدو أن الخوارزمية الأساسية هي O (n 2 ) ، كما هو موضح في معظم التفسيرات ، حيث أننا نحتاج إلى تخطي كل البادئات ، ثم نحتاج إلى المرور بكل اللواحق لكل بادئة. يبدو أن خوارزمية ukkonen فريدة من نوعها بسبب تقنية مؤشر اللاحقة التي يستخدمها ، على الرغم من أنني أعتقد أن هذا هو ما أواجه مشكلة في الفهم.

أواجه أيضًا مشكلة في الفهم:

  • بالضبط متى وكيف يتم تعيين "نقطة نشطة" واستخدامها وتغييرها
  • ما يجري مع جانب تقديس الخوارزمية
  • لماذا تحتاج عمليات التنفيذ التي رأيتها إلى "إصلاح" المتغيرات المحيطة التي يستخدمونها

هنا هو أكمل شفرة المصدر C # . لا يعمل فقط بشكل صحيح ، ولكنه يدعم التقسيم التلقائي ويعرض رسمًا نصيًا أجمل للإخراج. شفرة المصدر وناتج العينة في:

https://gist.github.com/2373868

التحديث 2017-11-04

بعد سنوات عديدة ، وجدت استخدامًا جديدًا لأشجار لاحقة ، ونفذت الخوارزمية في جافا سكريبت . جست هو أدناه. يجب أن يكون خالية من الأخطاء. npm install chalk إلى ملف js ، npm install chalk من نفس الموقع ، ثم قم بتشغيل مع node.js لمشاهدة بعض الإخراج الملونة. هناك نسخة مخففة في نفس Gist ، دون أي رمز التصحيح.

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




@jogojapan you brought awesome explanation and visualisation. But as @makagonov mentioned it's missing some rules regarding setting suffix links. It's visible in nice way when going step by step on http://brenden.github.io/ukkonen-animation/ through word 'aabaaabb'. When you go from step 10 to step 11, there is no suffix link from node 5 to node 2 but active point suddenly moves there.

@makagonov since I live in Java world I also tried to follow your implementation to grasp ST building workflow but it was hard to me because of:

  • combining edges with nodes
  • using index pointers instead of references
  • breaks statements;
  • continue statements;

So I ended up with such implementation in Java which I hope reflects all steps in clearer way and will reduce learning time for other Java people:

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);
        }
    });
  }
}



شكرا لشرح تعليمي بشكل جيد من قبل @ jogojapan ، نفذت الخوارزمية في بايثون.

تبين أن بعض المشاكل البسيطة التي ذكرهاjogojapan أكثر تعقيدًا مما توقعت ، ويجب أن يتم التعامل معه بحرص شديد. كلفني ذلك عدة أيام للحصول على تنفيذ قوي بما يكفي (على ما أظن). المشاكل والحلول مدرجة أدناه:

  1. End with Remainder > 0 وتبين أن هذا الموقف يمكن أن يحدث أيضًا أثناء خطوة التكشف ، وليس فقط نهاية الخوارزمية بأكملها. عندما يحدث ذلك ، يمكننا ترك الباقي ، actnode ، actedge ، و actlength دون تغيير ، إنهاء الخطوة الحالية تتكشف ، وبدء خطوة أخرى إما من خلال الحفاظ على طي أو تتكشف اعتمادا على ما إذا كان شار القادم في السلسلة الأصلية في المسار الحالي أو ليس.

  2. نقاط قفزة فوق: عندما نتبع وصلة لاحقة ، قم بتحديث النقطة النشطة ، ثم ابحث عن أن مكون active_length الخاص بها لا يعمل بشكل جيد مع active_node الجديد. يجب أن نتقدم إلى المكان الصحيح لتقسيم ، أو إدراج ورقة. This process might be not that straightforward because during the moving the actlength and actedge keep changing all the way, when you have to move back to the root node , the actedge and actlength could be wrong because of those moves. We need additional variable(s) to keep that information.

The other two problems have somehow been pointed out by @managonov

  1. Split Could Degenerate When trying to split an edge, sometime you'll find the split operation is right on a node. That case we only need add a new leaf to that node, take it as a standard edge split operation, which means the suffix links if there's any, should be maintained correspondingly.

  2. Hidden Suffix Links There is another special case which is incurred by problem 1 and problem 2 . Sometimes we need to hop over several nodes to the right point for split, we might surpass the right point if we move by comparing the remainder string and the path labels. That case the suffix link will be neglected unintentionally, if there should be any. This could be avoided by remembering the right point when moving forward. The suffix link should be maintained if the split node already exists, or even the problem 1 happens during a unfolding step.

Finally, my implementation in Python is as follows:

Tips: It includes a naive tree printing function in the code above, which is very important while debugging . It saved me a lot of time and is convenient for locating special cases.