¿Cómo puedo tomar una palabra de entrada (o una secuencia de letras) y sacar una palabra de un diccionario que contiene exactamente esas letras?Buscar anagaram (s) de palabras del diccionario
¿Java tiene una clase de diccionario de inglés (lista de palabras) que puedo usar, o hay implementaciones de código abierto de esto?
¿Cómo puedo optimizar mi código si esto se debe hacer de forma repetida?
Convierte tu diccionario a anagram dictionary. En un diccionario de anagramas, las palabras están indexadas por sus letras en orden alfabético ordenado. Para buscar anagramas para una palabra determinada, clasifique sus letras y busque las correspondientes del diccionario de anagramas.
dos palabras se dice que son anagramas si tienen los exactas mismas letras, exactamente el mismo número de veces.
El cheque por anagrama es ordenar las letras de las palabras y comprobar la igualdad:
sort_letters(word1) == sort_letters(word2)
ahora para encontrar todos los anagramas de una palabra del diccionario dada decir word1, que iba a encontrar todas las palabras el diccionario para el cual se sostiene la prueba anterior. Para optimizar la búsqueda solo podemos buscar palabras que sean de misma longitud.
Si tenemos que hacer esto en varias ocasiones que es mejor hacer un poco de pre-procesamiento . Podemos construir algo así como HashMap, donde en el mapa un string a un conjunto de strings que son anagramas. Algo así como:
Bad ==> Dab
Cat ==> Act, Tac
.....
Ahora da ninguna palabra que puedo mirar hacia el hashMap para obtener todos sus anagramas.
Puede utilizar Anagrams2 example del sitio de Sun como punto de partida
Para un mejor rendimiento, se puede tener una caché de anagramas de uso frecuente para words.Consider usando WeakHashMap/utilizado recientemente para este fin
Como unicornaddict mencionado, puede determinar bastante fácilmente si dos palabras son o no anagramas clasificándolas, sin embargo, esto es ineficiente, especialmente si lo hace repetidamente.
Una tabla de hash preparada probablemente sea la mejor solución al cargar su diccionario al principio del programa. Un algoritmo bastante fácil de escribir para hash/comparando sería
uint HashSomeWord(string someWord)
{
uint hashVal = 0;
//foreach letter in someword
{
//hashVal += letter.ValueAsInteger
}
return hashVal;
}
continuación
bool IsAnagram(string inputWord, string compareTo)
{
if(inputWord == null
|| compareTo == null
|| inputWord.Length != compareTo.Length
|| HashSomeWord(inputWord) != HashSomeSome(compareTo))
{
return false;
}
if(sort_letters(inputWord) == sort_letters(compareTo))
{
return true;
}
}
Mi Java es bastante oxidado, pero creo que lo haría.
Desde mi punto de vista, la clave para esta asignación es encontrar una función (hashFunc) que asigne cadenas a los números de modo que 1) dos anagramas se mapeen al mismo número, 2) dos no anagramas se asignan a números diferentes .Una vez que se ha encontrado la función, se puede aplicar sólo a las entradas de este modo evitar las comparaciones de cadenas tediosas:
if(hashFunc(word1) == hashFunc(word2)) -> word2 is anagram of word1
¿Tiene Java tiene una clase diccionario Inglés (lista de palabras) que puedo usar, o hay código abierto implementaciones de esto?
en sistemas UNIX, se puede comenzar con el words file
¿Cómo puedo optimizar mi código si esto tiene que ser hecho en repetidas ocasiones?
Convierta el diccionario en una tabla hash utilizando hashFunc precalculado.
google para "lista de palabras" y encontrará muchas listas de palabras en inglés. – Amber