私の理解では、アルファベットの入力文字列S（A1と呼びます）があり、それを別のアルファベットA2と同等の文字列S'に変換したいとします。実際、私が正しく理解していれば、Sと同等である可能性のある出力文字列のリスト[S'1、S'2、...、S'n]を生成したいと思うでしょう。
頭に浮かぶ1つのアプローチは、A2の有効な単語のリスト内の各単語に対して、に一致するA1の文字列のリストを生成することです。編集の例を使用すると、
px->ac
qy->ac
pr->ab
pr（わかりやすくするために、有効な単語を追加しました）
可能な一連の入力シンボルが常に有効な単語にマップされることがわかったので、テーブルを使用してTrieを作成できます。
各ノードは、トライのルートから現在のノードへのパスを形成するA1のシンボルのシーケンスにマップする、A2の有効な単語のリストへのポインターを保持します。
したがって、この例では、Trieは次のようになります。
Root (empty)
| a
|
V
+---Node (empty)---+
| b | c
| |
V V
Node (px,qy) Node (pr)
ルートノードから開始して、シンボルが消費されると、文字列全体を読み取るまで、現在のノードから、消費されたシンボルでマークされた子への遷移が行われます。そのシンボルに遷移が定義されていない場合、入力された文字列はトライに存在しないため、ターゲット言語の有効な単語にマップされません。それ以外の場合、プロセスの最後に、現在のノードに関連付けられている単語のリストは、入力文字列がマップされる有効な単語のリストになります。
トライを構築するための初期コスト（有効な単語のリストを変更したくない場合は、トライを事前に構築して出荷できます）とは別に、有効なマッピングのリストを見つけるには、入力の長さでO（n）が必要です。言葉。
Trieを使用すると、入力の最後に記号を追加することで生成できるすべての有効な単語のリストを検索できるという利点もあります。つまり、接頭辞の一致です。たとえば、入力記号「a」が指定されている場合、トライを使用して、「a」（「px」、「qr」、「py」）で始まるすべての有効な単語を検索できます。しかし、それを行うことは、完全に一致するものを見つけることほど速くはありません。
これが（Javaでの）解決策の簡単なハックです：
import java.util.*;
class TrieNode{
// child nodes - size of array depends on your alphabet size,
// her we are only using the lowercase English characters 'a'-'z'
TrieNode[] next=new TrieNode[26];
List<String> words;
public TrieNode(){
words=new ArrayList<String>();
}
}
class Trie{
private TrieNode root=null;
public void addWord(String sourceLanguage, String targetLanguage){
root=add(root,sourceLanguage.toCharArray(),0,targetLanguage);
}
private static int convertToIndex(char c){ // you need to change this for your alphabet
return (c-'a');
}
private TrieNode add(TrieNode cur, char[] s, int pos, String targ){
if (cur==null){
cur=new TrieNode();
}
if (s.length==pos){
cur.words.add(targ);
}
else{
cur.next[convertToIndex(s[pos])]=add(cur.next[convertToIndex(s[pos])],s,pos+1,targ);
}
return cur;
}
public List<String> findMatches(String text){
return find(root,text.toCharArray(),0);
}
private List<String> find(TrieNode cur, char[] s, int pos){
if (cur==null) return new ArrayList<String>();
else if (pos==s.length){
return cur.words;
}
else{
return find(cur.next[convertToIndex(s[pos])],s,pos+1);
}
}
}
class MyMiniTransliiterator{
public static void main(String args[]){
Trie t=new Trie();
t.addWord("ac","px");
t.addWord("ac","qy");
t.addWord("ab","pr");
System.out.println(t.findMatches("ac")); // prints [px,qy]
System.out.println(t.findMatches("ab")); // prints [pr]
System.out.println(t.findMatches("ba")); // prints empty list since this does not match anything
}
}
これは非常に単純なトライであり、圧縮や高速化は行われず、入力言語の小文字の英語文字でのみ機能します。ただし、他の文字セット用に簡単に変更できます。