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

Question

我正在寻找一种有效的数据结构/算法来存储和搜索基于音译的单词查找(比如google do:http://www.google.com/transliterate/但我不是试图使用google音译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,则可能的组合px, py, pz, qx, qy, qz在音译步骤1之后变为.在步骤2中,我们必须在有效单词列表中进行另一次搜索,并且除了px和之外必须消除它们中的每个人qy.

---

我目前所做的与上述方法没有什么不同.我没有使用音译表进行可能的组合,而是构建一个正则表达式[pq][xyz]并将其与我的有效单词列表进行匹配,后者提供输出px和qy.

我很想知道是否有更好的方法.

Answer 1

据我了解，您有一个字母表中的输入字符串 S（我们称其为 A1），并且您希望将其转换为字符串 S'，这与另一个字母表 A2 中的字符串 S' 等效。实际上，如果我理解正确的话，您想要生成一个可能相当于 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），这需要 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
    }
}

这是一个非常简单的特里树，没有压缩或加速，并且仅适用于输入语言的小写英文字符。但可以轻松修改为其他字符集。