obtener lista de anagramas de un diccionario

Question

Básicamente, los anagramas son como la permutación de string.E.g stack, sackt, stakc todos son anagramas de stack (las palabras anteriores no son significativas). De todos modos, podrías haber entendido lo que básicamente quise decir.

Ahora, quiero una lista de anagrams dada millones de palabras o simplemente decir de un diccionario.

Mi pregunta básica es Find total number of unique anagrams in a dictionary?

ordenación y comparación no funcionará, ya que es la complejidad de tiempo es bastante malo.

Pensé en usar tabla hash, cadena como clave.

Pero el problema es, ¿cuál debería ser la función hash? Sería útil si se proporciona algún pseudocódigo . Algunos otros enfoques mejores que los enfoques mencionados también serían útiles.

Gracias.

Answer 1

La solución obvia es asignar cada carácter a un número primo y multiplicar los números primos. Así que si 'a'' -> 2 y 'b' -> 3, a continuación,

• 'ab' -> 6
• 'ba' -> 6
• 'bab' -> 18
• 'Abba' -> 36
• 'baba' -> 36

para minimizar la posibilidad de desbordamiento, los números primos más pequeños podrían ser asignados a las letras más frecuentes (e, t, i, a, n) Nota: La 26ma prima es 101.

ACTUALIZACIÓN: an implementation can be found here

Answer 2

Una posible función hash podría ser (suponiendo solo palabras en inglés) un recuento ordenado del número de apariciones de cada letra. Entonces para "anagrama" generaría [('a', 3), ('g', 1), ('n', 1), ('m', 1), ('r', 1)].

Alternativamente, podría obtener una agrupación inexacta generando una máscara de bits de su palabra donde para los bits 0-25 cada bit representara la presencia o ausencia de esa letra (bit 0 representando 'a' hasta el bit 25 representando 'z') . Pero luego tendrías que hacer un poco más de procesamiento para dividir cada grupo hash aún más para distinguir, p. "a" de "demasiado".

¿Alguna de estas ideas ayuda? ¿Algún lenguaje de implementación particular en mente (podría hacer C++, python o Scala)?

Editar: se ha añadido algún ejemplo de código Scala y de salida:

OK: Estoy en el modo de Scala en el momento, así que he toqué algo que ver con lo que pides, pero (ejem) se puede no ser muy claro si no está familiarizado con Scala o la programación funcional.

El uso de una gran lista de palabras en inglés desde aquí: http://scrapmaker.com/data/wordlists/twelve-dicts/2of12.txt

corro el código Scala en ellos (tarda unos 5 segundos utilizando Scala 2.9 en el modo de escritura, incluyendo el tiempo para compilar, con un diccionario de alrededor de 40.000 palabras . No es el código más eficiente, pero lo primero que se me viene a la mente).

// Hashing function to go from a word to a sorted list of letter counts 
def toHash(b:String) = b.groupBy(x=>x).map(v => (v._1, v._2.size)).toList.sortWith(_._1 < _._1) 


// Read all words from file, one word per line 
val lines = scala.io.Source.fromFile("2of12.txt").getLines 

// Go from list of words to list of (hashed word, word) 
val hashed = lines.map(l => (toHash(l), l)).toList 

// Group all the words by hash (hence group all anagrams together) 
val grouped = hashed.groupBy(x => x._1).map(els => (els._1, els._2.map(_._2))) 

// Sort the resultant anagram sets so the largest come first 
val sorted = grouped.toList.sortWith(_._2.size > _._2.size) 

for (set <- sorted.slice(0, 10)) 
{ 
    println(set._2) 
} 

Este vuelca a cabo los primeros 10 juegos de anagramas (conjuntos con la primera mayoría de los miembros) ser:

List(caret, cater, crate, react, trace) 
List(reins, resin, rinse, risen, siren) 
List(luster, result, rustle, sutler, ulster) 
List(astir, sitar, stair, stria, tarsi) 
List(latrine, ratline, reliant, retinal) 
List(caper, crape, pacer, recap) 
List(merit, miter, remit, timer) 
List(notes, onset, steno, stone) 
List(lair, liar, lira, rail) 
List(drawer, redraw, reward, warder) 

Tenga en cuenta que este utiliza la primera sugerencia (lista de cargos de letras) no el método de máscara de bits más complicado.

Edición 2: Se puede reemplazar la función hash con un mecanismo simple de los caracteres de cada palabra (como lo sugiere JAB) y obtener el mismo resultado con más claro/código más rápido:

def toHash(b:String) = b.toList.sortWith(_<_) 

Answer 3

Ordenar y comparar no funcionará ya que la complejidad del tiempo es bastante mala.

Intercambiar complejidad del tiempo para memoria adicional, simplemente almacenar los cargos de las letras de una palabra en un 26- char (o su equivalente en cualquier idioma que está utilizando, y suponiendo que está utilizando el alfabeto romano y solo caracteres alfabéticos) array y hash the array. Estás atrapado con O (n) el tiempo relativo a la longitud de la palabra, pero la mayoría de las palabras en inglés no son tan largas.

p. Ej. stack, sackt, y habría stakc todos tienen una matriz con las ubicaciones para s, t, a, c, k == 1 y el resto todo listo para 0.

---

Basado en su comentario, lo que implica que de hecho estás de acuerdo con ordenar los caracteres de una palabra, siempre y cuando no estés ordenando las palabras, podrías hacer algo incluso más simple que la respuesta de Alex y simplemente ordenar los caracteres en las cadenas de palabras y calcular los resultados. (Larsmans lo dijo primero, pero no lo publicó como respuesta, así que ...)

Answer 4

Si XOR los valores de código hash de cada carácter, y luego XOR el resultado por la longitud de entrada, obtendrá el mismo valor independientemente del orden de la palabra, lo que significa que todos los anagramas producirán el mismo hash. (XORing por la longitud impide 'jefe' y 'bo' de devolver el mismo valor, ya que el hash de la 's' contra sí misma es siempre 0.)

Ejemplo:

int AnagramHash(string input) 
{ 
    int output = 0; 

    foreach(char c in input) 
     output ^= c.GetHashCode(); 

    return output^input.Length; 
} 

usted todavía tiene que buscar todas las palabras con el mismo AnagramHash. Actualizaría la tabla del diccionario con un campo para el hash (independientemente de su algoritmo) para reducir el cálculo general.

EDIT: Además, como nota al margen, XOR es la operación más simple realizada por la ALU, de modo que, si termina utilizándola, debería poder generar sus hash con bastante rapidez.

Answer 5

Utilice un HashMap con cadena como clave y la lista (cadena) como valor en lista de cadenas contiene todos los anagramas de una cadena de clave.

La pregunta es similar a "encontrar todos los anagramas de una palabra en un archivo"

Ver algo y código aquí http://justprogrammng.blogspot.com/2012/06/determine-anagrams-of-word-in-file.html