Dynamischer Algorithmus für die automatische Korrektur von Text

Ich schreibe ein automatisch korrektes Programm, das die Levenshtein-Entfernung zur Korrektur verwendet eine Phrase von nicht mehr als 64 Zeichen basierend auf einem spezifischen Wörterbuch mit 8000 Wörtern.

Das Wörterbuch enthält in jeder Zeile das Paar "Word word_frequency". Ich verwende DictionarEntry-Objekte, um diese Paare zu speichern. Class Dictionar Entry hat zwei Felder: value: speichert die Wortfolge freq: speichert die Frequenz Das Wörterbuch wird als LinkedList gespeichert. Ich habe von der 64 Zeichen langen Zeichenfolge gelesen. vor der Verarbeitung entferne ich alle Leerzeichen. "Coo lweather" - & gt; "Cooles Wetter" Ich habe festgestellt, dass die Levenshtein-Distanz für jedes Präfix in der letzten Zeile der Matrix, berechnet durch die Levenshtein-Dynamik, berechnet werden muss (siehe Wikipedia-Beispiel). Es gibt die Entfernungen für alle Präfixe zurück.

Die Funktion lev gibt einen Vektor zurück, der den Abstand von der zweiten Parameterzeichenfolge zu allen Präfixen des ersten, einschließlich sich selbst, enthält.

Mein Problem ist, dass ich ein paar zusätzliche Regeln beachten muss: min lev. Entfernung - & gt; min Anzahl der Wörter - & gt; maximale Frequenzsumme - & gt; mindestens lexikographisch  Dies würde so erklärt, als ob die Gesamtzahl der Lösungen größer als 1 wäre wir nehmen diejenigen mit der minimalen Anzahl von Wörtern. Wenn es noch mehr als eins gibt, folgen wir der Liste der Regeln.

Die Dynamik, die ich anwende, ähnelt einer Rucksackdynamik.  Ich weiß nicht, wie man die Mindestzahl von Wörtern implementiert (die maximale Häufigkeit ist sehr ähnlich)

Hier ist, was ich bisher versucht habe Beispiele für Eingabe / Ausgabe, bei denen dies fehlschlägt: "Wehe reserviert" Die Antwort sollte so zurückhaltend sein, was ich bekomme, ist eigentlich so serviert  Ich habe diese Methode gewählt, weil sie effizienter ist. Das Zeitlimit für Java beträgt 2 Sekunden.

Update: 7. April. Ich habe die Lösung für mein Problem gefunden, aber die CPU-Zeit ist zu groß, also muss ich es optimieren. Sie sollte nicht höher als 2000 ms sein und liegt derzeit bei etwa 6000 ms. Jetzt konzentriere ich mich auf die Optimierung.

Wo soll ich die Regeln implementieren und wie (idealerweise auf eine effizientere Weise als mit einer Matrix)?

Falls Sie irgendwelche Fragen haben oder etwas Unklares übrig gelassen haben, wenden Sie sich bitte an