Massive Algorithms: Multiple Patterns Searching

Multiple Patterns Searching - Suffix Tree

Pattern Searching | Set 8 (Suffix Tree Introduction) | GeeksforGeeks

Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.

Preprocess Pattern or Preoprocess Text?
We have discussed the following algorithms in the previous posts:

KMP Algorithm
Rabin Karp Algorithm
Finite Automata based Algorithm
Boyer Moore Algorithm

All of the above algorithms preprocess the pattern to make the pattern searching faster. The best time complexity that we could get by preprocessing pattern is O(n) where n is length of the text. In this post, we will discuss an approach that preprocesses the text. A suffix tree is built of the text. After preprocessing text (building suffix tree of text), we can search any pattern in O(m) time where m is length of the pattern.
Imagine you have stored complete work of William Shakespeare and preprocessed it. You can search any string in the complete work in time just proportional to length of the pattern. This is really a great improvement because length of pattern is generally much smaller than text.
Preprocessing of text may become costly if the text changes frequently. It is good for fixed text or less frequently changing text though.

A Suffix Tree for a given text is a compressed trie for all suffixes of the given text. We have discussed Standard Trie. Let us understand Compressed Trie with the following array of words

Build suffix tree from search text(not from pattern).
A Suffix Tree for a given text is a compressed trie for all suffixes of the given text.
How to build a Suffix Tree for a given text?
1) Generate all suffixes of given text.
2) Consider all suffixes as individual words and build a compressed trie.
A Suffix Tree for a given text is a compressed trie for all suffixes of the given text.

How to build a Suffix Tree for a given text?

Following are all suffixes of “banana\0″

banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

If we consider all of the above suffixes as individual words and build a trie, we get following.

If we join chains of single nodes, we get the following compressed trie, which is the Suffix Tree for given text “banana\0″

How to search a pattern in the built suffix tree?
1) Starting from the first character of the pattern and root of Suffix Tree, do following for every character.
…..a) For the current character of pattern, if there is an edge from the current node of suffix tree, follow the edge.
…..b) If there is no edge, print “pattern doesn’t exist in text” and return.
2) If all characters of pattern have been processed, i.e., there is a path from root for characters of the given pattern, then print “Pattern found”.

Let us consider the example pattern as “nan” to see the searching process. Following diagram shows the path followed for searching “nan” or “nana”.

How does this work?
Every pattern that is present in text (or we can say every substring of text) must be a prefix of one of all possible suffixes. The statement seems complicated, but it is a simple statement, we just need to take an example to check validity of it.

Code:
https://www.ideserve.co.in/learn/pattern-matching-using-trie

    // we are only dealing with keys with chars 'a' to 'z'

    final static int ALPHABET_SIZE = 26;

    final static int NON_VALUE = -1;

    class TrieNode

{

        ArrayList<Integer> endingIndices;

        TrieNode[] children;

        TrieNode(boolean isLeafNode, int value)

{

            children = new TrieNode[ALPHABET_SIZE];

            this.endingIndices = new ArrayList();

}

}

    TrieNode root;

    TrieForPatternMatching()

{

        this.root = new TrieNode(false, NON_VALUE);

}

    private int getIndex(char ch)

{

        return ch - 'a';

}

    public void insert(String key, int offset)

{

        // null keys are not allowed

        if (key == null) return;

        key = key.toLowerCase();

        TrieNode currentNode = this.root;

        int charIndex = 0;

        while (charIndex < key.length())

{

            int childIndex = getIndex(key.charAt(charIndex));

            if (childIndex < 0 || childIndex >= ALPHABET_SIZE)

{

                System.out.println("Invalid Key");

                return;

}

            if (currentNode.children[childIndex] == null)

{

                currentNode.children[childIndex] = new TrieNode(false, NON_VALUE);

}

            currentNode = currentNode.children[childIndex];

            // add index for this alphabet where it ends in the string

            currentNode.endingIndices.add(charIndex + offset);

            charIndex  += 1;

}

}

    private  void matchAndPrintPattern(String str)

{

        if (str == null) return;

        TrieNode currentNode = root;

        int charIndex = 0; 

        while ((charIndex < str.length()))

{

            if (currentNode == null) break;

            currentNode = currentNode.children[getIndex(str.charAt(charIndex))];

            charIndex += 1;

}

        if (charIndex < str.length())

{

            System.out.println("Pattern does not exist.");

}

        else

{

            System.out.println("Pattern found in text starting at following indices..");

            for (int i = 0; i < currentNode.endingIndices.size(); i++)

{

                System.out.print(currentNode.endingIndices.get(i) - (str.length() - 1));

                System.out.print(",");

}

}

        return;

}

    private  void generateAndInsertSuffixes(String text)

{

        for (int i = 0; i < text.length(); i++)

{

            this.insert(text.substring(i), i);

}

}

    public void printPatternMatches(String text, String pattern)

{

        generateAndInsertSuffixes(text);

        matchAndPrintPattern(pattern);

}

http://massivealgorithms.blogspot.com/2015/07/cc150v4-208-full-text-search-suffix.html

 // 后缀树节点
 static class SuffixTreeNode {
  HashMap<Character, SuffixTreeNode> children = new HashMap<Character, SuffixTreeNode>();

  char value;
  ArrayList<Integer> indexes = new ArrayList<Integer>();

  public SuffixTreeNode() {
  }

  public void insertString(String s, int index) {
   indexes.add(index);
   if (s != null && s.length() > 0) {
    value = s.charAt(0);
    SuffixTreeNode child = null;
    if (children.containsKey(value)) {
     child = children.get(value);
    } else {
     child = new SuffixTreeNode();
     children.put(value, child);
    }
    String remainder = s.substring(1);
    child.insertString(remainder, index);
   }
  }

  public ArrayList<Integer> search(String s) {
   if (s == null || s.length() == 0) {
    return indexes;
   } else {
    char first = s.charAt(0);
    if (children.containsKey(first)) {
     String remainder = s.substring(1);
     return children.get(first).search(remainder);
    }
   }
   return null;
  }
 }

 // 后缀树
 static class SuffixTree {
  SuffixTreeNode root = new SuffixTreeNode();

  public SuffixTree(String s) {
   for (int i = 0; i < s.length(); i++) {
    String suffix = s.substring(i);
    root.insertString(suffix, i);
   }
  }

  public ArrayList<Integer> search(String s) {
   return root.search(s);
  }
 }

http://blog.csdn.net/at8008/arWticle/details/17256321
构造S的后缀树 - O(ns^2)

1. 后缀树类, 后缀树存了字符串S所有的后缀

public class SuffixTreeNode {
 // 当前root的孩子们
 // 若为英语小写字母，则最多有26个孩子
 HashMap<Character, SuffixTreeNode> children 
        = new HashMap<Character, SuffixTreeNode>();
 
 char value; // 当前节点的值
 
 // 存该后缀出现的起始位置,即多模式查找的结果
 // exp: S = bibs, T = b, 则 节点b的 indexes = [0,3]
 ArrayList<Integer> indexes = new ArrayList<Integer>();
 
 public SuffixTreeNode(){}
 
 public void insertString(String s, int index){
  indexes.add(index);  // 添加当前index
  if(s != null && s.length() > 0){
   value = s.charAt(0);
   SuffixTreeNode child = null;
   // 若root已经有这个value的孩子了,则将后缀附加到这个子节点树上
   if(children.containsKey(value)){
    child = children.get(value);
   }else{
    child = new SuffixTreeNode();
    children.put(value, child);
   }
   String remainder = s.substring(1);
   // 递归添加后缀
   child.insertString(remainder, index);
   
  }
 }
 
 public ArrayList<Integer> search(String s){
  if(s == null || s.length() == 0)
   return indexes;
  else{
   char first = s.charAt(0);
   if(children.containsKey(first)){
    String remainder = s.substring(1);
    return children.get(first).search(remainder);
   }
  }
  return null;
 }
}

Applications of Suffix Tree
1) Pattern Searching
1) Starting from the first character of the pattern and root of Suffix Tree, do following for every character.
…..a) For the current character of pattern, if there is an edge from the current node of suffix tree, follow the edge.
…..b) If there is no edge, print “pattern doesn’t exist in text” and return.
2) If all characters of pattern have been processed, i.e., there is a path from root for characters of the given pattern, then print “Pattern found”.
2) Finding the longest repeated substring
3) Finding the longest common substring
The longest common substrings of a set of strings can be found by building a generalised suffix tree for the strings, and then finding the deepest internal nodes which have leaf nodes from all the strings in the subtree below it.

The figure is the suffix tree for the strings "ABAB", "BABA" and "ABBA".

If the suffix tree is prepared for constant time lowest common ancestor retrieval, it can be solved in O(N) time.

4) Finding the longest palindrome in a string

Ukkonen’s Suffix Tree Construction is discussed in following articles: - O(n)
Ukkonen’s Suffix Tree Construction – Part 1
Ukkonen’s Suffix Tree Construction – Part 2
Ukkonen’s Suffix Tree Construction – Part 3
Ukkonen’s Suffix Tree Construction – Part 4
Ukkonen’s Suffix Tree Construction – Part 5
Ukkonen’s Suffix Tree Construction – Part 6

X. Suffix Tree Application 2 – Searching All Patterns
https://www.geeksforgeeks.org/suffix-tree-application-2-searching-all-patterns/

Read full article from Pattern Searching | Set 8 (Suffix Tree Introduction) | GeeksforGeeks

Multiple Patterns Searching - Suffix Tree

Labels

Popular Posts