Ho scritto un piccolo programma che cerca di trovare una connessione tra due parole inglesi di uguale lunghezza. La Parola A si trasformerà in Parola B cambiando una lettera alla volta, ogni parola appena creata deve essere una parola inglese.Un modo più efficiente di trovare parole inglesi distanti una lettera dall'altra
Ad esempio:
Word A = BANG
Word B = DUST
Risultato:
BANG -> BUNG ->BUNT -> DUNT -> DUST
Il mio processo:
Caricare un lista di parole inglese (costituiti da 109582 parole) in un
Map<Integer, List<String>> _wordMap = new HashMap();, chiave sarà la lunghezza della parola.Utente inserito in 2 parole.
createGraph crea un grafico.
calcolare il percorso più breve tra questi 2 nodi
stampa il risultato.
Tutto funziona perfettamente bene, ma non sono soddisfatto con il tempo impiegato nel passaggio 3.
See:
Completely loaded 109582 words!
CreateMap took: 30 milsecs
CreateGraph took: 17417 milsecs
(HOISE : HORSE)
(HOISE : POISE)
(POISE : PRISE)
(ARISE : PRISE)
(ANISE : ARISE)
(ANILE : ANISE)
(ANILE : ANKLE)
The wholething took: 17866 milsecs
non sono soddisfatto con il tempo necessario creare il grafico in punto 3, ecco il mio codice per esso (sto usando JGraphT per il grafico):
private List<String> _wordList = new ArrayList(); // list of all 109582 English words
private Map<Integer, List<String>> _wordMap = new HashMap(); // Map grouping all the words by their length()
private UndirectedGraph<String, DefaultEdge> _wordGraph =
new SimpleGraph<String, DefaultEdge>(DefaultEdge.class); // Graph used to calculate the shortest path from one node to the other.
private void createGraph(int wordLength){
long before = System.currentTimeMillis();
List<String> words = _wordMap.get(wordLength);
for(String word:words){
_wordGraph.addVertex(word); // adds a node
for(String wordToTest : _wordList){
if (isSimilar(word, wordToTest)) {
_wordGraph.addVertex(wordToTest); // adds another node
_wordGraph.addEdge(word, wordToTest); // connecting 2 nodes if they are one letter off from eachother
}
}
}
System.out.println("CreateGraph took: " + (System.currentTimeMillis() - before)+ " milsecs");
}
private boolean isSimilar(String wordA, String wordB) {
if(wordA.length() != wordB.length()){
return false;
}
int matchingLetters = 0;
if (wordA.equalsIgnoreCase(wordB)) {
return false;
}
for (int i = 0; i < wordA.length(); i++) {
if (wordA.charAt(i) == wordB.charAt(i)) {
matchingLetters++;
}
}
if (matchingLetters == wordA.length() - 1) {
return true;
}
return false;
}
La mia domanda:
Come posso migliorare il mio algoritmo simmetrico per accelerare il processo?
Per qualsiasi redattore che sta leggendo questo, sì l'ho creato dopo aver visto il thread da/r/askreddit ieri.
Qualsiasi motivo per non utilizzare la distanza di Levenshtein? http://en.wikipedia.org/wiki/Levenshtein_distance –
Stai solo cercando di trovare il numero minimo di trasformazioni per creare Word B da Word A? Word A e Word B sono i parametri di input (cioè KNOWN in anticipo)? In tal caso, dovresti usare la distanza di Levenshtein come menzionato sopra. Tuttavia, sembra che tu voglia tradurre una lettera alla volta e che ogni parola intermedia debba anche essere una parola inglese? Tuttavia, se ciò è vero e considerando il tuo esempio di "BANG -> BUNG -> BUNT -> DUNT -> DUST" ... sono BUNG e BUNT parole davvero inglesi? Oppure .. è solo Word A il parametro di input e Word B è il risultato della trasformazione? Così confuso ... – GreenieMeanie
@GreenieMeanie Puoi cercare quelle due parole su un dizionario se non hai familiarità con loro, quelle 2 sono parole inglesi effettive. E usare la distanza di Levenshtein non ha nulla a che fare con la mia domanda, il collo di bottiglia con il mio programma sta estraendo tutti i dati da un file di testo e poi li colleghi tutti in un grafico, che Jon mi ha già aiutato a risolvere, come calcolare il percorso più breve non fa parte della mia domanda (e non ho problemi a risolvere quella parte da sola). Ho solo chiesto come rompere il collo della bottiglia, se questo non ti era chiaro nella mia domanda iniziale, è quello che intendevo in realtà. – 16dots