8

Android用のソフトキーボードを開発したいのですが、入力文字と辞書からの単語の文字がキーボードの隣にあるかどうかに基づいて提案を行うオートコレクトアルゴリズムをすでに取得しています。これは、レーベンシュタインアルゴリズムと組み合わせて機能します（文字を別の文字に置き換える必要がある場合は、それらが隣接しているかどうかがチェックされます）。そのため、このチェックは非常に頻繁に呼び出されます。現在、自動修正に費やされる時間の50％を消費しています。

私の現在のアプローチは、3層の別々のトライです。最初のレイヤー：最初のキャラクター。2番目のレイヤー：2番目のキャラクター：3番目のレイヤー：キャラクターが隣人である場合に情報を保持するブール値。しかし、私はトライがやり過ぎだと思いますか？すべての子供のためのインターンハッシュマップもそれを遅くするかもしれませんか？独自のcharToNumber関数を使用してハッシュマップを作成する必要がありますか？

これをどのように行いますか？どのボトルネックを回避できますか？Character.toLowerCase（）は、チェックが実行されるたびに呼び出される場合にも非効率的であるように見えます。

私はあなたが私が仕事をスピードアップするのを手伝ってくれることを願っています:)

4

4 に答える 4

6

キーボード上で2つの文字が隣り合っているかどうかを確認したいだけですか？キャラクターから隣接するキャラクターのセットへのマップを使用してみませんか？効率的なデータ構造を使用すると、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

これは非常に効率的で、ループやsのような複雑な計算がないはずhashCodeです。もちろん、テーブルを手動で初期化する必要があります。これは、アプリケーションの起動時に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);
}

a isneighbour bこのアルゴリズムは、その場合、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 に答える