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

Question

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

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

对于复杂的语言，必须有更好的方法来实现这一点，例如拼音输入法是如何工作的？关于从哪里开始有什么建议吗？

提前致谢。

---

编辑：如果我理解正确，这是@Dialecticus建议的-

我想从Language1（有3个字符a,b,c）音译到Language2< /strong>，有 6 个字符 p,q,r,x,y,z。由于每种语言拥有的字符数量及其音素不同，通常不可能定义一对一的映射。

让我们假设这里的语音是我们的关联数组/音译表：

a -> p, q
b -> r
c -> x, y, z

我们还有一个用于 Language2 的普通数组中的有效单词列表：

...
px
qy
...

如果用户输入 ac，则可能的组合将变为 <音译步骤 1 后的 code>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] ，它可能相当于 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)      

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

除了构建 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，没有压缩或加速，并且仅适用于输入语言的小写英文字符。但可以轻松修改为其他字符集。

Answer 2

我会一次构建一个符号的音译句子，而不是一次构建一个单词。对于大多数语言来说，可以独立于单词中的其他符号来音译每个符号。您仍然可以有作为完整单词的例外，必须音译为完整单词，但符号和例外的音译表肯定会小于所有现有单词的音译表。

音译表的最佳结构是某种关联数组，可能利用哈希表。在 C++ 中，有 std::unordered_map，并且在C# 您将使用 字典。