algorithm - 用于基于音译的单词查找的高效数据结构/算法

Question

我正在寻找一种有效的数据结构/算法来存储和搜索基于音译的单词查找(就像谷歌做的那样:http://www.google.com/transliterate/ 但我没有尝试使用谷歌音译 API)。不幸的是，我尝试使用的自然语言没有实现任何 soundex，所以我只能靠自己了。

对于一个开源项目，我目前使用纯数组来存储单词列表并动态生成正则表达式(基于用户输入)来匹配它们。它工作正常，但正则表达式太强大或占用资源太多，超出了我的需要。例如，如果我尝试将此解决方案移植到手持设备上，我担心它会耗尽太多电池电量，因为使用正则表达式搜索数千个单词的成本太高。

对于复杂的语言，必须有更好的方法来完成这个，例如拼音输入法是如何工作的？关于从哪里开始的任何建议？

提前致谢。

---

编辑:如果我理解正确，这是@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。

我很想知道是否有比这更好的方法。

Answer 1

据我了解，您有一个字母表中的输入字符串 S(我们称之为 A1)，您希望将其转换为字符串 S'，它在另一个字母表 A2 中是等效的。实际上，如果我理解正确的话，您想生成一个可能等同于 S 的输出字符串列表 [S'1,S'2,...,S'n]。

想到的一种方法是为 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)      

从根节点开始，随着符号被消耗，从当前节点到其标有被消耗符号的子节点进行转换，直到我们读取整个字符串。如果在任何时候都没有为该符号定义转换，则输入的字符串在我们的 trie 中不存在，因此不会映射到目标语言中的有效单词。否则，在过程结束时，与当前节点关联的单词列表是输入字符串映射到的有效单词列表。

除了构建 trie 的初始成本(如果我们不想更改有效单词列表，可以预先构建 trie)，这需要 O(n) 的输入长度来查找列表映射有效词。

使用 Trie 还提供了一个优势，您还可以使用它来查找所有有效单词的列表，这些单词可以通过在输入的末尾添加更多符号来生成 - 即前缀匹配。例如，如果输入符号“a”，我们可以使用 trie 查找所有以“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，没有压缩或加速，并且只适用于输入语言的小写英文字符。但它可以很容易地修改为其他字符集。