Trie算法对字符串大文本快速查找

Trie算法能根据给定的字符串集合,对另一个大型字符串进行快速匹配查找,时间复杂度只与后者的长度有关,trie算法相对简单且实用。

Trie算法先对给定的字符串进行归集,形成一个多叉树形结构。

查找时,使用字符导航的方式进行匹配查找,因为,trie算法有很多变种,这里以最左(前缀)匹配或包含查找为例进行说明。

Trie算法优点

使用字符导航的查找方式,可以最大限度地减少字符比较过程,因此,也常被用在词频统计和字符串排序方面。

trie算法对文本主体只需遍历一次,最终复杂度降到O(n)。

Trie算法简版java实现

Trie算法的数据结构

--java-* class Node {
  Map<Character, Node> next;
}

Trie算法样本数据处理

public void add(String text) {
   if (text != null) {
    char[] ca = text.toCharArray();
    Node root = this;
    for (char c : ca) {
     root = root.put(c);
    }
   }
}

先对样本进行拆解

public Node put(char c) {
   emptySafe();
   Node node = next.get(c);
   if (node == null) {
    node = new Node();
    next.put(c, node);
   }
   return node;
}

对数据做归集

public void emptySafe() {
   if (next == null) {
    next = new HashMap(5);
   }
}

Trie检索字符算法

public boolean exist(String text) {
   if (emptyCheck(text)) {
    return false;
   }
   char[] ca = text.toCharArray();
   Node root = this;
   for (char c : ca) {
    if (root.next != null) {
     Node node = root.next.get(c);
     if (node != null) {
      root = node;
     }
     if (root.next == null) {
      return true;
     }
    }
   }
   return false;
}

不管是前缀还是包含查找,其过程都是顺藤摸瓜的方式;包含查找在遇到未匹配的字符时,会回到样本数据的根节点上,以便对其它样本做匹配。

举一个例子便知,有两个样本数据:/abc、bcd,被检索的字符串为:/ab/bcd

对于这种数据,以最左(前缀)方式查找是不会匹配的,在"包含"查找中,查找路径首先会因为/ab误入歧途,所以,在匹配无结果时需要回到根节点,以便能匹配到bcd。

下面是最左(前缀)匹配,相对比较简单就不多说了。

public boolean prefix(String text) {
   if (emptyCheck(text)) {
    return false;
   }
   char[] ca = text.toCharArray();
   Node root = this;
   for (char c : ca) {
    Node node = root.next.get(c);
    if (node == null) {
     return false;
    }
    root = node;
    if (root.next == null) {
     return true;
    }
   }
   return false;
}


public boolean emptyCheck(String text) {
   return (next == null || next.isEmpty() || text == null || text.isEmpty());
}

说明

示例算法中,对样本数据的唯一要求是,不能存在包含关系,如:ab、abc,对于这种情况的查找,如果最终期望匹配abc是没有问题的,但不可能匹配到ab。

最后,以一张网络上找到Trie算法图片,来结束这篇关于Trie算法的探讨。