如果两个字符是键盘上的邻居,如何有效地检查？

Question

我想为Android开发一个软键盘,并且已经有了一个自动更正算法,如果输入字符和字典中单词的字符是键盘上的邻居,则根据事实提出建议.这与levenshtein算法结合使用(如果必须用不同的字符替换字符,则检查它们是否是邻居).这就是为什么经常调用此检查的原因.目前,它消耗了50%的自动更正时间.

我目前的做法是一个单独的三层,三层.第一层:第一个字符.第二层:第二个字符:第三层:如果字符是邻居,则保存信息的布尔值.但是我担心特里尼有点矫枉过正？每个孩子的实习生哈希图也会降低它的速度？我应该用自己的charToNumber函数构建一个hashmap吗？

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

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

Answer 1

您只想确定键盘上是否有两个字符相邻？为什么不使用从字符到一组相邻字符的地图？使用高效的数据结构时,您将获得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

这应该是非常有效的,没有循环和复杂的计算,如hashCodes.当然你必须手动初始化表,我建议在应用程序启动时从som外部配置文件中执行一次.

BTW整洁的想法!

Answer 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