string - silabas - palabras en desorden

Cómo encontrar palabras de palabras revueltas

Question

Estoy tratando de encontrar una manera de encontrar palabras específicas en el texto codificado que aparecen consecutivamente. Los caracteres que no se encuentran tendrán una X en su lugar.

Por ejemplo, digamos que la lista de palabras del diccionario es:

jane
john
brownbag
foo
youth

y texto codificado:

ofozlhuoyt => fooXXyouth
yuawbnrobgajen => XXbrownbagjane
janjeohn => (nothing since jane and john aren''t consecutive)

Enfoque que estoy intentando:

Diga, tengo un hash con las teclas de la a la z con el conjunto como valores para cada tecla. Cada número en el conjunto representará el índice donde de la palabra que contiene el personaje en particular.

Del ejemplo de arriba:

{a: [0,2]}
{b: [2]}
{c: []}
{e: [0]}
{f: [3]}
{g: [2]}
{h: [1,4]}
{j: [0,1]}
...
{n: [0,1,2]}
{o: [1,2,3,4]}
{r: [2]}
{u: [4]}
{t: [4]}
{w: [2]}
{y: [4]}
...
{z: []}

Después de preparar lo anterior, podemos comenzar a buscar cada carácter del texto codificado:

Primera cadena: ofozlhuoyt

1. o => existe en 1, 2, 3 y 4

2. comenzar con 1: jane (longitud 4)

3. obtener 4 caracteres: ofoz

4. "jane".sort(false) == "ofoz".sort(false)?

5. si es falso: repita los pasos 1 a 3 para 2 (john)

6. si es verdadero: agregue foo a la lista de palabras correctas y comience el paso 0 con z

¿Hay una mejor manera de hacer esto? Siento que existe una mejor estructura de datos para resolver algo como esto, pero no puedo descifrar cuál usar.

Answer 1

¡Puedes usar números primos!

Cuando multiplica n números primos, el producto que obtenga será diferente de cualquier otra combinación de primos.

En su problema, la clave es que el orden no importa, por lo que la clasificación será una pérdida de tiempo . En otras palabras,

''jane'' == ''ejna'' == ''jnea'' == ...

Por lo tanto, puede crear su propia función hash basada en la propiedad de prima fría y usar la conmutatividad sobre la multiplicación para evitar la clasificación / búsqueda de cadenas por completo. Y en Python, ni siquiera tiene que preocuparse por el tamaño de las entradas; eso será útil en caso de que tu diccionario tenga palabras realmente grandes.

A continuación se muestra un simple dict cartas de mapeo a los primeros 26 primos, y la función hash que lo acompaña.

letters_to_primes = {''a'': 2, ''b'': 3, ''c'': 5, ''d'': 7, ... ''x'': 89, ''y'': 97, ''z'': 101}
def my_prime_hash(word):
sum = 1
for letter in word:
sum = sum * letters_to_primes[letter] # Multiplication is commutative!
return sum

De nuevo, la propiedad clave que estamos explotando aquí es que

my_prime_hash(''jane'') == my_prime_hash(''enaj'') == ... == 27434

Ahora simplemente necesitamos crear nuestro dict de las palabras del diccionario dado. Propongo una tabla de hash de encadenamiento externo . Vamos a llamarlo ''hashed_words''.

# Given these words
words = [''jane'', ''john'', ''brownbag'', ''foo'', ''youth'', ''nib'', ''bin'']
# Compute the hash table
hashed_words = {}
for word in words:
w_hash = my_prime_hash(word)
if w_hash in hashed_words: hashed_words[w_hash].append(word)
else: hashed_words[w_hash] = [word]

Después de ejecutarlo, hashed_words se ve así:

{1113571: [''john''], 27434: [''jane''],
28717: [''foo''], 448956643: [''youth''],
3131090838L: [''brownbag''], 2967: [''nib'', ''bin'']}

que es lo que queremos

Ahora puede comenzar a descifrar la palabra codificada calculando los productos de las letras y verificar en cada punto si el producto está en hashed_words. Una máquina de estados como la que otros han propuesto es necesaria para casos como ''mart'' e ''inteligente'' en la palabra codificada ''mrtasgth'' (ver comentarios a continuación).

Nota: En lugar de asignar números primos en orden ascendente, podría considerar la distribución de frecuencia de todas las letras que ocurren en su diccionario y asignar el número primo más bajo a la letra con la frecuencia más alta. De hecho, esto ahorrará memoria al crear su tabla hash ''hashed_words''.

Answer 2

Existe una forma potencialmente más rápida, siempre que tenga suficiente memoria para implementarla.

Primero, genera todas las permutaciones para cada palabra. Entonces para "jane" tendrías:

aejn
aenj
ajen
ajne
anej
anje
etc.

Luego, construya una máquina de estados para el algoritmo Aho-Corasick , con cada una de las permutaciones para que una sola palabra pase al mismo estado final. Ese estado final daría salida a la cadena que está buscando.

Ahora ejecuta el texto a través de la máquina de estado. El resultado serían las palabras que se encuentran y sus posiciones. Luego puede ordenar las palabras encontradas por posición y determinar si aparecen consecutivamente.

La máquina de estados es potencialmente muy grande (n! Estados para cada palabra, donde n es el número de caracteres de la palabra), y llevará algún tiempo construirla. Pero una vez que está construido, coincide muy rápidamente. Si su lista de palabras es estática y tiene mucho texto para buscar, este es el camino a seguir. Siempre que tenga suficiente memoria.

Utilicé un algoritmo Aho-Corasick modificado que buscaba texto en busca de ocurrencias de millones de frases (nombres de bandas y canciones) en títulos de videos. La máquina de estado ocupaba aproximadamente 10 gigabytes de RAM y tardaba aproximadamente una hora en construirse, pero fue rápida en lo que respecta a la coincidencia.

Answer 3

Tal vez algo así como:

http://en.wikipedia.org/wiki/Rabin-Karp_algorithm

que es muy similar a la idea hash y está relacionado con el algoritmo aho-corasick