Encontrar las palabras del diccionario

Question

Tengo muchas cadenas compuestas que son una combinación de dos o tres palabras en inglés.

e.g. "Spicejet" is a combination of the words "spice" and "jet" 

Necesito separar estas palabras inglesas individuales de tales cadenas compuestas. Mi diccionario va a consistir en alrededor de 100000 palabras.

¿Cuál sería la forma más eficiente de separar palabras individuales de inglés de tales cadenas compuestas?

Answer 1

Me parece que desea almacenar su diccionario en un Trie o una estructura de datos DAWG.

A Trie ya almacena palabras como palabras compuestas. Por lo tanto, "spicejet" se almacenará como "spice jet" donde * denota el final de una palabra. Todo lo que tienes que hacer es buscar la palabra compuesta en el diccionario y realizar un seguimiento de la cantidad de terminadores de final de palabra que tocas. A partir de ahí, tendrías que probar cada subcadena (en este ejemplo, aún no sabemos si "jet" es una palabra, así que tendremos que buscarlo).

Answer 2

¿Y cómo va a decidir cómo dividir las cosas? Busque en la web y encontrará ejemplos de URL que resultaron tener otros significados.

Suponiendo que no tenían las capitales para seguir adelante, ¿qué hacer con estos (los que vienen a la mente en este momento, sé que hay más.):

PenIsland 
KidsExchange 
TherapistFinder 

El último de ellos es particularmente problemático porque la parte problemática es que dos palabras se ejecutan juntas pero no es una palabra compuesta, el significado cambia por completo cuando la rompes.

Answer 3

Entonces, dada una palabra, ¿es una palabra compuesta, compuesta de otras dos palabras en inglés? Podrías tener algún tipo de tabla de búsqueda para todas esas palabras compuestas, pero si solo examinas a los candidatos e intentas emparejarlos con palabras en inglés, obtendrás falsos positivos.

Editar: parece que tendré que ir a dar algunos ejemplos. Palabras que estaba pensando incluyen:

accustomednesses != accustomed + nesses 
adulthoods != adult + hoods 
agreeabilities != agree + abilities 
willingest != will + ingest 
windlasses != wind + lasses 
withstanding != with + standing 
yourselves != yours + elves 
zoomorphic != zoom + orphic 
ambassadorships != ambassador + ships 
allotropes != allot + ropes 

Aquí hay un código Python para probar a hacer el punto. Conseguirse un diccionario en el disco y tener un ir: (¿? ¿Es una operación de una sola vez al día semanal?)

from __future__ import with_statement 

def opendict(dictionary=r"g:\words\words(3).txt"): 
    with open(dictionary, "r") as f: 
     return set(line.strip() for line in f) 

if __name__ == '__main__': 
    s = opendict() 
    for word in sorted(s): 
     if len(word) >= 10: 
      for i in range(4, len(word)-4): 
       left, right = word[:i], word[i:] 
       if (left in s) and (right in s): 
        if right not in ('nesses',): 
         print word, left, right 

Answer 4

No estoy seguro de cuánto tiempo o la frecuencia que tiene que hacer esto, pero usted' Obviamente, va a querer una búsqueda de diccionario ponderada y rápida.

También querrá tener un mecanismo de resolución de conflictos, tal vez una cola para resolver conflictos manualmente en tuplas que tienen múltiples significados posibles.

Me gustaría ver en Tries. Usando uno puedes encontrar (y ponderar) tus prefijos de manera eficiente, que es precisamente lo que estarás buscando.

Tendrá que compilar el Tries usted mismo a partir de una buena fuente de diccionario, y pesar los nodos en palabras completas para proporcionar un mecanismo de buena calidad de referencia.

Hacemos una lluvia de ideas aquí, pero si usted sabe que su conjunto de datos consiste principalmente en duplets o trillizos, probablemente pueda realizar múltiples búsquedas Trie, por ejemplo, buscar 'Spic' y luego 'ejet' y luego encontrar que ambos resultados un puntaje bajo, abandónelo en 'Spice' y 'Jet', donde ambos Tries producirían un buen resultado combinado entre los dos.

También consideraría utilizar el análisis de frecuencia en los prefijos más comunes hasta un límite arbitrario o dinámico, p. Ej. filtrando 'the' o 'un' o 'in' y ponderando los correspondientes.

¡Suena como un problema divertido, buena suerte!

Answer 5

Se me ocurre que hay un número relativamente pequeño de subcadenas (longitud mínima 2) a partir de cualquier palabra compuesta razonable. Por ejemplo para "spicejet" obtengo:

'sp', 'pi', 'ic', 'ce', 'ej', 'je', 'et', 
'spi', 'pic', 'ice', 'cej', 'eje', 'jet', 
'spic', 'pice', 'icej', 'ceje', 'ejet', 
'spice', 'picej', 'iceje', 'cejet', 
'spicej', 'piceje', 'icejet', 
'spiceje' 'picejet' 

... 26 subcadenas.

lo tanto, encontrar una función para generar todas las personas (diapositiva a través de su cadena mediante pasos de 2, 3, 4 ... (len(yourstring) - 1) y luego simplemente marque cada uno de los de una tabla o conjunto de hash.

existencia

Answer 6

Palabra . que se podría hacer con un trie, o más simplemente con un conjunto (es decir, una tabla hash) Dada una función adecuada, se podría hacer:

# python-ish pseudocode 
def splitword(word): 
    # word is a character array indexed from 0..n-1 

    for i from 1 to n-1: 
     head = word[:i] # first i characters 
     tail = word[i:] # everything else 

     if is_word(head): 
      if i == n-1: 
       return [head] # this was the only valid word; return it as a 1-element list 
      else: 
       rest = splitword(tail) 
       if rest != []: # check whether we successfully split the tail into words 
        return [head] + rest 

    return [] # No successful split found, and 'word' is not a word. 

Básicamente, sólo tratar los diferentes puntos de quiebre para ver si podemos hacer palabras. La recursividad significa que retrocederá hasta que se encuentre una división exitosa.

Por supuesto, esto puede no encontrar los splits que desea. Puede modificar esto para devolver todas las divisiones posibles (en lugar de simplemente la primera que encuentre), y luego hacer algún tipo de suma ponderada, tal vez, para preferir palabras comunes sobre palabras poco comunes.

Answer 7

Una pregunta similar ha sido reciente: Word-separating algorithm. Si quisieras limitar el número de divisiones, harías un seguimiento del número de divisiones en cada una de las tuplas (así que en lugar de un par, un triple).

Answer 8

Usaría el siguiente algoritmo.

1. de inicio con la lista ordenada de las palabras para dividir, y una lista ordenada de palabras disminuido (diccionario).

2. Cree una lista de resultados de los objetos que debe almacenar: la palabra restante y la lista de palabras coincidentes.

3. Rellene la lista de resultados con las palabras para dividir como palabras restantes.

4. Walk a través de la matriz de resultado y el diccionario concurrentemente - siempre el aumento de la menos de la dos, de una manera similar al algoritmo de combinación. De esta manera puede comparar todos los posibles pares coincidentes en una sola pasada.

5. Cada vez que encuentre una coincidencia, es deciruna palabra de división de palabras que comienza con una palabra de diccionario , reemplace la palabra de diccionario coincidente y la parte restante en la lista de resultados. Tienes que tener en cuenta posibles múltiplos.

6. En cualquier momento que la parte restante esté vacía, ha encontrado un resultado final.

7. Cada vez que no encuentra una coincidencia en el "lado izquierdo", en otras palabras, cada vez que se incrementa el puntero del resultado debido ninguna coincidencia, eliminar el elemento resultado correspondiente. Esta palabra no tiene coincidencias y no puede ser dividida.

8. Una vez que llegue a la parte inferior de las listas , obtendrá una lista de resultados parciales. Repetir el bucle hasta que esto está vacío - pase al punto 4.

Answer 9

Si el objetivo es encontrar el "el mayor descanso posible para la entrada" a medida que respondió, entonces el algoritmo podría ser bastante sencillo si usas alguna teoría de grafos Tomas la palabra compuesta y haces un gráfico con un vértice antes y después de cada letra. Tendrás un vértice para cada índice en la cadena y uno más allá del final. A continuación, encontrará todas las palabras legales en su diccionario que son subcadenas de la palabra compuesta. Luego, para cada subcadena legal, agregue un borde con un peso 1 al gráfico que conecta el vértice antes de la primera letra en la subcadena con el vértice después de la última letra en la subcadena. Finalmente, use un algoritmo de ruta más corta para encontrar la ruta con menos bordes entre el primer y el último vértice.

El pseudo código es algo como esto:

parseWords(compoundWord) 
    # Make the graph 
    graph = makeGraph() 
    N = compoundWord.length 
    for index = 0 to N 
     graph.addVertex(i) 

    # Add the edges for each word 
    for index = 0 to N - 1 
     for length = 1 to min(N - index, MAX_WORD_LENGTH) 
      potentialWord = compoundWord.substr(index, length) 
      if dictionary.isElement(potentialWord) 
       graph.addEdge(index, index + length, 1) 

    # Now find a list of edges which define the shortest path 
    edges = graph.shortestPath(0, N) 

    # Change these edges back into words. 
    result = makeList() 
    for e in edges 
     result.add(compoundWord.substr(e.start, e.stop - e.start + 1)) 
    return result 

que, obviamente, no he probado este pseudo-código, y puede haber algunos errores off-by-one de indexación, y no hay cualquier error de comprobación, pero la idea básica está ahí. Hice algo similar a esto en la escuela y funcionó bastante bien. Los bucles de creación de borde son O (M * N), donde N es la longitud de la palabra compuesta, y M es la longitud máxima de palabra en su diccionario o N (el que sea menor). El tiempo de ejecución del algoritmo de ruta más corta dependerá del algoritmo que elija. Dijkstra's viene más a la mente. Creo que su tiempo de ejecución es O (N^2 * log (N)), ya que los bordes máximos posibles son N^2.

Puede usar cualquier algoritmo de ruta más corta. Hay several shortest path algorithms que tienen sus diversas fortalezas y debilidades, pero supongo que para su caso la diferencia no será muy significativa. Si, en lugar de tratar de encontrar la menor cantidad posible de palabras para dividir el compuesto, quisieras encontrar el más posible, entonces le das a los bordes pesas negativas y tratas de encontrar el camino más corto con an algorithm that allows negative weights.

Answer 10

Esto puede ser un problema muy difícil y no hay una solución general sencilla (puede haber heurísticas que funcionen para subconjuntos pequeños).

Nos enfrentamos exactamente a este problema en química, donde los nombres están compuestos por la concatenación de morfemas.Un ejemplo es:

ethylmethylketone 

donde los morfemas son:

ethyl methyl and ketone 

abordamos esto a través de autómatas y la máxima entropía y el código está disponible en Sourceforge

http://www.sf.net/projects/oscar3-chem 

pero se advirtió que tomará algún trabajo.

A veces encontramos ambigüedades y seguimos encontrando una buena manera de informarlo.

Para distinguir entre penIsland y penisLand requeriría heurísticas específicas de dominio. La interpretación probable dependerá del corpus utilizado: ningún problema lingüístico es independiente del dominio o dominios que se analizan.

Como otro ejemplo, la cadena

weeknight 

se puede analizar como

wee knight 

o

week night 

Ambos son "derecho" en el que obedezcan la forma "adj-sustantivo "o" sustantivo-sustantivo ". Ambos tienen "sentido" y el que se elija dependerá del dominio de uso. En un juego de fantasía el primero es más probable y en el comercio el último. Si tiene problemas de este tipo, será útil contar con un corpus de uso acordado que haya sido anotado por expertos (técnicamente un "Estándar de oro" en el procesamiento del lenguaje natural).