Napisałem mały program, który próbuje znaleźć połączenie między dwoma równej długości angielskich słów. Słowo A zmieni się w Słowo B, zmieniając jedną literę na raz, każde nowo utworzone słowo musi być słowem angielskim.Bardziej skuteczny sposób na znalezienie angielskich słów, które są jedną literę od siebie
Na przykład:
Word A = BANG
Word B = DUST
Wynik:
BANG -> BUNG ->BUNT -> DUNT -> DUST
Mój proces:
Załaduj wordlist English (składają 109582 słów) do
Map<Integer, List<String>> _wordMap = new HashMap();, klucz zostanie długość słowa.Użytkownik wstawić 2 słowa.
createGraph tworzy wykres.
obliczyć najkrótszą ścieżkę między tymi węzłami 2
drukuje wyniki.
Wszystko działa perfekcyjnie, ale nie jestem zadowolony z czasu zajęło w kroku 3.
Patrz:
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
nie jestem zadowolony z czasu potrzebnego stworzyć wykres na kroku 3, oto mój kod dla niego (używam JgraphT na wykresie):
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;
}
Moje pytanie:
Jak mogę poprawić mój algorytm Inorder aby przyspieszyć ten proces?
Dla każdego reddytora, który to czyta, tak stworzyłem to po obejrzeniu wątku z/r/askreddit wczoraj.
Jakikolwiek powód, aby nie używać odległości Levenshtein? http://en.wikipedia.org/wiki/Levenshtein_distance –
Czy próbujesz znaleźć minimalną liczbę transformacji, aby utworzyć Słowo B ze Słowa A? Czy słowo A i słowo B to parametry wejściowe (tj. ZNANE wcześniej)? W takim przypadku powinieneś użyć odległości Levenshteina, jak wspomniano powyżej. Jednak brzmi to tak, jakbyś chciał tłumaczyć jedną literę na raz i że każde słowo pośrednie musi być również angielskim słowem? Ale jeśli to prawda i biorąc pod uwagę twój przykład "BANG -> BUNG -> BUNT -> DUNT -> DUST" ... czy BUNG i BUNT są naprawdę angielskimi słowami? Czy też tylko słowo A jest parametrem wejściowym, a słowo B jest wynikiem transformacji? Tak zdezorientowany ... – GreenieMeanie
@GreenieMeanie Możesz wyszukać te 2 słowa w słowniku, jeśli ich nie znasz, te 2 to prawdziwe angielskie słowa. I używanie dystansu Levenshteina nie ma nic wspólnego z moim pytaniem, szyjka butelki z moim programem wyciąga wszystkie dane z pliku tekstowego, a następnie łączy je wszystkie na wykresie, na którym Jon już pomógł mi rozwiązać, jak obliczyć najkrótszą ścieżkę nie jest częścią mojego pytania (i nie mam problemu z rozwiązaniem tej części siebie). Pytałem tylko, jak przełamać wąskie gardło, jeśli nie było to dla ciebie jasne w moim pierwotnym pytaniu, to właśnie miałem na myśli. – 16dots