これは何？ †
- 某所で没になった、高速文字列置換プログラムです。
- アルゴリズム
プログラム †
- RootNode?.java
package com.snail;
public class RootNode extends Node{
/**
* 変換エントリーを追加する
* @param src 変換元
* @param dest 変換先
*/
public void addEntry(final String src,final String dest){
addEntry(src.toCharArray(),0,dest);
}
/**
* 文字列置換を行います
* @param src 変換元文字列
* @return 返還後文字列
*/
public synchronized String replace(final String src){
char[] srcCharArray = src.toCharArray();
StringBuilder dest = new StringBuilder();
for(int start=0;start<srcCharArray.length;){
Node node = searchNode(src.toCharArray(),start);
if( node == null ){
// startを起点とする置換エントリーが見つからなかった
dest.append(srcCharArray[start]);
start = start + 1;
}else{
// startを起点とする置換エントリーが見つかった
dest.append(node.getReplaceString());
start = start + node.getDepth();
}
}
return dest.toString();
}
}
- Node.java
package com.snail;
import java.util.HashMap;
import java.util.Map;
public class Node {
/**
* 置換元文字列の長さ(木構造の深さ)
*/
private int pDepth = 0;
/**
* 置き換え文字(無い場合にはnull)
*/
private String pReplaceString = null;
/**
* 子ノード
*/
private Map<Character, Node> pChildNodes = new HashMap<Character, Node>();
/**
* @return the replaceString
*/
public String getReplaceString() {
return pReplaceString;
}
/**
* @param replaceString the replaceString to set
*/
public void setReplaceString(String replaceString) {
pReplaceString = replaceString;
}
/**
* @return the childNodes
*/
public Map<Character, Node> getChildNodes() {
return pChildNodes;
}
/**
* @param childNodes the childNodes to set
*/
public void setChildNodes(Map<Character, Node> childNodes) {
pChildNodes = childNodes;
}
protected void addEntry(final char[] src, final int depth, final String dest) {
pDepth = depth;
if (src.length == depth) {
// 変換元文字列をすべて木構造に展開した
pReplaceString = dest;
return;
}
if (!pChildNodes.containsKey(src[depth])) {
pChildNodes.put(src[depth], new Node());
}
pChildNodes.get(src[depth]).addEntry(src, depth + 1, dest);
}
protected Node searchNode(final char[] src, final int depth) {
if (src.length == depth) {
// 文字列の末端に達した
return null;
}
if (pChildNodes.containsKey(src[depth])) {
// 続きがあるので検索を続行する
Node terminal = pChildNodes.get(src[depth]).searchNode(src, depth + 1);
if(terminal!=null){
// 変換候補が見つかった
return terminal;
}else{
// 最長一致を探そうとして失敗した場合
// 戻る途中で変換候補が見つかれば、それを変換候補とする
if(pReplaceString!=null){
return this;
}
}
}
if (pReplaceString == null) {
// 続きが無く、変換文字列もない場合
return null;
} else {
// 続きが無く、変換文字列がある場合(このノードが変換対象)
return this;
}
}
/**
* @return the depth
*/
public int getDepth() {
return pDepth;
}
/**
* @param depth the depth to set
*/
public void setDepth(int depth) {
pDepth = depth;
}
/**
* 木構造を標準出力にダンプします
*/
public void dumpTree() {
if (pReplaceString != null) {
System.out.println("→" + pReplaceString);
}else{
System.out.println("×");
}
for (Map.Entry<Character, Node> entry : pChildNodes.entrySet()) {
for (int cnt = 0; cnt < pDepth; cnt++) {
System.out.print("|");
}
System.out.print(entry.getKey());
entry.getValue().dumpTree();
}
}
}
使い方 †
package com.snail;
public class StrReplacerDriver {
public static String[][] replaceEntry = new String[][] { { "もえ", "萌え" },
{ "もえるごみ", "燃えるゴミ" } ,{"もえぷろ","燃えろプロ野球"}
};
public static String source = "もえるごみははげしくもえだした。";
/**
* @param args
*/
public static void main(String[] args) {
// 最長一致、木構造変換
RootNode root = new RootNode();
for (String[] entry : replaceEntry) {
root.addEntry(entry[0], entry[1]);
}
System.out.println("【木構造・最長一致置換】");
root.dumpTree();
System.out.println("----");
System.out.println("置換前："+source);
System.out.println("置換後："+root.replace(source));
System.out.println("-------------------------");
// 単純変換
System.out.println("【単純置換】");
String simpleReplaced = new String(source);
for (String[] entry : replaceEntry) {
System.out.println(entry[0]+"→"+entry[1]);
simpleReplaced = simpleReplaced.replaceAll(entry[0], entry[1]);
}
System.out.println("----");
System.out.println("置換前："+source);
System.out.println("置換後："+simpleReplaced);
}
}
Java#JavaSE
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
