Je souhaite développer un clavier logiciel pour Android et avoir déjà un algorithme d'autocorrie qui fait des suggestions sur la base du fait que le caractère d'entrée et le caractère d'un mot du dictionnaire sont des voisins sur le clavier. Cela fonctionne en combinaison avec l'algorithme Levenshtein (si un caractère doit être remplacé par un caractère différent, il est vérifié si elles sont voisines). C'est pourquoi cette vérification s'appelle très fréquemment. Actuellement, il consomme 50% du temps passé à l'autocorrection.
Mon approche actuelle est une trie séparée avec 3 couches. Première couche: premier caractère. Deuxième couche: deuxième caractère: troisième couche: booléen tenant les informations si les personnages sont voisins. Mais j'ai bien peur qu'une trie soit trop grande? Les stagiaires pour chaque enfant peuvent également le ralentir, ainsi? Devrais-je construire un haschmap avec une fonction de chartonnombre propre?
Comment feriez-vous cela? Quels goulots d'étranglement peuvent être évités? Caractère.Tolowercase () semble être inefficace aussi bien quand on l'appelle chaque fois qu'un chèque est effectué.
J'espère que vous pourrez m'aider à accélérer la tâche :)
4 Réponses :
Vous voulez simplement déterminer si deux caractères sont côte à côte sur le clavier? Pourquoi ne pas utiliser une carte d'un caractère à un ensemble de caractères adjacents? Lorsque vous utilisez des structures de données efficaces, vous obtiendrez Voici un exemple de code: ceci doit être très efficace, pas de boucles et de calculs complexes tels que BTW NEUT IDEA! O (1) TEMPS - Utilisez une matrice pour une carte (espace clé en continu - Codes ASCII des touches) et Bitset pour un ensemble de clés adjacentes. Également très compact. hashcode s. Bien sûr, vous devez initialiser la table manuellement, je conseillerais de le faire une fois au démarrage de l'application du fichier de configuration externe SOM.
Et le gagnant est...!! : D J'ai essayé votre version et a couru toutes les combinaisons de caractères 1 000 000 fois. Votre code a pris 1752 ms. Le bloc-interrupteur brut 3596 ms. L'approche de proximité de Scott 7254 ms et mon origine Trie-approche incroyable 24 408 ms! Alors, merci beaucoup, Thomas :)
Ok, la nouvelle version de Scott est encore meilleure. Les différences de vitesse sont très intéressantes. Mais néanmoins: merci, Thomas!
J'aime vraiment l'idée.
Pour la vitesse brute, vous utiliseriez une instruction massive du commutateur code>. Le code serait grand, mais il n'y aurait rien de plus rapide: P> 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);
}
Pas sûr de cela, mais je soupçonne bitset sera plus rapide que la liste brute. Cependant, comme il n'y aura jamais plus de clés dans chaque liste d'adjacence, hashset n'est probablement pas le plus efficace et le plus compact de ce problème.
Premièrement, j'ai eu une énorme structure si elle n'était pas si rapide mais je viens de adapter votre approche de commutation (le travail a été effectué par le programme lui-même) et la vitesse est deux fois plus rapide que ma précédente approche trie. Merci pour ça! Mais je vais aussi essayer la suggestion Bitset / Hashset aussi. Merci pour toutes vos réponses rapides!
Qu'en est-il d'attribuer des chiffres à chaque touche et d'utiliser cela pour déterminer la proximité.
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
Très belle idée! Mais malheureusement, il est plus lent qu'un bloc de commutation brut respectivement que la version Bitset. Mais néanmoins: merci pour vous une suggestion intéressante!
Merci, il peut être optimisé et être beaucoup plus proche de la vitesse Bitset si le code est ajusté de l'utilisation d'un objet de carte à un double [] tableau. J'ai édité l'exemple à montrer. Question très intéressante!
Ok, maintenant je suis choqué. Heureusement, j'ai essayé votre nouvelle version. Il a fallu 469 ms pendant 1 000 000 points. Bitset a pris 1752 ms qui a également été une amélioration majeure par rapport à mon 24 408 ms-trie, mais votre version le basse. Merci beaucoup!
J'ai multiplié chaque valeur de 10 et modifié le type de variable en court. L'amélioration de la mémoire est probablement très petite mais l'amélioration de la vitesse mesure 23% de 23%!
Voici ma version hongroise (si quelqu'un en a besoin):
50% de temps en autocorrection semble être un nombre énorme, mais cela ne nous dit pas comment cela affecte l'expérience utilisateur. Combien de temps faut-il pour corriger un mot et combien de temps faut-il?
Actuellement, c'est une application Java normale depuis que je souhaite développer le moteur en premier (la vitesse d'émulateur Android ralentirait le développement;)). Une "recherche" moyenne prend 8 ms tandis que 40 ms sont consacrées à la vérification si les clés sont adjacentes. Mais mon ordinateur de bureau a obtenu 4x4 GHz. Je suppose donc que l'expérience utilisateur sur un smartphone de 1 GHz serait considérablement affectée, mais je dois toujours tester cela;)