以前どっかの仕事で必要になったので休日に書いたコードです。
どうしても期待するパフォーマンスが出なくて試行錯誤の結果こうなりました。トライ木というデータ構造の名前がついているのは後から知ったもの。（http://ja.wikipedia.org/wiki/トライ木）
マッチするかどうかのインターフェイスを以下のように定義するとして、
Macher.java
package search;
/**
* 文字列に対するマッチ処理を行うためのインターフェイス。
*/
public interface Matcher {
boolean match(String target);
}
こんな感じのコードを用意。
TreeMacher.java
package search;
import java.util.HashMap;
import java.util.Map;
/**
* マッチ対象の文字列集合を前処理し、ツリー構造で保持する。
* NGワードチェックなど、マッチ対象の文字列集合がほぼ静的に決定されるケースで高速に動作する。
*/
public class TreeMatcher implements Matcher{
private CharTreeNode rootNode = null;
public TreeMatcher(String[] words){
this.rootNode = new CharTreeNode(null);
this.rootNode.addWords(words);
}
/**
* マッチ処理を行う。
*/
public boolean match(String target){
CharTreeNode currentNode = null;
for(int i=0;i<target.length();i++){
currentNode = this.rootNode;
for(int k=0;i+k<target.length();k++){
Character c = target.charAt(i+k);
currentNode = currentNode.child.get(c);
if(currentNode == null){
break;
}
if(currentNode.end){
return true;
}
}
}
return false;
}
/**
* ツリー構造を保持する内部クラス。
*
*/
static class CharTreeNode {
boolean end = false;
Character value;
Map<Character,CharTreeNode> child = new HashMap<Character, CharTreeNode>();
CharTreeNode(Character value){
this.value = value;
}
void addWords(String[] words){
for(String word : words){
this.addWord(word);
}
}
void addWord(String word){
addWord(word,this);
}
static void addWord(String value, CharTreeNode parent){
if(value == null || value.length() < 1){
parent.end = true;
return;
}
if(parent == null || parent.end){
return;
}
Character firstLetter = value.charAt(0);
CharTreeNode current = null;
if(parent.child.containsKey(firstLetter)){
current = parent.child.get(firstLetter);
}else{
current = new CharTreeNode(firstLetter);
parent.child.put(firstLetter,current);
}
current.addWord(value.substring(1,value.length()));
}
}
}
マッチさせたい文字列のパターンが数万とかあったりする時、ベタな String#contains によるチェック処理の100倍くらいのパフォーマンスが出ます。
ただ前処理が重いのとメモリ食います。
ご利用は計画的に。