Насколько я понимаю, у вас есть входная строка S в алфавите (давайте назовем это A1), и вы хотите преобразовать ее в строку S ', которая эквивалентна в другом алфавите A2. На самом деле, если я правильно понимаю, вы хотите сгенерировать список [S'1, S'2, ..., S'n] выходных строк, которые потенциально могут быть эквивалентны S.
Один подход, который приходит на ум, заключается в том, что для каждого слова в списке допустимых слов в A2 генерируется список строк в A1, который соответствует. Используя пример в вашем редактировании, мы имеем
px->ac
qy->ac
pr->ab
(я добавил дополнительное действительное слово pr для ясности)
Теперь, когда мы знаем, какие возможные серии входных символов всегда будут отображаться в правильное слово, мы можем использовать нашу таблицу для построения Trie .
Каждый узел будет содержать указатель на список допустимых слов в A2, которые сопоставляются с последовательностью символов в A1, которые образуют путь от корня 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
}
}
Это очень простая процедура, без сжатия и ускорений, и она работает только с английскими буквами нижнего регистра для языка ввода. Но его можно легко изменить для других наборов символов.