我正在寻找一种有效的数据结构/算法，用于存储和搜索基于音译的单词查找(如谷歌做:http://www.google.com/transliterate/但我不打算使用谷歌音译API)。不幸的是，我正在尝试的自然语言没有实现任何声音索引，所以我只能靠自己。
对于一个开源项目，目前我使用普通数组来存储单词列表，并动态生成正则表达式(基于用户输入)来匹配它们。它工作得很好，但是正则表达式过于强大或资源密集，超出了我的需要。例如，如果我尝试将此解决方案移植到手持设备上，我担心它会消耗太多电池，因为使用正则表达式搜索数千个单词的成本太高了。
对于复杂的语言，一定有更好的方法来实现这一点，例如拼音输入法是如何工作的?有什么建议从哪里开始吗?提前感谢。
编辑:如果我理解正确的话，这是@Dialecticus建议的-
我想从Language1(有3个字符a,b,c)转写到Language2(有6个字符p,q,r,x,y,z)。由于每种语言所拥有的字符数量及其电话号码的差异，通常不可能定义一对一的映射。
让我们假设这是我们的关联数组/音译表:
a -> p, q
b -> r
c -> x, y, z
对于Language2:
，我们也有一个普通数组中的有效单词列表。...
px
qy
...
如果用户输入ac，则经过音译步骤1后可能的组合为px, py, pz, qx, qy, qz。在步骤2中，我们必须在有效的单词列表中进行另一次搜索，并且必须消除除px和qy之外的所有单词。
我现在所做的与上面的方法没有什么不同。我没有使用音译表进行可能的组合，而是构建一个正则表达式[pq][xyz]，并将其与我的有效单词列表进行匹配，该列表提供输出px和qy。
我很想知道是否有比那更好的方法。
据我所知，你有一个字母表中的输入字符串S(我们称之为A1)，你想把它转换成字符串S'，这是它在另一个字母表A2中的等效。实际上，如果我理解正确的话，你想要生成一个列表[S'1,S'2，…，S'n]的输出字符串，可能相当于S
想到的一种方法是，对于A2中有效单词列表中的每个单词，在A1中生成与。使用编辑中的示例，我们有
px->ac
qy->ac
pr->ab
(为了清晰，我添加了一个额外的有效词pr)
现在我们知道了输入符号的哪些序列可能总是映射到一个有效的单词，我们可以使用我们的表来构建一个Trie。
每个节点都持有一个指针，指向A2中有效单词的列表，这些单词映射到A1中形成从Trie根到当前节点的路径的符号序列。
因此，对于我们的示例，Trie看起来像这样 Root (empty)
| a
|
V
+---Node (empty)---+
| b | c
| |
V V
Node (px,qy) Node (pr)
从根节点开始，当符号被消耗时，从当前节点转移到标记有消耗符号的子节点，直到我们读取了整个字符串。如果在任何时候都没有为该符号定义转换，则输入的字符串在我们的树中不存在，因此不映射到目标语言中的有效单词。否则，在处理结束时，与当前节点关联的单词列表是输入字符串映射到的有效单词列表。
除了构建树的初始成本(如果我们不希望有效单词列表发生变化，则可以预先构建该树)之外，查找映射有效单词列表的输入长度为0 (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
}
}
这是一个非常简单的trie，没有压缩或加速，只适用于输入语言的小写英文字符。但它可以很容易地修改为其他字符集
我会一次构建一个符号，而不是一次构建一个单词。对于大多数语言来说，每个符号都可以独立于单词中的其他符号进行音译。您仍然可以将例外作为必须音译为完整单词的整个单词，但是符号和例外的音译表肯定会小于所有现有单词的音译表。
音译表的最佳结构是某种关联数组，可能使用哈希表。在c++中有std::unordered_map，在c#中你会使用Dictionary。