algorithm - Encontrar anagramas para una palabra dada
data-structures language-agnostic (12)
Algoritmo de ejemplo:
Open dictionary
Create empty hashmap H
For each word in dictionary:
Create a key that is the word''s letters sorted alphabetically (and forced to one case)
Add the word to the list of words accessed by the hash key in H
Para verificar todos los anagramas de una palabra dada:
Create a key that is the letters of the word, sorted (and forced to one case)
Look up that key in H
You now have a list of all anagrams
Relativamente rápido de construir, increíblemente rápido en la búsqueda.
Dos palabras son anagramas si una de ellas tiene exactamente los mismos caracteres que la de otra palabra.
Ejemplo: Anagram y Nagaram son anagramas (no distinguen entre mayúsculas y minúsculas).
Ahora hay muchas preguntas similares a esto. Un par de enfoques para determinar si dos cadenas son anagramas son:
1) Sort las cuerdas y compárelas.
2) Cree un frequency map para estas cadenas y verifique si son iguales o no.
Pero en este caso, se nos da una palabra (en aras de la simplicidad, supongamos una sola palabra y solo tendrá anagramas de una sola palabra) y necesitamos encontrar anagramas para eso.
La solución que tengo en mente es que podemos generar todas las permutaciones para la palabra y verificar cuál de estas palabras existe en el diccionario . Pero claramente, esto es altamente ineficiente. Sí, el diccionario está disponible también.
Entonces, ¿qué alternativas tenemos aquí?
También leí en un hilo similar que se puede hacer algo con Tries pero la persona no explicó en qué consistía el algoritmo y por qué usamos un Trie en primer lugar, solo una implementación se proporcionó también en Python o Ruby. Así que eso no fue realmente útil, razón por la cual he creado este nuevo hilo. Si alguien quiere compartir su implementación (que no sea C, C ++ o Java), explíquelo amablemente.
Bueno, Tries haría más fácil verificar si la palabra existe. Entonces, si pones todo el diccionario en un trie:
http://en.wikipedia.org/wiki/Trie
luego puedes tomar tu palabra y realizar un retroceso simple tomando un char y comprobando recursivamente si podemos "caminar" hacia abajo por el Trie con cualquier combinación del resto de los caracteres (sumando un carácter a la vez). Cuando todos los caracteres se utilizan en una rama de recursión y había una ruta válida en el Trie, entonces la palabra existe.
Trie ayuda porque es una buena condición de detención: podemos verificar si la parte de una cadena, por ejemplo, "Anag" es una ruta válida en el trie, si no podemos romper esa rama de recursividad perticular. Esto significa que no tenemos que verificar cada permutación de los personajes.
En pseudo-código
checkAllChars(currentPositionInTrie, currentlyUsedChars, restOfWord)
if (restOfWord == 0)
{
AddWord(currentlyUsedChar)
}
else
{
foreach (char in restOfWord)
{
nextPositionInTrie = Trie.Walk(currentPositionInTrie, char)
if (nextPositionInTrie != Positions.NOT_POSSIBLE)
{
checkAllChars(nextPositionInTrie, currentlyUsedChars.With(char), restOfWord.Without(char))
}
}
}
Obviamente necesitas una buena estructura de datos de Trie que te permita progresivamente "caminar" por el árbol y verificar en cada nodo si hay una ruta con el carácter dado a cualquier nodo siguiente ...
Eso depende de cómo almacene su diccionario. Si se trata de una matriz simple de palabras, ningún algoritmo será más rápido que lineal.
Si está ordenado, aquí hay un enfoque que puede funcionar. Lo he inventado hace un momento, pero supongo que es más rápido que el enfoque lineal.
- Denote tu diccionario como D, prefijo actual como S. S = 0;
- Usted crea un mapa de frecuencia para su palabra. Permite denotarlo por F.
- Usando la búsqueda binaria, encuentre los punteros para comenzar con cada letra en el diccionario. Vamos a denotar esta matriz de punteros por P.
- Para cada carácter c de A a Z, si F [c] == 0, sáltelo, sino
- S + = c;
- F [c] -;
- P <- para cada carácter i P [i] = puntero a la primera palabra que comienza con S + i.
- Llame recursivamente al paso 4 hasta que encuentre una coincidencia para su palabra o hasta que encuentre que no existe tal coincidencia.
Así es como lo haría, de todos modos. Debería haber un enfoque más convencional, pero esto es más rápido que lineal.
Generar todas las permutaciones es fácil, supongo que le preocupa que verificar su existencia en el diccionario sea la parte "altamente ineficiente". Pero eso en realidad depende de la estructura de datos que use para el diccionario: por supuesto, una lista de palabras sería ineficaz para su caso de uso. Hablando de http://en.wikipedia.org/wiki/Trie , probablemente serían una representación ideal, y bastante eficiente también.
Otra posibilidad sería hacer un preprocesamiento en su diccionario, por ejemplo, crear una tabla hash donde las claves sean las letras de la palabra ordenadas, y los valores sean listas de palabras. Incluso puede serializar esta tabla hash para que pueda escribirla en un archivo y volver a cargarla rápidamente más tarde. Luego, para buscar anagramas, simplemente ordena la palabra dada y busca la entrada correspondiente en la tabla hash.
Primero compruebe si la longitud de las cadenas es la misma. luego verifique si la suma de los caracteres en ambas cadenas es la misma (es decir, la suma del código ascii), entonces las palabras son anagramas, más no un anagrama
Sabemos que si dos palabras no tienen la misma longitud, no son anagramas. Entonces puede dividir su diccionario en grupos de palabras de la misma longitud.
Ahora nos enfocamos en solo uno de estos grupos y, básicamente, todas las palabras tienen exactamente la misma longitud en este universo más pequeño.
Si cada posición de letra es una dimensión, y el valor en esa dimensión se basa en la letra (digamos el código ASCII). Luego puede calcular la longitud del vector de palabra.
Por ejemplo, diga ''A'' = 65, ''B'' = 66, luego length("AB") = sqrt(65*65 + 66*66) . Obviamente, length("AB") = length("BA") .
Claramente, si dos palabras son anagramas, entonces sus vectores tienen la misma longitud. La siguiente pregunta es si los vectores de dos palabras (del mismo número de letras) tienen la misma longitud, ¿son anagramas? Intuitivamente, diría que no, dado que todos los vectores con esa longitud forman una esfera, hay muchos. No estoy seguro, ya que estamos en el espacio entero en este caso, cuántos hay en realidad.
Pero al menos te permite dividir tu diccionario aún más. Para cada palabra en su diccionario, calcule la distancia del vector: for(each letter c) { distance += c*c }; distance = sqrt(distance); for(each letter c) { distance += c*c }; distance = sqrt(distance);
A continuación, cree un mapa para todas las palabras de longitud n , y clave con la distancia y el valor es una lista de palabras de longitud n que ceden esa distancia particular.
Crearás un mapa para cada distancia.
Entonces su búsqueda se convierte en el siguiente algoritmo:
- Usa el mapa correcto del diccionario basado en la longitud de la palabra
- Calcule la longitud del vector de su palabra
- Busque la lista de palabras que coincidan con esa longitud
- Revise la lista y elija los anagramas usando un algoritmo ingenuo, ahora la lista de candidatos se reduce en gran medida
Se me ocurrió una nueva solución, supongo. Utiliza el teorema fundamental de la aritmética. Entonces, la idea es usar una matriz de los primeros 26 números primos. Luego, para cada letra de la palabra de entrada obtenemos el número primo correspondiente A = 2, B = 3, C = 5, D = 7 ... y luego calculamos el producto de nuestra palabra de entrada. A continuación hacemos esto para cada palabra en el diccionario y si una palabra coincide con nuestra palabra de entrada, la agregamos a la lista resultante. Todos los anagramas tendrán la misma firma porque
Cualquier entero mayor que 1 es un número primo, o puede escribirse como un producto único de números primos (ignorando el orden).
Aquí está el código. Convierto la palabra en MAYÚSCULAS y 65 es la posición de A que corresponde a mi primer número primo:
private int[] PRIMES = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
107, 109, 113 };
Este es el método:
private long calculateProduct(char[] letters) {
long result = 1L;
for (char c : letters) {
if (c < 65) {
return -1;
}
int pos = c - 65;
result *= PRIMES[pos];
}
return result;
}
Una solución es: asignar los números primos a los caracteres alfabéticos y multiplicar el número primo
For ex -
a -> 2
b -> 3
......
.......
......
z -> 101
Asi que
''ab'' -> 6
''ba'' -> 6
''bab'' -> 18
''abba'' -> 36
''baba'' -> 36
Obtenga MUL_number para la palabra dada. devuelve todas las palabras del diccionario que tienen el mismo MUL_número que la palabra dada
intentado implementar la solución hashmap
public class Dictionary {
public static void main(String[] args){
String[] Dictionary=new String[]{"dog","god","tool","loot","rose","sore"};
HashMap<String,String> h=new HashMap<String, String>();
QuickSort q=new QuickSort();
for(int i=0;i<Dictionary.length;i++){
String temp =new String();
temp= q.quickSort(Dictionary[i]);//sorted word e.g dgo for dog
if(!h.containsKey(temp)){
h.put(temp,Dictionary[i]);
}
else
{
String s=h.get(temp);
h.put(temp,s + " , "+ Dictionary[i]);
}
}
String word=new String(){"tolo"};
String sortedword = q.quickSort(word);
if(h.containsKey(sortedword.toLowerCase())){ //used lowercase to make the words case sensitive
System.out.println("anagrams from Dictionary : " + h.get(sortedword.toLowerCase()));
}
}
static void Main(string[] args)
{
string str1 = "Tom Marvolo Riddle";
string str2 = "I am Lord Voldemort";
str2= str2.Replace(" ", string.Empty);
str1 = str1.Replace(" ", string.Empty);
if (str1.Length != str2.Length)
Console.WriteLine("Strings are not anagram");
else
{
str1 = str1.ToUpper();
str2 = str2.ToUpper();
int countStr1 = 0;
int countStr2 = 0;
for (int i = 0; i < str1.Length; i++)
{
countStr1 += str1[i];
countStr2 += str2[i];
}
if(countStr2!=countStr1)
Console.WriteLine("Strings are not anagram");
else Console.WriteLine("Strings are anagram");
}
Console.Read();
}
- Calcule el vector de conteo de frecuencia para cada palabra en el diccionario, un vector de longitud de la lista del alfabeto.
- generar un vector gaussiano aleatorio de la longitud de la lista del alfabeto
proyecte el vector de recuento de cada palabra de diccionario en esta dirección aleatoria y almacene el valor (inserte tal que la matriz de valores esté ordenada).
Dada una nueva palabra de prueba, proyectarla en la misma dirección aleatoria utilizada para las palabras del diccionario.
- Haga una búsqueda binaria para encontrar la lista de palabras que se correlacionan con el mismo valor.
- Verificar si cada palabra obtenida como arriba es de hecho un anagrama verdadero. Si no, elimínelo de la lista.
- Devuelve los elementos restantes de la lista.
PD: El procedimiento anterior es una generalización del procedimiento de número primo que potencialmente puede generar números grandes (y por lo tanto problemas de precisión computacional)
- Reduzca las palabras a, por ejemplo, minúsculas (
clojure.string/lower-case). - Clasifíquelos (
group-by) por correspondencia de frecuencia de letras (frequencies). - Suelta los mapas de frecuencia,
- ... dejando las colecciones de anagramas.
( These ) son las funciones correspondientes en el dialecto Lisp Clojure.
Toda la función se puede expresar así:
(defn anagrams [dict]
(->> dict
(map clojure.string/lower-case)
(group-by frequencies)
vals))
Por ejemplo,
(anagrams ["Salt" "last" "one" "eon" "plod"])
;(["salt" "last"] ["one" "eon"] ["plod"])
Una función de indexación que asigna cada cosa a su colección es
(defn index [xss]
(into {} (for [xs xss, x xs] [x xs])))
Para que, por ejemplo,
((comp index anagrams) ["Salt" "last" "one" "eon" "plod"])
;{"salt" ["salt" "last"], "last" ["salt" "last"], "one" ["one" "eon"], "eon" ["one" "eon"], "plod" ["plod"]}
... donde comp es el operador de composición funcional.