8

我想为Android开发一个软键盘，并且已经有了一个自动更正算法，该算法根据输入字符和字典中单词的字符是否是键盘上的邻居这一事实提出建议。这与 levenshtein-algorithm 结合使用（如果必须将字符替换为不同的字符，则检查它们是否是邻居）。这就是为什么这个检查被非常频繁地调用。目前，它消耗了 50% 的时间用于自动更正。

我目前的方法是一个单独的 3 层树。第一层：第一个字符。第二层：第二个字符：第三层：布尔值，如果字符是邻居，则保存信息。但我担心尝试是矫枉过正？每个孩子的实习生哈希图也可能会减慢速度？我应该用自己的 charToNumber 函数构建哈希图吗？

你会怎么做？可以避免哪些瓶颈？每次执行检查时调用 Character.toLowerCase() 似乎也效率低下。

我希望你能帮助我加快任务:)

4

4 回答 4

6

您只想确定键盘上的两个字符是否彼此相邻？为什么不使用从一个字符到一组相邻字符的映射？当使用高效的数据结构时，您将获得O(1)时间 - 将数组用于映射（连续键空间 - 键的 ASCII 码），将BitSet用于一组相邻键。也非常紧凑。

这是一个示例代码：

BitSet[] adjacentKeys = new BitSet[127];

//initialize
adjacentKeys[(int) 'q'] = new BitSet(127);
adjacentKeys[(int) 'q'].set((int)'a');
adjacentKeys[(int) 'q'].set((int)'w');
adjacentKeys[(int) 'q'].set((int)'s');
//...

//usage
adjacentKeys[(int) 'q'].get((int) 'a');     //q close to a yields true
adjacentKeys[(int) 'q'].get((int) 'e');     //q close to e yields false

这应该非常hashCode有效，没有循环和像s这样的复杂计算。当然，您必须手动初始化表，我建议在应用程序启动时从 som 外部配置文件执行一次。

顺便说一句，好主意！

于 2011-08-16T13:57:53.733 回答
3

我真的很喜欢这个主意。

对于原始速度，您将使用大量switch声明。代码会很大，但没有比这更快的了：

public static boolean isNeighbour(char key1, char key2) {
    switch (key1) {
    case 'a':
        return key2 == 'w' || key2 == 'e' || key2 == 'd' || key2 == 'x' || key2 == 'z';
    case 'd':
        return key2 == 's' || key2 == 'w' || key2 == 'f' || key2 == 'c' || key2 == 'x';
    // etc
    default:
        return false;
    }
}


这是一种“标准”的方法，它仍然应该表现良好：

private static final Map<Character, List<Character>> neighbours =
    new HashMap<Character, List<Character>>() {{
    put('s', Arrays.asList('a', 'w', 'e', 'd', 'x', 'z')); 
    put('d', Arrays.asList('s', 'e', 'w', 'f', 'c', 'x'));
    // etc
}};

public static boolean isNeighbour(char key1, char key2) {
    List<Character> list = neighbours.get(key1);
    return list != null && list.contains(key2);
}

该算法没有利用 if a isneighbour bthen的事实b isneighbour a，而是为了代码的简单而牺牲了数据大小。

于 2011-08-16T14:00:58.167 回答
2

如何为每个键分配数字并使用它来确定接近度。

    public static void main(String[] args) {
    double[] d = new double[26];
    d['q'-97] = 100d;
    d['w'-97] = 101d;
    d['e'-97] = 102d;
    d['r'-97] = 103d;
    d['t'-97] = 104d;
    //(optionally, put a space of 5 between right hand and left hand for each row)
    d['y'-97] = 105d;
    d['u'-97] = 106d;
    d['i'-97] = 107d;
    d['o'-97] = 108d;
    d['p'-97] = 109d;


    //my keyboard middle row is about 20% indented from first row
    d['a'-97] = 200.2;
    d['s'-97] = 201.2;
    d['d'-97] = 202.2;
    d['f'-97] = 203.2;
    d['g'-97] = 204.2;
    d['h'-97] = 205.2;
    d['j'-97] = 206.2;
    d['k'-97] = 207.2;
    d['l'-97] = 208.2;

    //third row is about 50% indented from middle row
    d['z'-97] = 300.5;
    d['x'-97] = 301.5;
    d['c'-97] = 302.5;
    d['v'-97] = 303.5;
    d['b'-97] = 304.5;
    d['n'-97] = 305.5;
    d['m'-97] = 306.5;

    for (char a = 'a'; a <= 'z'; a++) {
        for (char b = 'a'; b <= 'z'; b++)
            if (a != b && prox(a,b,d))
                System.out.println(a + " and " + b + " are prox");
    }

}

static boolean prox(char a, char b, double m) {
    double a1 = m[a-97];
    double a2 = m[b-97];

    double d = Math.abs(a1-a2);
    //TODO: add in d == 5 if there is a spacing for left and right hand gap (since it's more unlikely of a crossover)
    return d == 0 || d == 1 || (d >= 99 && d <= 101);
}

部分输出：

a and q are prox
a and s are prox
a and w are prox
a and z are prox
....
g and b are prox
g and f are prox
g and h are prox
g and t are prox
g and v are prox
g and y are prox   
....
y and g are prox
y and h are prox
y and t are prox
y and u are prox
于 2011-08-16T19:13:43.920 回答
0

这是我的匈牙利语版本（如果有人需要的话）：

 public static boolean isHungarianNeighbour(int key1, int key2) {
    switch (key1) {
        case 'q':
            return key2 == 'w' || key2 == 's' || key2 == 'a' || key2 == '1' || key2 == '2';
        case 'w':
            return key2 == 'q' || key2 == '2' || key2 == '3' || key2 == 'e' || key2 == 's' || key2 == 'a';
        case 'e':
            return key2 == '3' || key2 == '4' || key2 == 'w' || key2 == 'r' || key2 == 's' || key2 == 'd';
        case 'r':
            return key2 == '4' || key2 == '5' || key2 == 'e' || key2 == 't' || key2 == 'd'|| key2 == 'f';
        case 't':
            return key2 == '5' || key2 == '6' || key2 == 'r' || key2 == 'z' || key2 == 'f' || key2 == 'g';
        case 'z':
            return key2 == '6' || key2 == '7' || key2 == 't' || key2 == 'u' || key2 == 'g' || key2 == 'h';
        case 'u':
            return key2 == '7' || key2 == '8' || key2 == 'z' || key2 == 'i' || key2 == 'h' || key2 == 'j';
        case 'i':
            return key2 == '8' || key2 == '9' || key2 == 'u' || key2 == 'o' || key2 == 'j' || key2 == 'k';
        case 'o':
            return key2 == '9' || key2 == 'ö' || key2 == 'i' || key2 == 'p' || key2 == 'k' || key2 == 'l';
        case 'p':
            return key2 == 'ö' || key2 == 'ü' || key2 == 'o' || key2 == 'ő' || key2 == 'l' || key2 == 'é';
        case 'ő':
            return key2 == 'ü' || key2 == 'ó' || key2 == 'p' || key2 == 'ú' || key2 == 'é' || key2 == 'á';
        case 'ú':
            return key2 == 'ó' || key2 == 'ő' || key2 == 'á' || key2 == 'ű';
        case 'a':
            return key2 == 'q' || key2 == 'w' || key2 == 's' || key2 == 'y' || key2 == 'í';
        case 's':
            return key2 == 'w' || key2 == 'e' || key2 == 'a' || key2 == 'd' || key2 == 'y' || key2 == 'x';
        case 'd':
            return key2 == 'e' || key2 == 'r' || key2 == 's' || key2 == 'f' || key2 == 'x' || key2 == 'c';
        case 'f':
            return key2 == 'r' || key2 == 't' || key2 == 'd' || key2 == 'g' || key2 == 'c' || key2 == 'v';
        case 'g':
            return key2 == 't' || key2 == 'z' || key2 == 'f' || key2 == 'h' || key2 == 'v' || key2 == 'b';
        case 'h':
            return key2 == 'z' || key2 == 'u' || key2 == 'g' || key2 == 'j' || key2 == 'b' || key2 == 'n';
        case 'j':
            return key2 == 'u' || key2 == 'i' || key2 == 'h' || key2 == 'k' || key2 == 'n' || key2 == 'm';
        case 'k':
            return key2 == 'i' || key2 == 'o' || key2 == 'j' || key2 == 'l' || key2 == 'm';
        case 'l':
            return key2 == 'o' || key2 == 'p' || key2 == 'k' || key2 == 'é';
        case 'é':
            return key2 == 'p' || key2 == 'ő' || key2 == 'l' || key2 == 'á';
        case 'á':
            return key2 == 'ő' || key2 == 'ú' || key2 == 'é' || key2 == 'ű';
        case 'ű':
            return key2 == 'á' || key2 == 'ú';
        case 'í':
            return key2 == 'a' || key2 == 'y';
        case 'y':
            return key2 == 'a' || key2 == 's' || key2 == 'í' || key2 == 'x';
        case 'x':
            return key2 == 's' || key2 == 'd' || key2 == 'y' || key2 == 'c';
        case 'c':
            return key2 == 'd' || key2 == 'f' || key2 == 'x' || key2 == 'v';
        case 'v':
            return key2 == 'f' || key2 == 'g' || key2 == 'c' || key2 == 'b';
        case 'b':
            return key2 == 'g' || key2 == 'h' || key2 == 'v' || key2 == 'n';
        case 'n':
            return key2 == 'h' || key2 == 'j' || key2 == 'b' || key2 == 'm';
        case 'm':
            return key2 == 'j' || key2 == 'k' || key2 == 'n' || key2 == '?';
        default:
            return false;
    }
}
于 2015-05-26T10:47:54.583 回答