Ich möchte eine Soft-Tastatur für Android entwickeln und habe bereits einen Autokorrektur-Algorithmus, der Vorschläge basierend auf der Tatsache macht, ob das Eingabezeichen und das Zeichen eines Wortes aus dem Wörterbuch Nachbarn auf der Tastatur sind. Dies funktioniert in Kombination mit dem Levenshtein-Algorithmus (wenn ein Zeichen durch ein anderes Zeichen ersetzt werden muss, wird geprüft, ob es sich um Nachbarn handelt). Deshalb wird dieser Check sehr häufig aufgerufen. Derzeit verbraucht es 50% der Zeit für die Autokorrektur.
Mein aktueller Ansatz ist ein separater Trie mit 3 Layern. Erste Schicht: erstes Zeichen. Zweite Ebene: Zweites Zeichen: Dritte Ebene: Boolescher Wert, der die Information enthält, wenn die Zeichen Nachbarn sind. Aber ich fürchte, ein Trie ist Overkill? Der Praktikant hashmaps für jede Kinder kann es auch verlangsamen? Soll ich eine hashmap mit eigener charToNumber-Funktion erstellen?
Wie würdest du das machen? Welche Engpässe können vermieden werden? Character.toLowerCase () scheint auch ineffizient zu sein, wenn es bei jeder Überprüfung aufgerufen wird.
Ich hoffe, Sie können mir helfen, die Aufgabe zu beschleunigen:)
Sie möchten nur bestimmen, ob zwei Zeichen auf der Tastatur nebeneinander stehen? Warum nicht eine Karte von einem Zeichen zu einem Satz benachbarter Zeichen verwenden? Wenn Sie effiziente Datenstrukturen verwenden, erhalten Sie O(1) time - verwenden Sie Array für eine Karte (kontinuierlicher Schlüsselraum - ASCII-Codes von Schlüsseln) und BitSet für eine Reihe von benachbarten Schlüsseln. Auch sehr kompakt.
Hier ist ein Beispielcode:
%Vor% Dies sollte sehr effizient sein, keine Schleifen und komplizierte Berechnungen wie hashCode s. Natürlich müssen Sie die Tabelle manuell initialisieren, ich würde empfehlen, dies beim Start der Anwendung von einer externen Konfigurationsdatei aus zu tun.
BTW nette Idee!
Ich mag die Idee wirklich.
Für rohe Geschwindigkeit würden Sie eine massive switch -Anweisung verwenden. Der Code wäre groß, aber es wäre nichts schneller:
Hier ist eine "Standard" -Methode, die immer noch gut funktionieren sollte:
Dieser Algorithmus nutzt nicht die Tatsache, dass wenn a isneighbour b , dann b isneighbour a , sondern die Datengröße für die Einfachheit des Codes opfert.
Tags und Links java keyboard levenshtein-distance neighbours