Текстээс хайх Aho-Corasick алгоритм

Alfred V. Aho болон Margaret J. Corasick нарын эрдэмтэд 1975 онд зохиосон. Текстэн өгөгдлөөс олон дэд текстийг нэгэн зэрэг буюу параллель хайж олоход зорилго нь оршдог. Бичих, уншихад хялбар болгох үүднээс текстэн өгөгдлөө текст, хайж олох текстүүдээ үг гээд нэрлэчихье (Англиар харгалзан text, dictionary эсвэл text string, pattern string гэж нэрлэдэг).
Үг бүрээр давтаж, давталтын алхам бүрд текстийг эхнээс нь дуустал нь давтах байдлаар бол хэн ч олчихно л доо. Харамсалтай нь маш өндөр өртөгтэй, текст уртсаж, үг олшрох тусам тэсвэрлэхийн аргагүй удаан ажиллах учраас тэгж программ бичиж, хүнд хэрэглүүлнэ гэж бол ёстой гонж.
Бодит амьдралд ийм төрлийн ямар жишээнүүд байдаг вэ?

• Текстэн дэх товчилсон үг болон нэр томьёо бүрд тайлбар оруулах
• Утасны жагсаалт өгөгдсөн бол эздийг нь харгалзуулах
• Гений дарааллаас тодорхой бүтэцтэй генүүдийг илрүүлэх

г.м бичээд байвал дуусашгүй их юм бий.
Тэгээд яг яаж вэ?
    Гол санаа нь ижил эхлэлтэй үгнүүдийн давцхцал дээр суурилсан мод байгуулаад, хайлтын алхам бүрийн үр дүнг дараагийн алхамд хэрэглэх буюу текстийг эхнээс нь дуустал нэг л удаа давтаад бүх үгийг хайж олох явдал юм. Ж: 99073149, 88186877, 99073703, 99037154 дугааруудын мод доорх хэлбэртэй болно.

Энэ модыг trie гэж нэрлэдэг.(Retrieval гэдэг үгнээс авсан)
Trie байгуулах

• Мод нь Root буюу нэг үндэстэй байна. (Дээрх зургийн хувьд хараар будсан хамгийн дээд зангилаа)
• Үг бүрийн тэмдэгт бүрээр зангилаануудаа зурна. Ингэхдээ тухайн үгийн эхлэл өөр үгийн эхлэлтэй давцаж байгаа буюу ямар зангилаанууд нь ерөнхий байхыг хамгийн хурднаар тооцоолж зурах шаардлагатай.

Failure холбоос тодорхойлох
    Failure холбоос буюу failure link (suffix link) гэдэг нь аль нэг үгийн аль нэг хэсэг өөр үгнүүдийн эхлэл мөн эсэхийг тодорхойлсон холбоос юм. Жишээлбэл, this, history үгнүүдийн хувьд t + his + tory учраас his хэсгийг нэг л удаа хайна гэсэн үг.
this, issue, book, okay үгнүүдийн мод, failure холбоос нь доорх байдлаар зурагдана.

Уг алгоримтыг жава дээр доорх байдлаар нэвтрүүлж болно.

 public class AhoCorasick {  
      static class Result {  
           public String text;  
           public int endIndex;  
           @Override  
           public String toString() {  
                return String.format("%d: %s", endIndex, text);  
           }  
      }  
      Trie root = null;  
      static class Trie {  
           public String val = "";  
           public char ch = '#';  
           public Map<Character, Trie> next = new HashMap<Character, Trie>();  
           public Trie fail = null;  
      }  
      public void buildTree(String[] p) {  
           this.root = new Trie();  
           for (int i = 0; i < p.length; i++)  
                insert(p[i]);  
           buildFailure();  
      }  
      public void insert(String p) {  
           Trie t = root;  
           for (int i = 0; i < p.length(); i++) {  
                if (t.next.containsKey(p.charAt(i))) {  
                     t = t.next.get(p.charAt(i));  
                } else {  
                     Trie t1 = new Trie();  
                     t1.val = "";  
                     t1.ch = p.charAt(i);  
                     t.next.put(p.charAt(i), t1);  
                     t = t1;  
                }  
           }  
           t.val = p;  
      }  
      public void buildFailure() {  
           LinkedList<Trie> q = new LinkedList<>();  
           q.add(root);  
           while (!q.isEmpty()) {  
                Trie cur = q.pop();  
                for (Entry<Character, Trie> e : cur.next.entrySet()) {  
                     if (cur == root)  
                          e.getValue().fail = root;  
                     else {  
                          Trie p = cur.fail;  
                          while (p != null && !p.next.containsKey(e.getKey())) {  
                               p = p.fail;  
                          }  
                          if (p == null)  
                               cur.next.get(e.getKey()).fail = root;  
                          else  
                               cur.next.get(e.getKey()).fail = p.next.get(e.getKey());  
                     }  
                     q.add(cur.next.get(e.getKey()));  
                }  
           }  
      }  
      public List<Result> search(String s) {  
           List<Result> res = new ArrayList<>();  
           Result r;  
           Trie t = root;  
           for (int i = 0; i < s.length(); i++) {  
                while (!t.next.containsKey(s.charAt(i)) && t != root) {  
                     t = t.fail;  
                }  
                if (!t.next.containsKey(s.charAt(i))) {  
                     continue;  
                }  
                t = t.next.get(s.charAt(i));  
                Trie tt = t;  
                while (tt != root) {  
                     if (tt.val.length() > 0) {  
                          r = new Result();  
                          r.endIndex = i;  
                          r.text = tt.val;  
                          res.add(r);  
                     }  
                     tt = tt.fail;  
                }  
           }  
           return res;  
      }  
      @Override  
      public String toString() {  
           return this.toString(null, this.root, 0);  
      }  
      private String toString(Trie root, Trie t, int c) {  
           StringBuilder res = new StringBuilder();  
           String str;  
           if (root != null) {  
                str = "(" + t.ch + ", " + t.val + ") -> " + (t.fail != null ? t.fail.ch : '#');  
                if (c == 1)  
                     res.append("\n");  
                res.append(concatLeft(str, "  ", c - 1)).append("\n");  
           }  
           Set<Entry<Character, Trie>> entries = t.next.entrySet();  
           for (Entry<Character, Trie> e : entries) {  
                res.append(toString(t, e.getValue(), c + 1));  
           }  
           return res.toString();  
      }  
      public static String concatLeft(Object obj, String str, int count) {  
           String ret = String.valueOf(obj);  
           for (int i = 0; i < count; i++)  
                ret = str + ret;  
           return ret;  
      }  
 }  

Дээрх утасны дугааруудыг текстээс хайя.

 public static void main(String[] args) throws {  
           String[] p = { "99073149", "99073703", "99037154", "88186877" };  
           AhoCorasick aho = new AhoCorasick();  
           aho.buildTree(p);  
           System.out.println("Trie: " + aho.toString());  
           System.out.println(aho.search(  
                     "990731497891569907370346546599073149990738818687799073703789789798789990737036545645648818687712465"));  
 }  

Үр дүн

 Trie:   
 (8, ) -> #  
   (8, ) -> 8  
    (1, ) -> #  
      (8, ) -> 8  
       (6, ) -> #  
         (8, ) -> 8  
          (7, ) -> #  
            (7, 88186877) -> #  
 (9, ) -> #  
   (9, ) -> 9  
    (0, ) -> #  
      (3, ) -> #  
       (7, ) -> #  
         (1, ) -> #  
          (5, ) -> #  
            (4, 99037154) -> #  
      (7, ) -> #  
       (3, ) -> #  
         (1, ) -> #  
          (4, ) -> #  
            (9, 99073149) -> 9  
         (7, ) -> #  
          (0, ) -> #  
            (3, 99073703) -> #  
 Search result:  
 [7: 99073149, 21: 99073703, 35: 99073149, 48: 88186877, 56: 99073703, 76: 99073703, 93: 88186877]  

7, 21, 35... тоонууд тухайн үг текстийн аль хэсэгт агуулагдаж байгааг илэрхийлэх индекс (төгсгөлийн индекс).
Ихэнх хэл дээр дээрийнхтэй тун ижилхнээр бичиж нэвтрүүлэх боломжтой. Зарим хэл дээр нэвтрүүлсэн бэлэн сангууд байдаг. Тус аргыг ашиглаж https://www.hackerrank.com/challenges/determining-dna-health/problem бодлогыг бодож үзээрэй. Амжилт!